The linear polychromatic coloring conjecture for hypergraph families
The linear polychromatic coloring conjecture for hypergraph families
Let be a hypergraph family, and let denote the minimum number of vertices needed to guarantee a polychromatic -coloring in the relevant hypergraphs of . Linear polychromatic coloring conjecture. If
for a hypergraph family , then
The conjecture asserts that finiteness of the two-color threshold forces a linear bound for every number of colors. The surrounding discussion relates this question to shallow hitting sets and the linear bound supplied by the preceding lemma; no resolution is given here.
Sources & referencesView supporting material
Primary source
Balázs Bursics, Bence Csonka and Luca Szepessy, “Hitting sets and colorings of hypergraphs”, arXiv:2307.12154 (2026).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.