Page 38 - Ellingham, Mark, Mariusz Meszka, Primož Moravec, Enes Pasalic, 2014. 2014 PhD Summer School in Discrete Mathematics. Koper: University of Primorska Press. Famnit Lectures, 3.
P. 38
1.7 Connections with design theory
In general if we just take two arbitrary Steiner triple systems then we do not get an em-
bedding: we have a set of closed walks covering each edge twice, but may not have
proper rotations.
If we take two Steiner triple systems T1 and T2, not clear when T1 can be biembedded with
something isomorphic to T2. At least one case known where this cannot be done if
we insist that the embedding must be orientable.
Biembeddings of Latin squares
Definition: A latin square is an n × n array of n symbols so that every symbol occurs
exactly once in each row and each column.
Suppose we have a 2-face-colourable triangular embedding of a complete tripartite graph
Kn,n,n with tripartition (A, B,C ) where A = {a 1, a 2, . . . , a n }, etc. Take one colour class
of faces, then we have a partition of the edges of Kn,n,n into triangles. If we interpret
a triangle (a i b j ck ) as telling us to put symbol k in row i , column j , then we get a latin
square for each colour class. Altogether this is a biembedding of latin squares. If this
exists, the surface is necessarily orientable.
Again, if we take two arbitrary latin squares, it is not clear if we can biembed them. But
there is one positive result with very useful consequences.
Definition: A latin square L is consecutive-row-hamiltonian if for every two (cyclically)
consecutive rows, the permutation we get by mapping symbols in the first row to the
symbols in the same column in the second row is a cyclic (hamiltonian!) permuta-
tion.
Simple example: Zn , the addition table of n , is consecutive-row-hamiltonian.
Theorem (Grannell and Griggs [GG08]): Any latin square that is consecutive-row-ha-
miltonian has a biembedding with something isomorphic to itself (in fact, to itself with
all rows shifted up one position).
This was used as part of first construction of n an2 nonisomorphic triangulations of Kn
for certain n . Overall construction used ideas related to earlier result giving c n2 such
triangulations (mentioned in section on surgery).
Latin squares and hamilton cycle embeddings of complete tripartite graphs
Can also use latin squares to get other embeddings of complete tripartite graphs: ones
where all facial walks are hamilton cycles. Need two conditions. First, latin square
must be consecutive-entry-hamiltonian (similar to consecutive-row-hamiltonian,
and in fact could use that instead). Second, latin square L must have an orthogonal
mate: another latin square L such that for every symbol s of L and every symbol s
of L there is some row and column that contains s in L and s in L .
Theorem (Ellingham and Schroeder): An n × n latin square that is consecutive-entry-
hamiltonian and has an orthogonal mate can be used to construct a 2-face-colourable
In general if we just take two arbitrary Steiner triple systems then we do not get an em-
bedding: we have a set of closed walks covering each edge twice, but may not have
proper rotations.
If we take two Steiner triple systems T1 and T2, not clear when T1 can be biembedded with
something isomorphic to T2. At least one case known where this cannot be done if
we insist that the embedding must be orientable.
Biembeddings of Latin squares
Definition: A latin square is an n × n array of n symbols so that every symbol occurs
exactly once in each row and each column.
Suppose we have a 2-face-colourable triangular embedding of a complete tripartite graph
Kn,n,n with tripartition (A, B,C ) where A = {a 1, a 2, . . . , a n }, etc. Take one colour class
of faces, then we have a partition of the edges of Kn,n,n into triangles. If we interpret
a triangle (a i b j ck ) as telling us to put symbol k in row i , column j , then we get a latin
square for each colour class. Altogether this is a biembedding of latin squares. If this
exists, the surface is necessarily orientable.
Again, if we take two arbitrary latin squares, it is not clear if we can biembed them. But
there is one positive result with very useful consequences.
Definition: A latin square L is consecutive-row-hamiltonian if for every two (cyclically)
consecutive rows, the permutation we get by mapping symbols in the first row to the
symbols in the same column in the second row is a cyclic (hamiltonian!) permuta-
tion.
Simple example: Zn , the addition table of n , is consecutive-row-hamiltonian.
Theorem (Grannell and Griggs [GG08]): Any latin square that is consecutive-row-ha-
miltonian has a biembedding with something isomorphic to itself (in fact, to itself with
all rows shifted up one position).
This was used as part of first construction of n an2 nonisomorphic triangulations of Kn
for certain n . Overall construction used ideas related to earlier result giving c n2 such
triangulations (mentioned in section on surgery).
Latin squares and hamilton cycle embeddings of complete tripartite graphs
Can also use latin squares to get other embeddings of complete tripartite graphs: ones
where all facial walks are hamilton cycles. Need two conditions. First, latin square
must be consecutive-entry-hamiltonian (similar to consecutive-row-hamiltonian,
and in fact could use that instead). Second, latin square L must have an orthogonal
mate: another latin square L such that for every symbol s of L and every symbol s
of L there is some row and column that contains s in L and s in L .
Theorem (Ellingham and Schroeder): An n × n latin square that is consecutive-entry-
hamiltonian and has an orthogonal mate can be used to construct a 2-face-colourable
