Thresholds for colouring the random Borsuk graph

This paper establishes that the chromatic number of the random Borsuk graph transitions from being $k$-colourable to requiring more than $k$ colours when the average degree is constant for $2 \leq k \leq d$, and further identifies sharp thresholds for these transitions, particularly characterizing the$k=2$ case via continuum AB percolation.

The Gist

Imagine you are hosting a massive party on the surface of a giant, perfect sphere (like a beach ball). You invite $n$ guests, and they all pick their spots on the ball completely at random.

Now, here is the rule for making friends: Two guests become friends (an "edge" in graph theory) if they are standing almost exactly opposite each other.

In math terms, if the distance between them is very close to the maximum possible distance (halfway around the sphere), they get an edge. The parameter $\alpha$ controls how "close to opposite" they need to be. A small $\alpha$ means they must be extremely close to being perfect opposites to be friends. A larger $\alpha$ means they can be a bit further apart and still be friends.

The big question the paper asks is: How many colors do we need to paint the guests so that no two friends have the same color?

In graph theory, this is called the Chromatic Number. If you need 3 colors, it means you can't just paint everyone Red or Blue; you need a third color because the "friendship" pattern is too tangled to be split into just two groups.

Here is what the authors discovered, explained through simple analogies:

1. The "Thermodynamic" Sweet Spot

Usually, when you add edges to a random network, things change slowly. But this paper found a specific "sweet spot" where the behavior changes dramatically.

Imagine you are slowly turning up the volume on a radio.

• Low Volume (Small $\alpha$): The guests are very picky. Only perfect opposites are friends. The graph is sparse. You can easily color everyone with just a few colors.
• The Threshold: The authors found that there is a specific volume level (a specific value of $\alpha$) where the graph suddenly becomes impossible to color with $k$ colors.
• The Surprise: For most colors ($k$ from 2 up to $d$), this dramatic switch happens when the average number of friends per person is just a constant number (like 5 or 10 friends). It doesn't need to be a huge number of friends; just a few is enough to create a chaotic mess that requires more colors.

2. The "Odd Cycle" Problem (The 2-Color Limit)

Let's look at the simplest case: Can we color everyone with just 2 colors (Red and Blue)?

• The Rule: You can do this if and only if there are no "odd cycles." An odd cycle is a chain of friends where Person A is friends with B, B with C, and C is friends with A. If you try to color this Red-Blue-Red, Person C ends up needing to be Blue (because of A) but also Red (because of B). It's a contradiction.
• The Discovery: The authors proved that the moment the graph stops being 2-colorable is exactly when the "friendship network" starts forming these odd loops.
• The Metaphor: They compared this to a model called Continuum AB Percolation. Imagine two types of people, A and B, scattered on a floor. They only shake hands if they are close.
  • If the density of people is low, the handshakes form small, isolated islands. No odd cycles.
  • If the density crosses a critical line, a giant "infinite" cluster of handshakes forms. This giant cluster inevitably contains an odd loop.
  • The paper calculates the exact "density" (the value of $\alpha$) where this giant cluster forms. It's like finding the exact moment a puddle of water turns into a flood.

3. The "Almost All" Result (The 3 to $d+1$ Colors)

What about needing 3, 4, or more colors?

• The authors couldn't prove the exact "switch point" for every single number of guests ($n$).
• The Analogy: Imagine trying to predict the exact second a sandcastle will collapse as the tide comes in. It might collapse at 2:00:01 PM on Tuesday, but 2:00:03 PM on Wednesday.
• The Result: They proved that for almost all numbers of guests (99.9% of the time), there is a sharp, precise switch. If you add just a tiny bit more "friendship radius" ($\alpha$), the number of colors needed jumps up.
• They suspect this is true for every number of guests, but proving it for the rare "jumpy" cases is still a mystery.

4. The "High-Dimensional" Twist

The paper deals with spheres in $d$ dimensions (3D, 4D, 5D, etc.).

• The Intuition: As you add more dimensions, the sphere gets "emptier" in a way. It's harder for points to be close to each other.
• The Finding: Even in these high-dimensional spaces, the rule holds: You only need a constant average number of friends to force the graph to become complex enough to require more colors.

Summary of the "Big Picture"

Think of the random Borsuk graph as a social network of opposites.

