Minimum-Weight Edge Discriminators in Hypergraphs

In this paper we introduce the notion of minimum-weight edge-discriminators in hypergraphs, and study their various properties. For a hypergraph H = (V , E), a function λ : V → Z+∪{0} is said to be an edge-discriminator on H if ∑v∈Eiλ(v)>0, for all hyperedges Ei ∈ E and ∑v∈Eiλ(v) ≠ ∑v∈Ejλ(v), for every two distinct hyperedges Ei,Ej, ∈ E. An optimal edge-discriminator on H, to be denoted by λH, is an edge-discriminator on H satisfying ∑v∈VλH(v) = minλ ∑v∈Vλ(v), where the minimum is taken over all edge-discriminators on H. We prove that any hypergraph H = (V , E), with |E| = m, satisfies ∑v∈VλH(v) ≤ m(m+1)/2, and the equality holds if and only if the elements of E are mutually disjoint. For r-uniform hypergraphs H = (V,E), it follows from earlier results on Sidon sequences that ∑v∈VλH(v) ≤ |V|r+1+o(|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 H = (V,E), with |E| = m (≥3), satisfies ∑v∈Vλ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.