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 Erdos 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 Erdos 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).