Grid designs

• Published in 2026
• Added on 2026-03-01

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.

Links

• https://arxiv.org/abs/2601.00165v2
• https://arxiv.org/pdf/2601.00165v2

Other information

BibTeX entry

@article{Griddesigns,
	key = {Griddesigns},
	type = {article},
	title = {Grid designs},
	author = {Alon Danai and Joshua Kou and Andy Latto and Haran Mouli and James Propp},
	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.},
	comment = {},
	date_added = {2026-03-01},
	date_published = {2026-03-09},
	urls = {https://arxiv.org/abs/2601.00165v2,https://arxiv.org/pdf/2601.00165v2},
	collections = {combinatorics},
	url = {https://arxiv.org/abs/2601.00165v2 https://arxiv.org/pdf/2601.00165v2},
	year = 2026,
	urldate = {2026-03-01},
	archivePrefix = {arXiv},
	eprint = {2601.00165},
	primaryClass = {math.CO}
}