Rainbow connectivity Maker-Breaker game

This paper investigates biased Maker-Breaker games on systems of graphs where Maker aims to construct rainbow structures, specifically determining the threshold bias for rainbow connectivity and diameter games on complete graphs while disproving a conjecture by Balogh, Martin, and Pluhár.

The Gist

Here is an explanation of the paper "Rainbow Connectivity Maker-Breaker Game," translated into simple, everyday language with creative analogies.

The Big Picture: A Game of Colored Bridges

Imagine a city with $n$ intersections (vertices). In this city, there isn't just one road connecting two intersections; there are $s$ different layers of roads.

• Layer 1 is painted Red.
• Layer 2 is painted Blue.
• Layer 3 is painted Green, and so on.

Between any two intersections, there is a Red road, a Blue road, a Green road, etc.

Now, imagine two players, Maker and Breaker, playing a game to build a transportation network in this city. They take turns claiming these roads.

• Maker wants to build a network where you can travel between any two intersections using a "Rainbow Path." A Rainbow Path is a route where you never use the same color twice. (e.g., Red $\to$ Blue $\to$ Green).
• Breaker wants to stop Maker. He tries to claim roads so that Maker can never find a complete Rainbow Path between some pair of intersections.

The question the paper answers is: How much of an advantage does Breaker need to win?
If Maker gets 1 road per turn, how many roads ($b$) can Breaker grab per turn before he is guaranteed to win? This number is called the "Threshold Bias."

---

The Three Main Scenarios

The researchers found that the answer changes dramatically depending on how many colors (layers) of roads exist.

1. The "Small Number of Colors" Scenario (The Surprising Twist)

The Setup: Imagine there are only a few colors, say 3, 4, or 5 layers ($s$ is small).
The Intuition: Usually, in math games, if you play randomly, you get a result similar to playing perfectly. This is called the "Random Graph Intuition." You'd expect that if Breaker grabs enough roads to make the city look "sparse" (like a random graph), he wins.
The Reality: The paper proves that intuition fails here.

• If there are 2 colors, Breaker only needs to grab 2 roads for every 1 of Maker's to win.
• If there are 3 or more colors, the number Breaker needs to grab grows, but it grows much slower than the random intuition suggests.
• The Analogy: Imagine trying to build a bridge across a river using only Red and Blue planks. If the opponent is allowed to steal 2 planks for every 1 you place, they can easily block you. But if there are 100 colors, you might think the opponent needs to steal 100 planks to stop you. Surprisingly, they only need to steal about $\sqrt{100} = 10$ planks! The "Rainbow" requirement is actually harder to satisfy than it looks, making it easier for the blocker.

2. The "Huge Number of Colors" Scenario (The Intuition Holds)

The Setup: Now imagine there are thousands of colors ($s$ is very large, larger than $\log n$).
The Reality: Here, the "Random Graph Intuition" works perfectly.

• If Breaker grabs enough roads to make the city look like a random, sparse map, he wins.
• The Analogy: If you have a million different colors of planks, it's very hard for Breaker to block every possible color combination. The game behaves exactly as you would guess if you just threw darts at the board randomly. The threshold is roughly proportional to the number of colors divided by the logarithm of the city size.

3. The "Rainbow Tree" Scenario

The Setup: Instead of just connecting two points, Maker wants to build a Rainbow Spanning Tree. This is a network that connects every intersection in the city, using exactly one road of each color, with no loops.
The Reality: This is a much harder game for Maker. The threshold bias is huge (proportional to $n^2$).

• The Analogy: Building a single rainbow path is like finding a specific key in a haystack. Building a rainbow tree is like building a house where every single brick must be a different color, and you can't repeat a color. Breaker has a massive advantage here. The paper proves that Breaker needs to grab roughly $n^2 / \log(n)$ roads to stop Maker.

---

The "Diameter" Side Quest

The paper also solves a related puzzle called the Diameter Game.

• The Goal: Maker doesn't care about colors. She just wants to ensure that the distance between any two points is short (at most $s$ steps).
• The Result: The authors realized their strategy for the "Rainbow Game" could be adapted to solve this. They proved that the difficulty of keeping the city "compact" (short distances) is mathematically identical to the difficulty of building a rainbow path when there are few colors.
• Why it matters: This disproved a previous guess by other mathematicians who thought the "short distance" game was much easier to win for Maker. The authors showed it's actually quite hard.

---

