Polychromatic finiteness conjecture for hereditary hypergraph families

Let F\mathcal F be a hereditary family of hypergraphs, and let mk(F)m_k(\mathcal F) be the least integer mm, if it exists, such that every mm-heavy member of F\mathcal F is polychromatically kk-colorable; set mk(F)=m_k(\mathcal F)=\infty if no such mm exists. A hypergraph is mm-heavy when every edge has size at least mm, and a coloring is polychromatic when every edge contains a vertex of each of the kk colors.

Polychromatic finiteness conjecture. If m2(F)<m_2(\mathcal F)<\infty, then mk(F)<m_k(\mathcal F)<\infty for every kk for any hereditary family F\mathcal F.

This conjecture is known when m2(F)=2m_2(\mathcal F)=2, by a result of Berge, but remains open in general. It asks whether finiteness of the threshold for 2-colorability forces finiteness of the corresponding threshold for every number of colors.

Sources & referencesView supporting material

Primary source

Dömötör Pálvölgyi, “Note on polychromatic coloring of hereditary hypergraph families”, arXiv:2309.04603 (2023).

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.