1. Low Connectivity: Everyone is isolated or has a few friends. The network is simple and easy to organize (few colors).
2. The Critical Point: There is a precise moment where the network suddenly becomes "tangled."
   • For 2 colors, this happens when the network forms a giant, connected web (like a flood).
   • For more colors, this happens when the network becomes dense enough to force complex loops.
3. The Takeaway: You don't need a massive crowd of friends to make a social network chaotic. Just a few connections per person, in the right geometric arrangement, is enough to make the whole system explode in complexity.

The authors essentially mapped out the "tipping points" for this chaos, showing us exactly how much "friendship radius" is needed to break the system's ability to be simply organized.

Technical Summary

Here is a detailed technical summary of the paper "Thresholds for colouring the random Borsuk graph" by Acitores Montero, Irlbeck, Müller, and Stehlík.

1. Problem Statement and Context

The Object of Study:
The paper investigates the chromatic number ($\chi$) of the random Borsuk graph, denoted as $G(n, \alpha)$.

• Construction: The graph is formed by sampling $n$ points $X_1, \dots, X_n$ independently and uniformly at random on the $d$-dimensional unit sphere $S^d$.
• Edges: Two vertices $X_i$ and $X_j$ are connected by an edge if their geodesic distance satisfies $\text{dist}(X_i, X_j) > \pi - \alpha$.
• Parameter: $\alpha = \alpha(n)$ is a parameter that typically tends to 0 as $n \to \infty$. This condition implies that edges connect points that are "nearly antipodal."

Background:

• Deterministic Case: Erdős and Hajnal (1967) showed that for the deterministic Borsuk graph, if $\alpha$ is sufficiently small, the chromatic number is exactly $d+2$.
• Previous Random Results: Kahle and Martinez-Figueroa (2020) established that the transition from being $(d+1)$-colorable to requiring $\ge d+2$ colors occurs when the average degree is of logarithmic order, specifically when $\alpha \sim (\ln n / n)^{1/d}$.

The Research Gap:
The authors aim to determine the thresholds for $k$-colorability for all $2 \le k \le d+1$. Specifically, they investigate whether the transition from$k$-colorable to requiring$>k$colors occurs in the **"thermodynamic regime"** (where the average degree is constant, i.e.,$\alpha \sim n^{-1/d}$), which is a much denser regime than the logarithmic one found for the$d+2$ threshold.

---

2. Methodology and Techniques

The paper employs a diverse toolkit from probability theory, geometric combinatorics, and percolation theory.

A. Geometric Projections and Embeddings

• Stereographic Projection: The authors frequently map the sphere $S^d$ to $\mathbb{R}^d$ using stereographic projection to simplify geometric arguments. They establish precise bounds relating the geodesic distance on the sphere to the Euclidean distance in the projected space.
• Constructing Subgraphs (Theorem 1): To prove that $\chi > d$ in the thermodynamic regime, the authors construct a specific subgraph that behaves like a Borsuk graph in dimension $d-1$.
  • They define a function $h: S^{d-1} \to \mathbb{R}$ that is odd and Lipschitz.
  • They iteratively perturb this function to avoid "bad patches" (regions on the sphere devoid of random points) while maintaining the property that the image stays close to the equator.
  • This allows them to embed a $(d-1)$-dimensional Borsuk graph structure into the random graph, leveraging the Lyusternik-Shnirelmann theorem to force a high chromatic number.

B. Continuum AB Percolation (Theorem 2)

For the case $k=2$ (bipartiteness), the paper draws a deep connection to Continuum AB Percolation.

• The Model: Two independent Poisson point processes, $Z_A$ and $Z_B$, with intensities $\lambda_A$ and $\lambda_B$ on $\mathbb{R}^d$. An edge exists between $x \in Z_A$ and $y \in Z_B$ if $\|x-y\| \le 1$.
• Local Approximation: The authors show that locally, the random Borsuk graph in the thermodynamic regime converges to this AB percolation model.
• Critical Threshold: The threshold for 2-colorability corresponds to the critical intensity $\lambda_c$ of the AB percolation model.
  • If the intensity is below $\lambda_c$, clusters are finite, and the graph is bipartite (no odd cycles).
  • If above $\lambda_c$, an infinite cluster exists, implying the existence of odd cycles (and thus $\chi \ge 3$).
• Sprinkling Technique: To prove the existence of odd cycles in the supercritical regime, they adapt the "sprinkling" technique (Grimmett and Marstrand) to patch local percolation events into a global odd cycle.