How They Did It (The Secret Sauce)

The authors didn't just guess; they built a complex strategy for Maker that combines three different "mini-games" played simultaneously:

1. The "Box" Game: Maker treats groups of roads like boxes. She tries to grab a few roads from every box to ensure she has options everywhere.
2. The "Balancing" Game: She uses a strategy to keep her "outgoing" roads balanced. If Breaker blocks her on the left, she ensures she has plenty of roads on the right.
3. The "Spooky" Game: This is the cleverest part. The researchers imagined a third player, a "Ghost," who can change the rules mid-game. If Maker needs a road between two specific neighborhoods, but those neighborhoods didn't exist at the start of the game, the "Ghost" creates them. Maker has a strategy to win even if the board keeps changing shape.

By mixing these strategies with some heavy math (probability and random graphs), they proved exactly how many roads Breaker needs to steal to win in every scenario.

The Takeaway

This paper is a victory for strategic thinking over intuition.

• When there are few colors, the "Rainbow" rule is a trap that makes the game much harder for the builder than it seems.
• When there are many colors, the game behaves predictably like a random shuffle.
• The authors also fixed a long-standing error in the math community regarding how hard it is to keep a city's travel times short.

In short: Rainbow paths are tricky, and sometimes the blocker has a bigger advantage than you'd expect!

Technical Summary

Here is a detailed technical summary of the paper "Rainbow connectivity Maker-Breaker game" by Barkey et al.

1. Problem Statement

The paper investigates biased Maker-Breaker games played on systems of graphs. Specifically, it focuses on two variations where the board consists of $s$ copies of the complete graph $K_n$ (denoted as a system $\mathcal{G} = \{G_1, \dots, G_s\}$), where each copy represents a distinct "color."

The core objective for Maker is to claim edges such that the resulting subgraph contains specific rainbow structures:

1. Rainbow-Connectivity Game ($C_{s,n}$): Maker wins if she claims a rainbow path between every pair of vertices. A path is rainbow if it contains at most one edge from each graph $G_i$ (i.e., edges have distinct colors).
2. Rainbow-Spanning-Tree Game ($RS_n$): Maker wins if she claims a rainbow spanning tree (a spanning tree with exactly one edge from each of the $n-1$ available layers/colors).

The paper aims to determine the threshold bias $b_{game}$, which is the critical integer $b$ such that Breaker wins the $(1:b)$ game if $b \ge b_{game}$, and Maker wins if $b < b_{game}$. A central theme is testing the "Random Graph Intuition" (or Erdős paradigm), which posits that the threshold bias for a positional game often matches the threshold probability $p$ for the corresponding random graph property, scaled by the number of edges claimed per round.

2. Methodology

The authors employ a sophisticated combination of positional game theory, probabilistic methods, and combinatorial constructions.

• Strategic Frameworks:

  • Box Games & MinBox: Used to ensure Maker claims a sufficient fraction of edges in specific subsets (e.g., ensuring minimum degree conditions).
  • Spooky Balancing Games (SBG): A generalization of Box games where winning sets can grow dynamically during the game. This is crucial for Maker's strategy to handle the emergence of new neighborhoods and connections as the game progresses.
  • Beck's Criterion: Used to prove Breaker's winning strategies by showing that the sum of $(1+q)^{-|F|/p}$ over all winning sets is less than 1.

