Polychromatic finiteness conjecture for hereditary hypergraph families
Polychromatic finiteness conjecture for hereditary hypergraph families
Let be a hereditary family of hypergraphs, and let be the least integer , if it exists, such that every -heavy member of is polychromatically -colorable; set if no such exists. A hypergraph is -heavy when every edge has size at least , and a coloring is polychromatic when every edge contains a vertex of each of the colors.
Polychromatic finiteness conjecture. If , then for every for any hereditary family .
This conjecture is known when , 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
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.