Weak and strong versions of the 1-2-3 conjecture for uniform hypergraphs (Q2629488): Difference between revisions

Summary: Given an \(r\)-uniform hypergraph \(H=(V,E)\) and a weight function \(\omega:E\to\{1,\ldots,w\}\), a coloring of vertices of \(H\), induced by \(\omega\), is defined by \(c(v) = \sum_{e\ni v}w(e)\) for all \(v\in V\). If there exists such a coloring that is strong (that means in each edge no color appears more than once), then we say that \(H\) is strongly \(w\)-weighted. Similarly, if the coloring is weak (that means there is no monochromatic edge), then we say that \(H\) is weakly \(w\)-weighted. In this paper, we show that almost all 3 or 4-uniform hypergraphs are strongly 2-weighted (but not 1-weighted) and almost all 5-uniform hypergraphs are either 1 or 2 strongly weighted (with a nontrivial distribution). Furthermore, for \(r\geq 6\) we show that almost all \(r\)-uniform hypergraphs are strongly 1-weighted. We complement these results by showing that almost all 3-uniform hypergraphs are weakly 2-weighted but not 1-weighted and for \(r\geq 4\) almost all \(r\)-uniform hypergraphs are weakly 1-weighted. These results extend a previous work of \textit{L. Addario-Berry} et al. [Discrete Appl. Math. 156, No. 7, 1168--1174 (2008; Zbl 1147.05055)] for graphs. We also prove general lower bounds and show that there are \(r\)-uniform hypergraphs which are not strongly \((r^2-r)\)-weighted and not weakly 2-weighted. Finally, we show that determining whether a particular uniform hypergraph is strongly 2-weighted is NP-complete.