• Maker's Strategy (The "Hybrid" Approach):
  For the lower bounds (Maker winning), the authors design a complex strategy that runs three subgames in parallel:

  1. Minimum Degree Game: Ensures Maker builds a graph with high expansion properties (using a strategy similar to Krivelevich's).
  2. Random Graph Generation: Maker simulates the construction of random graphs ($G_{n,p}$) within her claimed edges to ensure connectivity properties hold asymptotically almost surely (a.a.s.).
  3. Balancing Game: Ensures Maker claims a balanced fraction of edges between specific expanding sets of vertices, preventing Breaker from isolating components.
  • Key Innovation: The strategy involves "exposing" edges (imagining them as part of a random graph) and claiming them if they are free, effectively combining deterministic game play with probabilistic analysis.

• Breaker's Strategy:
  Breaker's strategies often involve isolating vertices or preventing the formation of short paths between specific pairs of vertices by claiming edges incident to specific sets (cliques or neighborhoods) faster than Maker can expand.

3. Key Contributions and Results

A. Rainbow-Connectivity Game ($C_{s,n}$)

The paper establishes that the behavior of the threshold bias depends heavily on the number of colors $s$.

• Case $s=2$:

  • Result: The threshold bias is exactly $b = 2$.
  • Significance: This contradicts the random graph intuition. For random graphs, connectivity requires $p \approx \frac{\log n}{n}$, suggesting a bias of order $\frac{n}{\log n}$. However, with only 2 colors, Maker can win with a constant bias.

• Case $3 \le s = O(1)$(Constant$s$):

  • Result: The threshold bias is of order $n^{1 - 1/\lceil s/2 \rceil}$.
  • Detail:
    • If $b \ge C n^{1 - 1/\lceil s/2 \rceil}$, Breaker wins.
    • If $b \le \gamma n^{1 - 1/\lceil s/2 \rceil}$, Maker wins and constructs $\beta n^{s-1} b^{-s}$ rainbow paths between any pair.
  • Significance: The random graph intuition fails here. The random graph threshold for rainbow connectivity is $p \approx n^{-(s-1)/s}$, which would imply a bias of $n^{(s-1)/s}$. The actual game threshold is significantly lower (Maker wins with much higher bias) because Maker can strategically target specific path lengths rather than relying on random connectivity.

• Case $s = \omega(\log n)$ (Large $s$):

  • Result: The threshold bias is $\Theta\left(\frac{sn}{\log n}\right)$.
  • Detail: Specifically, $(\frac{1}{2} - o(1))\frac{sn}{\log n} \le b_{C_{s,n}} \le (1+o(1))\frac{sn}{\log n}$.
  • Significance: In this regime, the random graph intuition holds (up to a constant factor). The threshold matches the random graph prediction.

B. Rainbow-Spanning-Tree Game ($RS_n$)

• Result: The threshold bias satisfies:
  $$\left(\frac{\log 2}{8} - o(1)\right) \frac{n^2}{\log n} \le b_{RS_n} \le (1 + o(1)) \frac{n^2}{\log n}$$
• Significance: This confirms the random graph intuition for the spanning tree variant, as the random graph threshold for a rainbow spanning tree is also of order $\frac{n^2}{\log n}$.

C. Diameter Game ($D_{s,n}$)

The paper addresses the Diameter Game, where Maker wins if she creates a spanning subgraph with diameter at most $s$.

• Result: The threshold bias is $b_{D_{s,n}} = \Theta(n^{1 - 1/\lceil s/2 \rceil})$.
• Significance: This disproves Conjecture 9 by Balogh, Martin, and Pluhár, which suggested the threshold was closer to the Breaker side bound ($n^{1 - 1/(s-1)}$). The authors show the threshold is actually determined by the Maker side bound derived from the rainbow connectivity analysis.

4. Significance and Implications

1. Refutation of Universal Intuition: The paper demonstrates that the "Random Graph Intuition" is not universal for rainbow games. It holds when the number of colors is large ($s = \omega(\log n)$) but fails dramatically for small constant $s$, where the threshold bias is polynomially smaller than the random graph prediction.
2. Methodological Advancement: The introduction and application of Spooky Balancing Games allow for the analysis of games where the winning sets (neighborhoods) evolve dynamically. This technique is likely to be applicable to other positional games on dynamic structures.
3. Resolution of Open Problems:
   • It settles the threshold bias for the rainbow-connectivity game for constant $s$ and large $s$.
   • It resolves the gap in the diameter game bounds, correcting a previous conjecture.
   • It provides tight bounds (up to constant factors) for the rainbow spanning tree game.
4. Optimality: The authors prove that the number of rainbow paths Maker can guarantee is optimal up to constant factors, using potential function arguments.

5. Open Problems

The authors conclude by posing several open problems:

• Determining the exact threshold for the range $\sqrt{\log n} \ll s \ll \log n$, where current estimates fail.
• Proving the conjectured exact constants for the threshold biases in the large $s$ regime (e.g., $b_{C_{s,n}} \sim \frac{sn}{\log n}$).
• Investigating other rainbow structures, such as Rainbow Perfect Matchings and Rainbow Hamilton Cycles, for which they conjecture thresholds of $\Theta(\frac{n^2}{\log n})$.

In summary, this paper provides a comprehensive analysis of rainbow Maker-Breaker games, revealing a phase transition in the validity of the random graph intuition based on the number of available colors, and introducing powerful new game-theoretic tools to handle dynamic winning sets.