Local rainbow colorings

Noga Alon, Ido Ben‐EliezerJournal of Combinatorics 2011 · DOI

Abstract

Given a graph $H$, we denote by $C(n, H)$ the minimum number $k$ such that the following holds: there are $n$ colorings of $E(K_n)$ with $k$ colors, each associated with one of the vertices of $K_n$, such that for every copy $T$ of $H$ in $K_n$, at least one of the colorings associated with $V(T)$ assigns distinct colors to all the edges of $E(T)$. This paper investigates the behavior of $C(n, H)$ as $n$ grows, characterizing which graphs $H$ allow for constant colorings and providing new bounds for those that require growth.

Introduction

In extremal graph theory, a "rainbow" subgraph is one where every edge is assigned a unique color. While traditional research focuses on finding rainbow subgraphs within a single global coloring of a large graph, this paper shifts the perspective to a "local" version. This model is motivated by computational complexity theory, specifically the study of Span Programs—a linear algebraic model used to analyze Boolean functions.

The central challenge is determining the growth rate of $C(n, H)$. Does the number of colors needed stay constant regardless of the total number of vertices $n$, or must it scale to satisfy the rainbow condition for every possible copy of $H$?

The Problem: Local vs. Global Colorings

The authors define $C(n, H)$ as the minimum number of colors $k$ needed such that each of the $n$ vertices in a complete graph $K_n$ can be assigned its own coloring function. The requirement is strict: for every copy of a fixed graph $H$ appearing in $K_n$, there must be at least one vertex within that specific copy whose coloring function renders $H$ a rainbow. This local constraint is significantly more restrictive than global coloring requirements and directly relates to the "Fusion Method" used to prove lower bounds on the size of Span Programs.

Methodology

The research employs a diverse set of combinatorial and probabilistic tools to establish bounds:

  • Structural Graph Theory: The authors introduce the concept of being "2-locally large." A graph is 2-locally large if there exists a specific ordering of its vertices where every vertex is incident to or near at least two edges that exhibit certain symmetries. This property is key to identifying which graphs require non-constant colorings.
  • Probabilistic Method: To establish upper bounds (demonstrating that a small number of colors suffices), the authors use the Lovász Local Lemma. This allows them to prove the existence of a valid set of colorings by showing that the probability of failing the rainbow condition is strictly less than one.
  • Hypergraph Ramsey Theory: For lower bounds, the authors utilize the Erdős-Rado Theorem for 3-uniform hypergraphs. This helps identify monochromatic subsets that inevitably force color collisions.
  • Pigeonhole Principle: This classical tool is used extensively to derive lower bounds for specific structures like paths ($P_3$) and stars ($S_t$).

Key Insights and Results

The Threshold of Complexity

The most significant contribution is the characterization of "easy" versus "hard" graphs. The authors prove that $C(n, H)$ is bounded by a constant (specifically, at most 5) if and only if $H$ is small (at most 3 edges) and is not the path $P_3$.

The $P_3$ Anomaly

The path with 3 edges ($P_3$) serves as a critical threshold. It is the smallest graph that requires the number of colors to grow with $n$. The authors significantly improved the previous lower bound for $P_3$, showing: $$C(n, P_3) = \Omega\left(\left(\frac{\log n}{\log \log n}\right)^{1/4}\right)$$

General and Polynomial Growth

  • General Upper Bound: For any fixed graph $H$ with $r$ vertices, $C(n, H) = O(n^{\frac{r-2}{r}})$, indicating that the color requirement is always sublinear.
  • Polynomial Growth: For any graph $H$ with at least 13 edges, $C(n, H)$ must grow polynomially with $n$ (i.e., $C(n, H) = \Omega(n^b)$ for some constant $b > 0$).

Conclusion and Future Work

While this paper advances our understanding of local rainbow colorings, several open questions remain. A significant gap persists between the lower bound ($≈ \log^{1/4} n$) and the upper bound ($≈ \sqrt{n}$) for the path $P_3$. Closing this gap is essential for refining the mathematical model.

Furthermore, the authors suggest investigating the $n^{1-\epsilon}$ Conjecture: determining if, for any $\epsilon > 0$, there exists a large enough clique $K_r$ such that $C(n, K_r) \ge n^{1-\epsilon}$. Such a result would imply that for highly complex subgraphs, the number of colors required is nearly proportional to the number of vertices in the graph. While these improvements do not yet yield new lower bounds for Span Programs, they provide the necessary combinatorial foundation for future breakthroughs in circuit complexity.

Summary updated

Abstract

Given a graph H, we denote by C(n, H) the minimum number k such that the following holds. There are n colorings of E(K n ) with k-colors, each associated with one of the vertices of K n , such that for every copy T of H in K n , at least one of the colorings that are associated with V (T ) assigns distinct colors to all the edges of E(T ).
BibTeX
@article{alon2011local,
  author = {Noga Alon and Ido Ben‐Eliezer},
  title = {{Local rainbow colorings}},
  journal = {Journal of Combinatorics},
  year = {2011},
  doi = {10.4310/joc.2011.v2.n2.a6},
}
Figure