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

Seunghun Lee, Shakhar SmorodinskyarXiv 2024 · DOI · arXiv

Abstract

We study the conflict-free chromatic number of hypergraphs derived from the family of facets of $d$-dimensional cyclic polytopes with $n$ vertices. While in odd dimensions $d$ the problem is easy, for even dimensions the problem becomes very difficult and exhibits interesting connections to extremal graph theory. We provide sharp asymptotic bounds for the conflict-free chromatic number in several small even dimensions and non-trivial upper and lower bounds for general even dimensions. The main purpose of this paper is revealing a surprising relation between conflict-free colorings and the celebrated Erdős girth conjecture, opening new avenues for future research.

Introduction

Conflict-free (CF) coloring is a central concept in geometric hypergraph theory, originally motivated by frequency assignment in cellular networks. A hypergraph coloring is conflict-free if every hyperedge contains at least one vertex with a unique color. While CF-colorings for simple geometric objects like points in $\mathbb{R}^2$ with respect to half-spaces are well-understood, requiring $O(\log n)$ colors, higher-dimensional structures present significant challenges.

This work focuses on cyclic polytopes, fundamental objects in discrete geometry. A cyclic polytope $C(n, d)$ is the convex hull of $n$ points on the moment curve in $\mathbb{R}^d$. The problem is to determine the minimum number of colors, $\chi_{cf}(n, d)$, needed to CF-color the hypergraph whose edges are the facets of $C(n, d)$.

Methodology

The authors bridge combinatorial geometry and extremal graph theory through several key techniques.

Gale’s Evenness Criterion

The facets of a cyclic polytope are characterized by Gale’s Evenness Criterion, which states that a subset of $d$ vertices forms a facet if and only if any two vertices not in the subset are separated by an even number of vertices in the subset along the moment curve. This allows the geometric problem to be reformulated as a structured combinatorial hypergraph problem.

Palette Graphs and Eulerian Circuits

To establish upper bounds, the authors introduce the concept of a palette graph. They demonstrate that a valid CF-coloring can be constructed by traversing an Eulerian circuit $C_G$ of a graph $G$ with specific properties.

Eulerian circuit construction: A graph $G$ and its Eulerian circuit $C_G$ are used to assign colors to vertices $v_i$, ensuring the conflict-free property for facets of the cyclic polytope.

By selecting a graph $G$ with high girth (the length of its shortest cycle) and using its vertices as colors, the authors can map the vertices of the cyclic polytope to the vertices of $G$ such that the "evenness" constraints of the facets translate into path properties in $G$ that guarantee at least one unique color per facet.

Key Insights: The Girth Connection

The most significant finding is the asymptotic equivalence between the CF-chromatic number of even-dimensional cyclic polytopes and the Erdős Girth Conjecture. This conjecture asks for the maximum number of edges in a graph that contains no cycles shorter than a given length.

The authors show that for even $d$, the difficulty of finding an optimal CF-coloring is fundamentally tied to the density of graphs avoiding small cycles. This explains the "dimensionality gap": for odd $d$, $\chi_{cf}$ is constant ($\leq 3$), but for even $d \geq 4$, it grows at least as $\Omega(\sqrt{n})$.

Results

The paper establishes sharp asymptotic bounds for several small even dimensions by leveraging known extremal graph constructions:

  • For $d \in \{4, 6, 10\}$, $\chi_{cf} = \Theta(\sqrt{n})$.
  • For $d \in \{8, 14\}$, $\chi_{cf} = \Theta(n^{2/3})$.
  • For $d \in \{12, 18\}$, $\chi_{cf} = \Theta(n^{3/4})$.

For general even dimensions $d \geq 16$, the authors provide upper bounds of $O(n^{1 - \frac{2}{3k-1+\epsilon}})$ where $k = \lfloor d/4 \rfloor$, and a general lower bound of $\Omega(\sqrt{n})$ for all even $d \geq 4$.

Conclusion

This research reveals a deep link between the geometry of cyclic polytopes and extremal graph theory. The dependency on the Erdős Girth Conjecture suggests that further progress in bounding the CF-chromatic number for general even dimensions will likely require breakthroughs in graph theory. Future work may extend the palette graph methodology to other non-hereditary geometric hypergraphs.

Summary updated

Abstract

We study the conflict-free chromatic number of hypergraphs derived from the family of facets of $d$-dimensional cyclic polytopes with $n$ vertices. While in odd dimensions $d$ the problem is easy, for even dimensions the problem becomes very difficult and exhibits interesting connections to extremal graph theory. We provide sharp asymptotic bounds for the conflict-free chromatic number in several small even dimensions and non-trivial upper and lower bounds for general even dimensions. The main purpose of this paper is revealing a surprising relation between conflict-free colorings and the celebrated Erdős girth conjecture, opening new avenues for future research.
BibTeX
@misc{lee2024conflict,
  author = {Seunghun Lee and Shakhar Smorodinsky},
  title = {{On conflict-free colorings of cyclic polytopes and the girth conjecture for graphs}},
  year = {2024},
  eprint = {2408.09391},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2408.09391},
}
Figure