Grid designs
Alon Danai, Joshua Kou, Andy Latto, Haran Mouli, James Propp · 2026
Read Grid designs by Alon Danai, Joshua Kou, Andy Latto, Haran Mouli, James Propp (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-00165.txt.
Introduction
Alon Danai works with Joshua Kou, Andy Latto, Haran Mouli, and James Propp on a tiling style puzzle in graph theory. Take a grid graph built from paths or cycles. Can the edges of a complete graph split into exact copies of that grid? Each copy must be disjoint from the others. When the answer is yes, a grid design exists.
For a torus grid with prime or prime squared size, the answer is yes. The path grid case is less even. The three by three path grid admits no design. The four by four path grid does admit one. That last case links to the Connections word game. It scrambles the puzzle so each word pair sits adjacent exactly once. The constructions use arithmetic in finite fields. A party puzzle and pure design theory turn out to meet.
Catalog record
| CREATOR | Alon Danai, Joshua Kou, Andy Latto, Haran Mouli, James Propp |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 21 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-00165
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Grid designs Alon Danai, Joshua Kou, Andy Latto, Haran Mouli, James Propp Abstract Abstract: We define a grid graph as a Cartesian product of path-graphs P_{n} or cycle-graphs C_{n} , and define a grid design as a G -design where the graph G is a grid graph, that is, a decomposition of a complete graph into edge-disjoint subgraphs isomorphic to G . We show that when n is an odd prime or the square of an odd prime, the toroidal grid-graph G=C_{n}\square C_{n} admits a G -design. In the less symmetrical case of products of path-graphs, we prove that G=P_{3}\square P_{3} does not admit a G -design but that G=P_{4}\square P_{4} does. This last result is the special case that motivated the present paper: a P_{4}\square P_{4} -design corresponds to a way of successively scrambling a Connections puzzle so that each pair of words occurs adjacently exactly once. Our constructions use the arithmetic of finite fields. 1 Introduction A G -design is a decomposition of a complete graph into edge-disjoint subgraphs isomorphic to G . Let C_{n} denote the cycle graph on n vertices 0,…, n-1 and P_{n} denote the path graph on n vertices 1,…, n . The problem of constructing a C_{n} -design when n is odd goes back to the problème de ronde proposed by Lucas and solved by Walecki, [ 2 ] and Walecki’s construction essentially solves the closely related problem of constructing a P_{n} -design when n is even. In contrast, we are not aware of work on G -designs when G is of the form C_{n}\square C_{n} or P_{n}\square P_{n} . Here as usual G\square G^{\prime} denotes the Cartesian product of the graphs G=(V,E) and G^{\prime}=(V^{\prime},E^{\prime}) whose vertices are of the form (v,v^{\prime}) with v\in V and v^{\prime}\in V^{\prime} and whose edges are of the form \{(v,v^{\prime}),(w,w^{\prime})\} either with \{v,w\}\in E and v^{\prime}=w^{\prime} or with v=w and \{v^{\prime},w^{\prime}\}\in E^{\prime} . As a motivating example, consider the sample Connections puzzle (too easy to be typical of the genre but illustrative of the core idea) shown in Figure 1 . \begin{array}[]{|c|c|c|c|}\hline\cr\text{OVER}&\text{\!MOUTH\!}&\text{\>HAND\>}&\text{NOSE}\\[4.30554pt] \hline\cr\text{HORSE}&\text{SPITE}&\text{MILK}&\text{BITE}\\[4.30554pt] \hline\cr\text{FEEDS}&\text{CRY}&\text{GIFT}&\text{CUT}\\[4.30554pt] \hline\cr\text{LOOK}&\text{FACE}&\text{YOU}&\text{\>SPILT\>}\\[4.30554pt] \hline\cr\end{array} Figure 1: A sample Connections puzzle. Solving the puzzle involves noticing that the sixteen words can be partitioned into four groups, each of which comes from a different English proverb indicating things you shouldn’t do: BITE the HAND that FEEDS YOU, LOOK a GIFT HORSE in the MOUTH, CUT off your NOSE to SPITE your FACE, or CRY OVER SPILT MILK. In this instance, the four foursomes are related by a meta-theme (“things you shouldn’t do”); in actual Connections puzzles, that usually isn’t the case. Note that the grid contains the similar words “bite” and “cut” next to each other, suggesting membership in a foursome of actions that divide an objects into pieces. Likewise the proximity of “mouth”, “nose”, and “hand” suggests shared membership in a foursome of body parts. These are false leads. In the on-line version of the puzzle, there’s a button that allows you to scramble the words to make the false leads less salient and to bring out the true patterns, or at least to make it possible for your brain to find new connections between words. The computer code that scrambles the words uses a pseudorandom number generator to scramble the sixteen words uniformly; for instance, there is a 1 out of 16! chance that pressing the Scramble button will have no effect at all. Empirically one finds that it takes between 20 and 30 scramblings for all the possible adjacencies between the 16 words to appear. That is, if one scrambles only 20 times, it is nearly certain that some pair of words will not have occurred adjacently, whereas if one scrambles 30 times, it is nearly certain that every pair of words will have occurred adjacently at least once. Since each 4-by-4 grid (the original grid and the successive scrambled versions) has 24 adjacent pairs, and since 16\choose 2 is exactly five times 24, one might hope that if one is extremely lucky, it might happen that after a mere four scramblings each of the possible pairs of words will have occurred adjacently exactly once. The question is, can this actually happen? We will show that the answer is Yes ; that is, K_{16} can be partitioned into five copies of P_{4}\square P_{4} . Our proof makes use of the finite field with 16 elements, though the first construction of such a partition was not constructed algebraically but was found by Ed Kirkby using computer search. [ 3 ] Likewise, since a 3-by-3 grid graph has 12 adjacent pairs of cells, and since 9\choose 2 is exactly three times 12, one might hope that if the words in a 3-by-3 grid are scrambled and then scrambled again in just the right way, each of the possible pairs of words will occur adjacently exactly once. Can this actually happen? A combinatorial argument shows that in this case the answer is No ; that is, K_{9} cannot be partitioned into three copies of P_{3}\square P_{3} . More generally, whenever n is congruent to 0 or 3 mod 4, so that n^{2}\choose 2 is a multiple of 2n(n-1) , one may ask, for each such n , whether K_{n^{2}} can be partitioned into copies of P_{n}\square P_{n} . We have not made much of a dent in this problem, but we have had made some progress with a more symmetrical version of the problem in which P_{n}\square P_{n} is replaced by C_{n}\square C_{n} . Since n^{2}\choose 2 is a multiple of 2n^{2} whenever n is congruent to 1 or 3 mod 4, one may ask, for each such n , whether K_{n^{2}} can be partitioned into copies of C_{n}\square C_{n} ; we will show that this is indeed the case whenever n is an odd prime raised to the first or second power. This Note is organized as follows. In Section 2 , we use finite field methods to show that when p is an odd prime, K_{p^{2}} can be partitioned into (p^{2}-1)/4 copies of C_{p}\square C_{p} (Theorem 1), and that K_{p^{4}} can be partitioned into (p^{2}-1)/4 copies of C_{p^{2}}\square C_{p^{2}} (Theorem 2). In Section 3 , we show that K_{9} cannot be partitioned into 3 copies of P_{3}\square P_{3} (Theorem 3) and by modifying the method of Section 2 we show that K_{16} can be partitioned into 5 copies of P_{4}\square P_{4} (Theorem 4). Section 4 presents comments and open questions. 2 Torus Grids We can picture the torus graph C_{n}\square C_{n} either by modding out the infinite 4-regular graph {\mathbb{Z}}\square{\mathbb{Z}} by the translations (n,0) and (0,n) or by drawing the ordinary grid P_{n}\square P_{n} and adding wraparound edges along the boundary. Since C_{n}\square C_{n} has 2n^{2} edges while K_{n^{2}} has n^{2}(n^{2}-1)/2 edges, it is clear that if K_{n^{2}} can be decomposed into disjoint copies of C_{n}\square C_{n} , the number of copies must be (n^{2}-1)/4 , so n must be odd. Theorem 1: When p is an odd prime, K_{p^{2}} can be partitioned into (p^{2}-1)/4 copies of C_{p}\square C_{p} . Proof: Associate the vertices of K_{p^{2}} with the elements of {\mathbb{F}}_{p^{2}} , which we model as {\mathbb{F}}_{p}[x]/(f(x)) where f is some primitive quadratic polynomial over