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?

  • 3
    $\begingroup$ 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 $\endgroup$ – Gerhard Paseman Jun 12 '14 at 18:38
  • 1
    $\begingroup$ I think when there's no projective plane of order $k$ then the configuration you ask about is impossible for $n=k-1$. $\endgroup$ – Gerry Myerson Jun 13 '14 at 1:53
  • $\begingroup$ 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. $\endgroup$ – Joe Z. Jun 13 '14 at 6:12
  • $\begingroup$ 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. $\endgroup$ – Janne Kokkala Jun 13 '14 at 10:03
  • $\begingroup$ @JiK: Yeah, I forgot about that bit you just mentioned. $\endgroup$ – 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.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.