The linear polychromatic coloring conjecture for hypergraph families

Let H\mathcal{H} be a hypergraph family, and let mH(k)m_\mathcal{H}(k) denote the minimum number of vertices needed to guarantee a polychromatic kk-coloring in the relevant hypergraphs of H\mathcal{H}. Linear polychromatic coloring conjecture. If

mH(2)<m_\mathcal{H}(2)<\infty

for a hypergraph family H\mathcal{H}, then

mH(k)=O(k).m_\mathcal{H}(k)=O(k).

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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.