Minimum-weight edge discriminators in hypergraphs (Q405305)

Summary: 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, \mathcal E)\), a function \(\lambda: \mathcal V\to \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 \mathcal E\), and \(\sum_{v\in E_i}{\lambda(v)}\neq \sum_{v\in E_j}{\lambda(v)}\), for every two distinct hyperedges \(E_i, E_j \in \mathcal 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, \mathcal E)\), with \(|\mathcal 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 \(\mathcal E\) are mutually disjoint. For \(r\)-uniform hypergraphs \(\mathcal H=(\mathcal V, \mathcal 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, \mathcal E)\), with \(|\mathcal 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.