Grid designs

This paper investigates the existence of $G$-designs (decompositions of complete graphs into edge-disjoint copies of a grid graph $G$), proving that such designs exist for toroidal grids $C_n \square C_n$ when $n$ is an odd prime or its square, and for the path-grid $P_4 \square P_4$ (which relates to scrambling Connections puzzles), while showing that $P_3 \square P_3$ admits no such design.

The Gist

Imagine you have a giant box of 16 unique Scrabble tiles. Your goal is to arrange them into a 4x4 square grid. In this grid, every tile touches its neighbors (up, down, left, right).

Now, imagine you want to create a series of different grids. The rule is strict: Every single possible pair of tiles must sit next to each other exactly once across all your grids. No pair can be neighbors twice, and no pair can be left out.

This is the core puzzle the paper solves. It turns out, for a 4x4 grid of 16 items, you can do this perfectly with exactly five different arrangements.

Here is the breakdown of the paper's journey, translated from "math-speak" to "everyday speak."

1. The Inspiration: The "Connections" Puzzle

The authors were inspired by the popular New York Times game Connections. In that game, you see 16 words in a grid. You have to find four groups of four words that share a hidden theme.

• The Problem: The game sometimes "scrambles" the words to hide the answers. But the computer just shuffles them randomly.
• The Observation: If you shuffle the words randomly, you might need to hit the "Scramble" button 20 or 30 times before every possible pair of words has accidentally ended up next to each other.
• The Big Question: Is it possible to be so lucky (or so smart) that you only need four scrambles (plus the original grid = 5 total) to make sure every single pair of words has been neighbors exactly once?

The paper says: Yes, it is possible.

2. The Two Types of Grids

The authors looked at two ways to arrange these grids:

• The "Flat" Grid (Path-Graphs): Think of a standard piece of graph paper. The edges stop at the border. If you are in the top-left corner, you only have two neighbors.
• The "Donut" Grid (Torus/Cycle-Graphs): Imagine wrapping that graph paper into a cylinder, then connecting the ends to make a donut (a torus). Now, if you walk off the right edge, you pop up on the left. If you walk off the top, you pop up on the bottom. Everyone has four neighbors.

3. The Results: What Works and What Doesn't

The "Donut" Grids (The Easy Wins)

When the grid is shaped like a donut (where you can wrap around), the math works out beautifully for certain sizes.

• The Magic Number: If the grid size is based on an odd prime number (like 3, 5, 7, 11) or the square of an odd prime (like 9, 25), you can perfectly arrange the grid so every pair meets exactly once.
• The Secret Sauce: The authors used Finite Fields. Think of this as a special kind of math where numbers "wrap around" like a clock. Instead of 12 + 1 = 13, maybe 12 + 1 = 1. By using these special number systems, they could generate the perfect patterns mathematically without guessing.

The "Flat" Grids (The Tricky Ones)

When the grid is flat (like a normal piece of paper), it's much harder.

• The 3x3 Case (9 items): The authors proved this is impossible. No matter how you try, you cannot arrange 9 items in a 3x3 grid five times (or three times, depending on the math) so that every pair touches exactly once. It's like trying to fit a square peg in a round hole; the geometry just doesn't allow it.
• The 4x4 Case (16 items): This is the "Holy Grail" of the paper. They proved that for 16 items in a 4x4 flat grid, it is possible.
  • You need exactly 5 grids.
  • In the first grid, you have 24 pairs of neighbors.
  • In 5 grids, you have $24 \times 5 = 120$ neighbor slots.
  • The total number of unique pairs you can make with 16 items is also 120.
  • So, if you can fill those 5 grids perfectly, you have used every single pair exactly once.

4. How Did They Do It? (The "Magic" Method)

You might think they just used a computer to try billions of random shuffles until one worked.

