Note on Polychromatic Coloring of Hereditary Hypergraph Families

Area of Science:

• Combinatorics
• Graph Theory
• Hypergraph Theory

Background:

• Polychromatic coloring is a concept in hypergraph theory.
• Hereditary hypergraph families are collections of hypergraphs closed under subgraphs.
• Previous work by Berge laid foundational understanding in this area.

Purpose of the Study:

• To disprove a conjecture by Keszegh and the author regarding polychromatic colorings.
• To explore the properties of polychromatic colorings in specific hypergraph families.
• To investigate the limitations of current methods for constructing such hypergraphs.

Main Methods:

• Construction of a specific 5-uniform hypergraph.
• Analysis of its polychromatic 3-colorability.
• Examination of the 2-colorability of its restricted subhypergraphs (edges of size at least 3).

Main Results:

• A 5-uniform hypergraph was exhibited that does not possess a polychromatic 3-coloring.
• All restricted subhypergraphs with edges of size at least 3 were shown to be 2-colorable.
• The presented method was found to be insufficient for generating hypergraphs of arbitrary high uniformity.

Conclusions:

• The conjecture by Keszegh and the author is disproven.
• This work represents a significant step in understanding polychromatic colorings of hereditary hypergraph families.
• Connections to panchromatic colorings were also noted.