Note on polychromatic coloring of hereditary hypergraph families II
Dömötör Pálvölgyi · 2026
Read Note on polychromatic coloring of hereditary hypergraph families II by Dömötör Pálvölgyi (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-24412.txt.
Introduction
Pálvölgyi extends prior work on polychromatic colorings of hereditary hypergraphs. For h from 4 up, he builds a hypergraph of uniformity twice h minus one with no polychromatic 3-coloring. Yet all of its h-heavy subhypergraphs are 2-colorable, and with the h equals 3 case this gives such cases for every h from 3 up. The build uses complements of h-uniform hypergraphs. For h from 9 up, a probabilistic argument proves existence. Cases h from 4 to 8 are certified by computer check, with code in the appendix.
Catalog record
| CREATOR | Dömötör Pálvölgyi |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 21228 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.24412
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Note on polychromatic coloring of hereditary hypergraph families II Dömötör Pálvölgyi Abstract We extend a recent construction concerning polychromatic colorings of hereditary hypergraph families. For every integer h ≥ 4 h\geq 4 we construct a ( 2 h − 1 ) (2h-1) -uniform hypergraph which has no polychromatic 3 3 -coloring, but all of whose h h -heavy restricted subhypergraphs are 2 2 -colorable. Together with the previously known case h = 3 h=3 , this gives examples with uniformity 2 h − 1 2h-1 for every h ≥ 3 h\geq 3 . The construction is based on complements of suitable h h -uniform hypergraphs on 3 h − 1 3h-1 vertices. For h ≥ 9 h\geq 9 we prove existence by a simple probabilistic argument; the remaining cases 4 ≤ h ≤ 8 4\leq h\leq 8 are certified by a short exhaustive computer check, whose fully reproducible description and source code are included in the appendix. Disclaimer. This manuscript, including this disclaimer, was written by ChatGPT 5.5 Thinking, based on an interactive discussion with Dömötör Pálvölgyi. The mathematical correctness of the manuscript has been verified by the author. Keywords: hypergraphs, graph colorings, polychromatic coloring, panchromatic coloring, Property B Mathematics Subject Classification (MSC): 05C15 (Coloring of graphs and hypergraphs) A hypergraph \mbox{$\mathcal{H}$}=(V,E) is a collection of subsets of a vertex set V . It is m -uniform if all its edges have size m , and it is h -heavy if all its edges have size at least h . For X\subset V , the trace of \mathcal{H} on X is \mbox{$\mathcal{H}$}[X]=(X,\{e\cap X:e\in E(\mbox{$\mathcal{H}$})\}). A subhypergraph of a trace is called a restricted subhypergraph. A coloring of the vertices of \mathcal{H} with colors 1,\ldots,k is polychromatic if every edge of \mathcal{H} contains all k colors. For k=2 , this is the usual proper 2 -coloring of a hypergraph, also known as Property B. The starting point is the following result from [ 2 ] . For background on geometric hypergraph colorings and their relation to cover-decomposition, see the surveys [ 3 , 4 ] . Theorem 1 ( [ 2 ] ) . There exists a 5 -uniform hypergraph which has no polychromatic 3 -coloring, but all of whose 3 -heavy restricted subhypergraphs are 2 -colorable. Here we prove the corresponding statement for every larger value of the heaviness parameter. Theorem 2 . For every integer h\geq 4 , there exists a (2h-1) -uniform hypergraph \mathcal{H} which has no polychromatic 3 -coloring, but all of whose h -heavy restricted subhypergraphs are 2 -colorable. Roadmap. Section 1 gives the complement construction and reduces Theorem 2 to three elementary conditions on a family of h -sets. Section 2 proves the existence of such families for all h\geq 9 by a random construction and finishes the proof of the theorem modulo the finite cases. Section 3 examines whether a natural covering-design method might reach uniformity 2h+c for fixed c\geq 0 , and explains why the calculation becomes unfavorable as soon as c\geq 1 , while the case c=0 remains a delicate possible next step. Appendix A gives the explicit deterministic data for 4\leq h\leq 8 , Appendix B contains the verification code, and Appendix C briefly records how this manuscript arose from the prompting process. Combining Theorems 1 and 2 , we get examples of uniformity 2h-1 for every h\geq 3 . 1 A complement construction The construction is most naturally described through complements. Fix an integer h\geq 2 and put n=3h-1. Let V be an n -element set. We shall choose a family \mbox{$\mathcal{K}$}\subset{V\choose h} . The sets in \mathcal{K} will be the missing h -sets of an auxiliary hypergraph. Define \mbox{$\mathcal{G}$}={V\choose h}\setminus\mbox{$\mathcal{K}$}, and then define a (2h-1) -uniform hypergraph \mathcal{H} by E(\mbox{$\mathcal{H}$})=\{V\setminus B:B\in\mbox{$\mathcal{G}$}\}. Thus the edges of \mathcal{H} are the complements of the edges of \mathcal{G} . We need three properties of \mathcal{K} . (K1) For every A\in{V\choose h-1} , not all h -sets of the form A\cup\{v\} , v\in V\setminus A , belong to \mathcal{K} . Equivalently, among the 2h extensions of A to an h -set, at least one is not in \mathcal{K} . (K2) For every X\in{V\choose 2h} , there is an h -set R\subset X such that R\in\mbox{$\mathcal{K}$}\quad\hbox{and}\quad X\setminus R\in\mbox{$\mathcal{K}$}. (K3) For every Y\in{V\choose h} , there is a set U\subset V\setminus Y , |U|=h-1 , such that U\cup\{y\}\in\mbox{$\mathcal{K}$}\qquad\hbox{for every }y\in Y. Lemma 3 . If \mbox{$\mathcal{K}$}\subset{V\choose h} satisfies (K1) , (K2) , and (K3) , then the hypergraph \mathcal{H} defined above has no polychromatic 3 -coloring, but all of its h -heavy restricted subhypergraphs are 2 -colorable. Proof. First we show that \mathcal{H} has no polychromatic 3 -coloring. Consider any 3 -coloring of V . One color class S has size at most \left\lfloor{3h-1\over 3}\right\rfloor=h-1. Extend S , if necessary, to an (h-1) -set A . By (K1), some set A\cup\{v\} with v\in V\setminus A does not belong to \mathcal{K} . Hence B=A\cup\{v\}\in\mbox{$\mathcal{G}$}. The corresponding edge V\setminus B of \mathcal{H} misses the color class S . Thus the coloring is not polychromatic. It remains to prove that every h -heavy trace of \mathcal{H} is 2 -colorable. Since every subhypergraph of a 2 -colorable hypergraph is 2 -colorable, it is enough to color the h -heavy part of every trace \mbox{$\mathcal{H}$}[X] . Let X\subset V . We give a red-blue coloring of X with no monochromatic trace edge of size at least h . If |X|\leq 2h-2 , color X as evenly as possible. Then both color classes have size at most h-1 , so no monochromatic h -heavy trace can occur. Suppose next that |X|=2h-1 . Let Y=V\setminus X , so |Y|=h . By (K3), there is a set U\subset X , |U|=h-1 , such that U\cup\{y\}\in\mbox{$\mathcal{K}$}\qquad\hbox{for every }y\in Y. Color U blue and color X\setminus U red. The blue class has size h-1 , so it contains no monochromatic h -heavy trace. If there were a red monochromatic trace of size at least h , then, since the red class has size exactly h , there would be some B\in\mbox{$\mathcal{G}$} such that X\setminus B=X\setminus U. Equivalently, B\cap X=U. As B has size h and U has size h-1 , this means B=U\cup\{y\} for some y\in Y , contradicting the choice of U , because all such sets belong to \mathcal{K} . Now suppose that |X|=2h . By (K2), write X=R\sqcup S with |R|=|S|=h,\qquad R,S\in\mbox{$\mathcal{K}$}. Color R red and S blue. If there were a red monochromatic trace of size at least h , then it would have to be all of R , and hence for some B\in\mbox{$\mathcal{G}$} we would have X\setminus B=R. Thus B\cap X=S . Since |B|=|S|=h , this forces B=S , contradicting S\in\mbox{$\mathcal{K}$} and B\in\mbox{$\mathcal{G}$} . The blue case is symmetric. Finally suppose that |X|\geq 2h+1 . Choose any 2h -subset X_{0}\subset X . By (K2), there is an h -set R\subset X_{0} with R\in\mbox{$\mathcal{K}$} . Color R red and color X\setminus R blue. A red monochromatic trace of size at least h would have to be exactly R . This would imply X\setminus R\subset B for some B\in\mbox{$\mathcal{G}$} , impossible because |X\setminus R|\geq h+1\quad\hbox{while}\quad|B|=h. A blue monochromatic trace would imply R\subset B for some B\in\mbox{$\mathcal{G}$} . Since |R|=|B|=h