Latin cubes and hypercubes

Define a Latin hypercube of order n and dimension d to be a set of nd tuples (x1,x2,...,xd+1) over {0,1,...,n-1} such that each of the nd possible d-tuples appears exactly once in each set of d coordinate positions.

Latin hypercubes of dimension 1, 2 and 3 are commonly called permutations, Latin squares, and Latin cubes, respectively. The hypercube can be represented as a d-dimensional array C with C[x1,x2,...,xd] = xd+1 for each (d+1)-tuple. In the example below, we use this array representation to show a Latin hypercube with n=4 and d=3.
0123
1032
2301
3210
1032
0123
3210
2301
2301
3210
0123
1032
3210
2301
1032
0123
C[i,j,0] C[i,j,1] C[i,j,2] C[i,j,3]

A Latin hypercube is reduced if, whenever d-1 entries of a tuple are 0, the other two entries are equal. In the case of Latin squares, this is equivalent to the first row and column being in natural order. The example above is reduced.

Equivalence operations

Given a Latin hypercube A={(x1,...,xd+1)} and permutations (p1,...,pd+1) of {0,1,...,n-1}, then B={(p1(x1),...,pd+1(xd+1))} is also a Latin hypercube, said to be isotopic to the first. This is an equivalence relation, and the equivalence classes are called isotopy classes. If in fact A=B, then (p1,...,pd+1) is called an autotopism of A. The autotopisms of A form a group under composition, called the autotopy group Is(A).

Given a Latin hypercube A={(x1,...,xd+1)} and a permutation q of {1,2,...,d+1}, then B={(y1,...,yd+1)} is also a Latin hypercube, where yi=xq(i) for each i, is also a Latin hypercube, called a conjugate of A.

The operation of combining a conjugacy and an isotopism is called a paratopism. Paratopism is an equivalence operation whose equivalence classes are called main classes. A paratopism which takes a Latin hypercube A onto itself is an autoparatopism of A. The autoparatopisms of A form a group under composition, called the autoparatopy group Par(A). The autotopy group is a subgroup of the autoparatopy group.

The relative counts of Latin hypercubes and their isotopy or main classes depends on the group sizes:

Small Latin hypercubes

For Latin squares, see the Latin squares page. Here we give one representative from each main class of Latin hypercubes for some small orders and dimensions. The files have one line for each main class, containing a hypercube, then |Is(A)| and |Par(A)|/|Is(A)|. The hypercube is given as a list of the values C[x1,x2,...,xd] for subscripts in lexicographic order [0,0,...,0], [0,0,...,1], ..., [n-1,n-1,...,n-1]. (See above for the definition of C.)

This data was computed by Brendan McKay and Ian Wanless.

n d reduced
hypercubes
isotopy
classes
main
classes
4 3 64 12 5
4 4 7132 328 26
4 5 201538000 2133586 4785
5 3 40246 59 15
5 4 31503556 5466 86
5 5 50490811256 1501786 3102 (gzipped)
6 3 95909896152 5678334 264248 (gzipped)

Reference

B. D. McKay and I. M. Wanless, A census of small Latin hypercubes, SIAM Journal on Discrete Mathematics 22 (2008) 719-736.   preprint in PDF

 


Page Master: Brendan McKay, bdm@cs.anu.edu.au and http://cs.anu.edu.au/~bdm.

Up to the combinatorial data page