• Actually: They used algebra.
• They treated the 16 words as numbers in a special "field" (a mathematical playground with 16 elements).
• They created a formula that acts like a recipe. If you follow the recipe, it tells you exactly where to place every word in the grid.
• The Cool Part: The solution has a rhythmic symmetry. If you take the first grid and apply a specific mathematical "twist" (multiplying by a specific number), you get the second grid. Do it again, you get the third. It's like a dance where the dancers rotate positions in a perfect, predictable pattern to ensure no one ever bumps into the same person twice.

5. Why Should You Care?

This isn't just about solving a puzzle game.

1. Efficiency: It proves that you can design systems (like communication networks or tournament schedules) where every participant interacts with every other participant exactly once, with zero wasted effort.
2. Mathematical Beauty: It shows that even in something as chaotic as "scrambling," there are hidden, perfect structures waiting to be found if you look at them through the lens of algebra.
3. The "Connections" Game: It confirms that the New York Times could theoretically program their game to cycle through exactly 5 perfect scrambles, guaranteeing that players see every possible connection between words without any repetition.

Summary Analogy

Imagine you are hosting a party with 16 guests. You want to seat them at a square table (4x4) for five different courses.

• The Rule: For every course, guests sit next to their neighbors.
• The Goal: By the end of the fifth course, every single guest must have sat next to every other guest exactly once.
• The Result: The paper says, "Yes, we can do this!" and provides the exact seating chart for all five courses. They also proved that if you only had 9 guests and a smaller table, it would be mathematically impossible to pull this off.

The authors used the "arithmetic of clocks" (finite fields) to write the perfect seating chart, turning a chaotic puzzle into a symphony of order.

Technical Summary

Here is a detailed technical summary of the paper "Scrambling Connections Puzzles with Finite Fields" by Danai et al.

1. Problem Definition

The paper investigates the existence of $G$-designs for specific grid graphs. A $G$-design is defined as a decomposition of the edge set of a complete graph $K_N$ into edge-disjoint subgraphs, all isomorphic to a specific graph $G$.

The authors focus on two types of grid graphs formed by the Cartesian product of path graphs ($P_n$) and cycle graphs ($C_n$):

• Torus Grids: $G = C_n \square C_n$ (vertices arranged on a torus).
• Ordinary Grids: $G = P_n \square P_n$ (vertices arranged on a standard planar grid).

The Core Question: For which values of $n$ can the complete graph $K_{n^2}$ be partitioned into disjoint copies of $C_n \square C_n$ or $P_n \square P_n$?

Motivation: The problem is motivated by the "Scramble" feature in the New York Times "Connections" puzzle. In a standard 4x4 grid of 16 words, there are 24 adjacent pairs. The total number of unique pairs among 16 words is $\binom{16}{2} = 120$. Since $120 = 5 \times 24$, the authors ask if it is possible to generate exactly 5 distinct grid arrangements (scrambles) such that every possible pair of words appears as neighbors exactly once across the 5 grids. This corresponds to partitioning$K_{16}$into 5 copies of$P_4 \square P_4$.

2. Methodology

The authors primarily utilize algebraic combinatorics, specifically the arithmetic of finite fields ($\mathbb{F}_q$), to construct these decompositions.

• Vertex Association: The vertices of the complete graph $K_{n^2}$ are identified with the elements of a finite field $\mathbb{F}_{n^2}$ (or $\mathbb{F}_{n^4}$ for the torus case).
• Edge Definition via Field Differences: Subgraphs are constructed by defining edges based on the difference between field elements. Two vertices $u$ and $v$ are connected if their difference $u - v$ belongs to a specific set of basis elements or their negatives.
• Basis Selection: The construction relies on selecting a basis for the field extension over its prime subfield. The authors partition the non-zero elements of the field into sets that correspond to the "steps" (edges) required to form the grid structure.
• Symmetry and Cyclic Groups: The proofs often exploit the cyclic symmetry of the multiplicative group of the finite field ($\mathbb{F}^*$), generated by a primitive element $x$.

3. Key Contributions and Results

A. Torus Grids ($C_n \square C_n$)

