# Which Graeco-Latin hypercubes are impossible?

Define a Graeco-Latin hypercube of dimension $n$ and order $k$ as an $n$-dimensional grid, with $k$ cells in each direction (for a total of $k^n$ cells), where:

• Each cell contains an ordered tuple $(x_1, x_2, x_3, ..., x_n)$ where each $x_i$ is a number from $1$ to $k$.

• For each row in any direction, no number is repeated in the same position on any two ordered tuples.

• Each possible ordered tuple is represented exactly once in the hypercube.

The case of $n = 2$ and $k = 6$ is the 36 officers problem, which Euler proved was impossible. Are there any other cases known to be impossible? Has there been any research done on this topic?

• If I get you correctly, looking at a 2d-face of a hypercube, for each pair i < j of coordinates of the tuples, the restriction (x_i, x_j) will form a Latin square. This means your dimension n will be bounded, certainly by the square root of the number of Latin squares of order k, and likely much smaller. Look up Mutually Orthogonal Latin squares for a better idea of bounds. Gerhard "Ask Me About System Design" Paseman, 2014.06.12 – Gerhard Paseman Jun 12 '14 at 18:38
• I think when there's no projective plane of order $k$ then the configuration you ask about is impossible for $n=k-1$. – Gerry Myerson Jun 13 '14 at 1:53
• There exists a projective plane of order $3$ and a bunch of Greaco-Latin hypercubes of dimension $2$. I'm not sure what you're talking about. – Joe Z. Jun 13 '14 at 6:12
• Something (possibly the requirement that all $n$-tuples occur somewhere in the hypercube?) seems to be missing from the definition. Otherwise, for $n=2,k=6$, any two Latin squares of order $6$ superimposed would satisfy the definition. – Janne Kokkala Jun 13 '14 at 10:03
• @JiK: Yeah, I forgot about that bit you just mentioned. – Joe Z. Jun 13 '14 at 17:29

Here is a selection of recent papers on orthogonal Latin hypercube designs. I'm not sure these are the same as Graeco-Latin hypercubes, but surely these papers give some idea of what designs are, and are not, possible.

MR2659850 (2011k:62223) Sun, Fasheng; Liu, Min-Qian; Lin, Dennis K. J. Construction of orthogonal Latin hypercube designs with flexible run sizes. J. Statist. Plann. Inference 140 (2010), no. 11, 3236–3242.

MR3183676 Georgiou, Stelios D.; Efthimiou, Ifigenia Some classes of orthogonal Latin hypercube designs. Statist. Sinica 24 (2014), no. 1, 101–120.

MR3377513 Cao, Rui-Yuan; Liu, Min-Qian Construction of second-order orthogonal sliced Latin hypercube designs. J. Complexity 31 (2015), no. 5, 762–772.

MR3254915 Georgiou, S. D.; Stylianou, S.; Drosou, K.; Koukouvinos, C. Construction of orthogonal and nearly orthogonal designs for computer experiments. Biometrika 101 (2014), no. 3, 741–747.

MR3183339 Huang, Hengzhen; Yang, Jian-Feng; Liu, Min-Qian Construction of sliced (nearly) orthogonal Latin hypercube designs. J. Complexity 30 (2014), no. 3, 355–365.

MR3183681 Yang, Jinyu; Liu, Min-Qian; Lin, Dennis K. J. Construction of nested orthogonal Latin hypercube designs. Statist. Sinica 24 (2014), no. 1, 211–219.

MR2933184 Yang, Jinyu; Liu, Min-Qian Construction of orthogonal and nearly orthogonal Latin hypercube designs from orthogonal designs. Statist. Sinica 22 (2012), no. 1, 433–442.

MR2861300 (2012j:05072)
Sun, FaSheng; Pang, Fang; Liu, MinQian Construction of column-orthogonal designs for computer experiments. Sci. China Math. 54 (2011), no. 12, 2683–2692.