Abstract
For any $c \ge 2$, a $c$-strong coloring of a hypergraph $G$ is an assignment of colors to the vertices of $G$ such that for every edge $e$ of $G$, the vertices of $e$ are colored by at least $\min\{c, |e|\}$ distinct colors. A hypergraph $G$ is $t$-intersecting if every two edges of $G$ have at least $t$ vertices in common. This paper investigates the minimum number of colors, $\chi(t, c)$, sufficient to $c$-strong color any $t$-intersecting hypergraph. We show that when $t \le c-2$, no finite number of colors is sufficient. Conversely, for $t \ge c$, we use a probabilistic argument to show that a finite number of colors is sufficient, though a large gap remains between the best upper and lower bounds. The case $t = c-1$ remains an open question for $c > 2$.
Introduction
In the study of hypergraphs—mathematical structures where "edges" can contain any number of vertices—vertex coloring is a fundamental problem. Traditional coloring definitions usually fall into two categories:
- Weak Coloring: Requires that no edge is monochromatic (at least two colors per edge).
- Strong Coloring: Requires every vertex within a single edge to have a unique color.
This paper explores the middle ground: $c$-strong coloring. In a $c$-strong coloring, each edge $e$ must contain at least $\min\{c, |e|\}$ distinct colors. This definition provides a spectrum of constraints, where $c=2$ corresponds to weak coloring and $c$ approaching the size of the edges approaches strong coloring. The authors specifically examine these colorings within the context of $t$-intersecting hypergraphs, where every two edges share at least $t$ common vertices. The central question is: for fixed $c \ge 2$ and $t \ge 1$, what is the minimum number of colors $\chi(t, c)$ required to color any such hypergraph?
The Phase Transition of Colorability
A primary contribution of this research is identifying a "phase transition" in the finiteness of $\chi(t, c)$. The relationship between the intersection requirement $t$ and the coloring constraint $c$ determines whether a universal coloring bound exists.
The Uncolorable Regime ($t \le c - 2$)
The authors prove that if the intersection $t$ is too small relative to $c$, specifically $t \le c - 2$, then $\chi(t, c) = \infty$. This means that for any number of colors $k$, one can construct a $t$-intersecting hypergraph that cannot be $c$-strong colored with $k$ colors. This is established through combinatorial constructions and a monotonicity property: increasing both the intersection requirement and the color requirement necessarily increases the chromatic number.
The Colorable Regime ($t \ge c$)
In contrast, when $t \ge c$, the authors prove that a finite number of colors always suffices. Using the probabilistic method, they demonstrate that a valid coloring exists by showing that the probability of a random coloring failing to meet the $c$-strong criteria is strictly less than one.
The Frontier: $t = c - 1$
The case where $t = c - 1$ represents the boundary of current knowledge. While it is known that $\chi(1, 2) = 3$ (the weak coloring of 1-intersecting hypergraphs), it is currently unknown whether $\chi(2, 3)$ or any higher instance is finite. This remains the most significant open problem in this area.
Methodology
The research utilizes two distinct mathematical strategies:
- Combinatorial Constructions: To establish lower bounds and the infinite nature of $\chi(t, c)$ for small $t$, the authors build specific hypergraph families that force color conflicts.
- The Probabilistic Method: To derive upper bounds for $t \ge c$, the authors assign colors to vertices uniformly at random. They apply the Union Bound alongside results regarding the "$p$-biased measure" of intersecting families (drawing on work by Dinur, Safra, and Friedgut). This allows them to prove that a valid coloring exists by bounding the likelihood of a "bad" coloring.
Key Results and Bounds
The paper provides several specific bounds for $\chi(t, c)$:
- Infinite Bounds: $\chi(t, c) = \infty$ whenever $t \le c - 2$.
- Lower Bounds: For the colorable regime ($t \ge c$), the authors show $\chi(t, c) \ge 2(c - 1)$.
- Upper Bounds (Probabilistic):
- When $t = c$, the number of colors is at most $\sqrt{c} \cdot e^c$ (exponential in $c$).
- When $t = 2c$, the bound improves to $\chi(t, c) < 2c^2$ (polynomial in $c$).
- Weak Coloring Baseline ($c=2$): The authors provide a complete characterization: $\chi(0, 2) = \infty$, $\chi(1, 2) = 3$, and $\chi(t, 2) = 2$ for all $t \ge 2$.
Connection to Property Testing
Interestingly, this coloring problem arose from research into property testing of boolean functions. Specifically, it helps guarantee that when a domain is randomly partitioned, the union of a small number of parts will not accidentally contain a "bad" intersecting family. This ensures that certain local properties can be tested efficiently across the domain.
Conclusion and Future Work
While this paper establishes the fundamental boundaries of semi-strong coloring, significant gaps remain. The most immediate open problem is determining if $\chi(c-1, c)$ is finite for $c > 2$. Additionally, there is a large disparity between the linear lower bounds and the exponential/quadratic upper bounds. The authors suspect the lower bound $\chi(t, c) = 2(c - 1)$ might be the actual answer for $t \ge c$, but current probabilistic methods have yet to reach that level of tightness.
Summary updated