The authors prove that a decomposition exists when $n$ is an odd prime or the square of an odd prime.

• Theorem 1: If $p$ is an odd prime, $K_{p^2}$ can be partitioned into $(p^2 - 1)/4$ copies of $C_p \square C_p$.
  • Method: Vertices are elements of $\mathbb{F}_{p^2}$. Edges are formed by differences of $\pm \alpha$ and $\pm \beta$, where $\{\alpha, \beta\}$ is a basis for $\mathbb{F}_{p^2}$ over $\mathbb{F}_p$. The non-zero elements are partitioned into pairs $\{x^k, -x^k\}$ to generate the required subgraphs.
• Theorem 2: If $p$ is an odd prime, $K_{p^4}$ can be partitioned into $(p^4 - 1)/4$ copies of $C_{p^2} \square C_{p^2}$.
  • Method: Uses $\mathbb{F}_{p^4}$. The authors utilize a known result by Kotzig that $C_p \square C_p$ can be decomposed into Hamiltonian cycles. They construct a larger structure $C_p \square C_p \square C_p \square C_p$ and decompose it into four copies of $C_{p^2} \square C_{p^2}$.

B. Ordinary Grids ($P_n \square P_n$)

The results for planar grids are more nuanced, with both negative and positive results.

• Theorem 3 (Negative Result): $K_9$ cannot be partitioned into 3 copies of $P_3 \square P_3$.
  • Proof Strategy: A combinatorial argument based on vertex degrees. In $K_9$, every vertex has degree 8. In $P_3 \square P_3$, the center vertex has degree 4, while corner vertices have degree 2. The authors show that assigning the "center" of the three grids to specific vertices in $K_9$ leads to a contradiction regarding the adjacency requirements of the remaining vertices.
• Theorem 4 (Positive Result): $K_{16}$ can be partitioned into 5 copies of $P_4 \square P_4$.
  • Significance: This confirms the feasibility of the "Connections" puzzle scrambling goal.
  • Method: Uses the field $\mathbb{F}_{16} \cong \mathbb{F}_2[x]/(x^4+x+1)$. The authors define a mapping from field elements to the $4 \times 4$grid based on a specific basis${\alpha, \beta, \gamma, \delta}$. They construct 5 specific subgraphs$G_i$using powers of a generator$x$.
  • Verification: They prove that the differences between adjacent elements in these grids cover every non-zero element of $\mathbb{F}_{16}$ exactly once, ensuring no repeated pairs and full coverage.

4. Significance and Implications

1. Resolution of a Practical Puzzle: The paper provides a mathematical proof that the "perfect scramble" for a 4x4 Connections puzzle is possible. It validates that one can generate 5 distinct grids where every pair of words is adjacent exactly once, solving a problem that previously relied on computer search (Ed Kirkby's 2023 finding).
2. Extension of Classical Problems: The work extends the classical problème de ronde (round table problem) and problème de banc (bench problem) solved by Lucas and Walecki. While those problems dealt with decomposing graphs into paths or cycles, this paper addresses decompositions into Cartesian products of paths and cycles.
3. New Algebraic Constructions: The paper introduces novel algebraic constructions for graph decompositions using finite fields, specifically handling the asymmetry of path graphs ($P_n$) compared to the symmetry of cycle graphs ($C_n$).
4. Open Problems: The authors identify unresolved cases, such as $C_{15} \square C_{15}$ and $P_7 \square P_7$, and suggest future directions involving higher-dimensional grids ($C_n \square C_n \square \dots$) and mixed products ($C_m \square P_n$).

Summary Conclusion

The paper successfully bridges recreational mathematics (puzzle design) and deep combinatorial theory. By leveraging finite field arithmetic, the authors prove the existence of $G$-designs for toroidal grids of prime power order and resolve the specific case of the 4x4 planar grid, while proving the impossibility for the 3x3 case. This establishes a rigorous theoretical foundation for "perfect" scrambling algorithms in grid-based puzzles.