Sum-distinguishing number of sparse hypergraphs (Q6171496)

A vertex labeling of a hypergraph is sum distinguishing if it uses positive integers and the sums of labels taken over the distinct hyperedges are distinct. Let \(s(H)\) be the smallest integer \(N\) such that there is a sum-distinguishing labeling of \(H\) with each label at most \(N\). The largest value of \(s(H)\) over all hypergraphs on \(n\) vertices and \(m\) hyperedges is denoted \(s(n,m)\). It is proven that \(s(n,m)\) is almost-quadratic in \(m\) as long as \(m\) is not too large. More precisely, the following holds: If \(n \leq m \leq n^{O(1)}\) then \(s(n,m) =m^2/w(m)\), where \(w(m)\) is a function that goes to infinity and is smaller than any polynomial in \(m\). The parameter \(s(n,m)\) has close connections to several other graph and hypergraph functions. It answers a question of \textit{A. Gyárfás} et al. [J. Comb. Math. Comb. Comput. 11, 161--172 (1992; Zbl 0755.05082)] whether there are \(n\)-vertex hypergraphs with irregularity strength greater than \(2n\). The result implies that there are \(n\)-vertex hypergraphs with irregularity strength at least \(n^{2-o(1)}.\) The results also imply that \(s^\ast(n) = n2/w(n)\) where \(s^\ast(n)\) is the distinguishing closed-neighborhood number, i.e., the smallest integer \(N\) such that any \(n\)-vertex graph allows for a vertex labeling with positive integers at most \(N\) so that the sums of labels on distinct closed neighborhoods of vertices are distinct.