Equitable colorings of hypergraphs with few edges (Q2309544)

Given an \(n\)-uniform hypergraph \(H=(V,E)\) on \(v\) vertices, a proper \(r\)-coloring of the vertices is a function \(c:V\to [r]\) such that for each hyperedge \(e\in E\), and each color \(i\in [r]\), we have \(|e \cap f^{-1}(i)|<n\), i.e. no hyperedge is monochromatic. A proper \(r\) coloring is equitable if, additionally, we have that for any pair of colors \(i,j\in [r]\), \(||f^{-1}(i)|-|f^{-1}(j)|| \leq 1\). The authors consider the problem of determining the minimum number of hyperedges in an \(n\)-uniform hypergraph that is not equitably \(r\)-colorable, and show that it is strictly greater than \(l(n,r)={\frac{n}{\ln n}}^{\frac{r-1}{r}}r^{n-1}\), for all \(r<(\ln n)^{1/5}\), (provided \(r|v\)). In other words, every \(n\)-uniform hypergraph having at most \(l(n,r)\) hyperedges has an equitable \(r\)-coloring. This matches, upto constants, the best lower bound for proper \(r\)-colorable hypergraphs given by \textit{D. D. Cherkashin} and \textit{J. Kozik} [Random Struct. Algorithms 47, No. 3, 407--413 (2015; Zbl 1325.05121)], who gave a simpler proof of the Radhakrishnan-Srinivasan bound [\textit{J. Radhakrishnan} and \textit{A. Srinivasan}, Random Struct. Algorithms 16, No. 1, 4--32 (2000; Zbl 0942.05024)] for \(r=2\) (the celebrated Property B problem of Erdős) and extended it to general \(r\). The best upper bound remains that of [\textit{M. Fiedler} (ed.), Theory of graphs and its applications. Proceedings of the symposium, Smolenice, Czechoslovakia, June 17--20, 1963. Prague: Publishing House of the Czechoslovak Academy of Sciences (1964; Zbl 1437.05005)], of \(O(n^2r^{n-1})\). The general strategy is to first (i) obtain a proper \(r\)-coloring, then (ii) bound the number of excess vertices in each of the color classes, showing that only the classes \(c^{-1}(1),\ldots, c^{-1}(r-1)\) will have excess vertices, and finally (iii) to recolor a small number of vertices in each color class with the color \(r\). To obtain a proper \(r\)-coloring, the recoloring argument of \textit{A. Pluhár} [Random Struct. Algorithms 35, No. 2, 216--221 (2009; Zbl 1209.05097)], which involves considering a random permutation of the vertices and bounding the number of ordered \(r\)-chains, is slightly -- but crucially -- modified to consider the number of ordered \(k\)-chains for all \(k \in [r]\). Next, the number of excess vertices in each color class is bounded using a configuration very similar to ordered \(k\)-chains. Finally, it is shown that there exist a subset of vertices in each color class, having cardinality at least the excess number of vertices in the class, such that recoloring this subset with color \(r\), does not induce any monochromatic hyperedge. This is done by considering \(k\)-complex ordered chains which are more involved variation of ordered \(k\)-chains. Thus, the authors demonstrate the versatility of the recoloring technique, and specifically Pluh\H{a}r's notion of ordered \(k\)-chains to obtain proper \(r\)-colorings of \(n\)-uniform hypergraphs, which are also equitable.