C. Sharp Thresholds and Boolean Functions (Theorem 4)

For $k \in \{3, \dots, d+1\}$, the authors utilize results on sharp thresholds for Boolean functions (specifically a result by Müller [33] based on Bourgain's work).

• Poissonization: They switch from a fixed number of points $n$ to a Poisson point process with mean $\mu = n$.
• Discretization: The sphere is discretized into small cells. The event "$\chi > k$" is approximated by an increasing event on a set of independent Bernoulli variables.
• Density Argument: They prove that the threshold function $\alpha_k(n)$ cannot "jump" too wildly. By showing that the set of $n$ where the threshold behaves irregularly has density zero, they establish a sharp threshold for "almost all $n$."

D. Method of Moments (Theorem 3)

For the transition from 1-colorable (no edges) to 2-colorable, they use the method of moments to show that the number of edges converges to a Poisson distribution, yielding a coarse threshold.

---

3. Key Results

The paper establishes four main theorems characterizing the chromatic number transitions:

Theorem 1 (Threshold for $\chi > d$):
There exists a constant $c(d) > 0$ such that if $\alpha \ge c \cdot n^{-1/d}$, then $\chi(G(n, \alpha)) \ge d+1$ with high probability.

• Significance: This shows the transition to needing $d+1$ colors happens in the thermodynamic regime (constant average degree), much earlier than the logarithmic regime required for $d+2$ colors.

Theorem 2 (Sharp Threshold for $\chi > 2$):
There exists a constant $c_2(d) > 0$ such that:

• If $\alpha \le (c_2 - \epsilon)n^{-1/d}$, then $\chi(G(n, \alpha)) \le 2$ (bipartite) w.h.p.
• If $\alpha \ge (c_2 + \epsilon)n^{-1/d}$, then $\chi(G(n, \alpha)) \ge 3$ w.h.p.
• Significance: This is a sharp threshold. The constant $c_2$ is explicitly related to the critical intensity of continuum AB percolation on $\mathbb{R}^d$.

Theorem 3 (Threshold for $\chi > 1$):
The transition from having no edges to having edges (and thus $\chi \ge 2$) occurs when $n^2 \alpha^d$ is constant. This is a coarse threshold (probability transitions from 0 to 1 over a wider range of $\alpha$).

Theorem 4 (Sharp Thresholds for $3 \le k \le d+1$):
For each $k \in \{3, \dots, d+1\}$, there exists a sequence $\alpha_k(n)$ such that the property $\chi(G(n, \alpha)) > k$ has a sharp threshold for almost all $n$ (a set of density 1).

• Specifically, for almost all $n$, if $\alpha > (1+\epsilon)\alpha_k(n)$, $\chi > k$ w.h.p., and if $\alpha < (1-\epsilon)\alpha_k(n)$, $\chi \le k$ w.h.p.

---

4. Significance and Open Problems

Significance:

1. Regime Identification: The paper fundamentally shifts the understanding of random Borsuk graphs by showing that the "hard" coloring constraints (requiring $d+1$ colors) appear at constant average degrees, not just logarithmic ones.
2. Percolation Connection: It provides a novel and rigorous link between the chromatic number of geometric graphs on spheres and continuum percolation theory (specifically AB percolation).
3. Sharpness: It resolves the nature of the thresholds for $k=2$ (proving sharpness) and provides strong evidence for sharpness for all $k$, moving beyond the semi-sharp thresholds known for the $d+2$ case.

Conjectures and Open Problems:
The authors propose the following conjectures:

• Conjecture 55: The "almost all $n$" condition in Theorem 4 is unnecessary; the threshold is sharp for all large $n$.
• Conjecture 57: For each $3 \le k \le d$, there exists a constant$c_k$such that the threshold is of the form$c_k \cdot n^{-1/d}$, with$c_2 < c_3 < \dots < c_d$.
• Topological Conjecture (58): The hitting time for the chromatic number to exceed $k$ coincides with the hitting time for the graph to contain a subgraph whose neighborhood complex is homotopy equivalent to $S^{k-1}$. This generalizes the fact that $\chi \ge 3$ is equivalent to the existence of an odd cycle (homotopy equivalent to $S^1$).

In summary, this paper provides a comprehensive analysis of the chromatic number of random Borsuk graphs, utilizing advanced geometric constructions and percolation theory to pinpoint the exact regimes where colorability transitions occur.