Grid designs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912959005982720 |
|---|---|
| author | Danai, Alon Kou, Joshua Latto, Andy Mouli, Haran Propp, James |
| author_facet | Danai, Alon Kou, Joshua Latto, Andy Mouli, Haran Propp, James |
| contents | We define a grid graph $G$ as a Cartesian product of path-graphs $P_n$ or cycle-graphs $C_n$ as shown in Figure 1, and we ask, when can the edge set of a complete graph be expressed as a disjoint union of graphs isomorphic to $G$? That is, we are asking for which grid graphs a $G$-design exists, where a $G$-design is defined as 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_00165 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Grid designs Danai, Alon Kou, Joshua Latto, Andy Mouli, Haran Propp, James Combinatorics 05C70 We define a grid graph $G$ as a Cartesian product of path-graphs $P_n$ or cycle-graphs $C_n$ as shown in Figure 1, and we ask, when can the edge set of a complete graph be expressed as a disjoint union of graphs isomorphic to $G$? That is, we are asking for which grid graphs a $G$-design exists, where a $G$-design is defined as 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. |
| title | Grid designs |
| topic | Combinatorics 05C70 |
| url | https://arxiv.org/abs/2601.00165 |