On conflict-free colorings of cyclic polytopes and the girth conjecture for graphs

We study conflict-free colorings for hypergraphs derived from the family of facets of d-dimensional cyclic polytopes. For odd dimensions d, the problem is fairly easy. However, for even dimensions d the problem becomes very difficult. We provide sharp asymptotic bounds for the conflict-free chromatic number in all even dimensions 4≤ d ≤ 20 except for $d=16$. We also provide non-trivial upper and lower bounds for all even dimensions d. We exhibit a strong relation to the famous Erd{o}s girth conjecture in extremal graph theory which might be of independent interest for the study of conflict-free colorings. Improving the upper or lower bounds for general even dimensions d would imply an improved lower or upper bound (respectively) on the Erd{o}s girth conjecture. Finally, we extend our result for dimension $4$ showing that the hypergraph whose hyperedges are the union of two discrete intervals from $[n]$ of cardinality at least $3$ has conflict-free chromatic number Θ(√n).