Minimum-Weight Edge Discriminators in Hypergraphs

Abstract

In this paper we introduce the notion of minimum-weight edge-discriminators in hypergraphs, and study their various properties. For a hypergraph $\mathcal H=(\mathcal V, \mathscr E)$, a function $\lambda: \mathcal V\rightarrow \mathbb Z^{+}\cup\{0\}$ is said to be an edge-discriminator on $\mathcal H$ if $\sum_{v\in E_i}{\lambda(v)}>0$, for all hyperedges $E_i\in \mathscr E$, and $\sum_{v\in E_i}{\lambda(v)}\ne \sum_{v\in E_j}{\lambda(v)}$, for every two distinct hyperedges $E_i, E_j \in \mathscr E$. An optimal edge-discriminator on $\mathcal H$, to be denoted by $\lambda_\mathcal H$, is an edge-discriminator on $\mathcal H$ satisfying $\sum_{v\in \mathcal V}\lambda_\mathcal H (v)=\min_\lambda\sum_{v\in \mathcal V}{\lambda(v)}$, where the minimum is taken over all edge-discriminators on $\mathcal H$.  We prove that any hypergraph $\mathcal H=(\mathcal V, \mathscr E)$,  with $|\mathscr E|=m$, satisfies $\sum_{v\in \mathcal V} \lambda_\mathcal H(v)\leq m(m+1)/2$, and the equality holds if and only if the elements of $\mathscr E$ are mutually disjoint. For $r$-uniform hypergraphs $\mathcal H=(\mathcal V, \mathscr E)$, it follows from earlier results on Sidon sequences that $\sum_{v\in \mathcal V}\lambda_{\mathcal H}(v)\leq |\mathcal V|^{r+1}+o(|\mathcal V|^{r+1})$, and the bound is attained up to a constant factor by the complete $r$-uniform hypergraph. Finally, we show that no optimal edge-discriminator on any hypergraph $\mathcal H=(\mathcal V, \mathscr E)$, with $|\mathscr E|=m~(\geq 3)$, satisfies $\sum_{v\in \mathcal V} \lambda_\mathcal H (v)=m(m+1)/2-1$. This shows that all integer values between $m$ and $m(m+1)/2$ cannot be the weight of an optimal edge-discriminator of a hypergraph, and this raises many other interesting combinatorial questions.