ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 18 (2020) 127-135
https://doi.org/10.26493/1855-3974.1959.9c7
(Also available at http://amc-journal.eu)
On the upper embedding of Steiner triple systems and Latin squares*
Terry S. Griggs
School of Mathematics and Statistics, The Open University, Milton Keynes MK7 6AA, United Kingdom
Thomas A. McCourt
Craigslea State High School, Brisbane QLD 4032, Australia
Received 26 March 2019, accepted 20 December 2019, published online 29 September 2020
It is proved that for any prescribed orientation of the triples of either a Steiner triple system or a Latin square of odd order, there exists an embedding in an orientable surface with the triples forming triangular faces and one extra large face.
Keywords: Upper embedding, Steiner triple system, Latin square. Math. Subj. Class. (2020): 05B07, 05B15, 05C10
1 Introduction
The motivation for the work described herein comes from two previous papers, respectively on the upper embedding of Steiner triple systems [1] and the upper embedding of Latin squares [ ]. First we recall the relevant definitions. Let X = (V, B) be a (partial) triple system on a point set V, that is, a collection B of 3-element subsets of V, called blocks
*All three authors wish to express their thanks to an anonymous referee for considerably improving the proof of Proposition 3.1.
t The third author acknowledges support from the APVV Research Grants 15-0220 and 17-0428 and the VEGA Research Grants 1/0142/17 and 1/0238/19.
E-mail addresses: t.s.griggs@open.ac.uk (Terry S. Griggs), tom.a.mccourt@gmail.com (Thomas A. McCourt), j.siran@open.ac.uk (Jozef Siran)
Jozef Siran t
School ofMathematics and Statistics, The Open University,
Milton Keynes MK7 6AA, United Kingdom and Slovak University of Technology, Bratislava 81005, Slovakia
Abstract
©® This work is licensed under https://creativecommons.org/licenses/by/4.0/
106
Ars Math. Contemp. 18 (2020) 105-115
or triples, such that every 2-element subset of V is contained in at most one triple in B. Equivalently, such a triple system X may be viewed as a pair (K, B), where K is a graph with vertex set V and edge set E consisting of all pairs uv for distinct points u, v e V such that {u, v} is a subset of some block in B. In other words, in the graph setting, B is regarded as a decomposition of the edge set E of K into triangles. Of course, such a graph K = (V, E) may admit many decompositions into triangles and so the set of blocks B needs to be specified. We will refer to K = (V, E) with the specified decomposition B of E as the graph associated with the triple system X = (V, B). We will be assuming throughout that the triple systems considered here are connected, meaning that their associated graphs are connected. In the case of a Steiner triple system S = STS(n) where n = |V|, the associated graph is the complete graph Kn. Such systems exist if and only if n = 1 or 3 (mod 6) [ ]. For a Latin square L = LS(n), the associated graph is the complete tripartite graph Kn,n,n where the three parts of the tripartition are the rows, the columns and the entries of the Latin square.
By an embedding of a triple system X = (V, B) we will understand a cellular embedding $: K ^ E of the associated graph K = (V, E) of X in an orientable surface E, such that every triangle in B bounds a face of $. Such faces will be called block faces, and the remaining faces of the embedding $ will be called outer faces. By the properties of the set B, in the embedding $ every edge of E lies on the boundary of exactly one block face, so that there is at least one outer face in $. The extreme case occurs if such an embedding has exactly one outer face; we then speak about an upper embedding and call the triple system X = (V, B) upper embeddable.
A necessary and sufficient condition for upper embeddability of triple systems follows from available knowledge about upper embeddings of graphs in general. To make use of this we will represent triple systems by their point-block incidence graphs as usual in design theory. For a triple system X = (V, B) its point-block incidence graph is the bipartite graph G(X) with vertex set V U B and edge set consisting of pairs {v, B} for v e V and B e B such that v e B. The pair (V, B) forms the bi-partition of the vertex set of G(X); vertices in V and B will be referred to as point vertices and block vertices respectively. By our convention regarding triple systems, the graph G(X) is assumed to be connected, and note that every block vertex has valency 3 in G(X).
It is a folklore fact in topological design theory that there is a one-to-one correspondence between orientable embeddings of a triple system X and its point-block incidence graph G(X) in orientable surfaces; the correspondence is illustrated in Figure 1. As is obvious from this figure, an embedding of G(X) arises from an embedding of X naturally. On the other hand, given an embedding of G(X) one obtains the corresponding embedding of X by 'inflating' every block vertex into a triangle on the surface. In particular, a triple system X is upper embeddable if and only if its point-block incidence graph is embeddable with exactly one face; such graphs are also called upper-embeddable. By a classical result of Jungerman [3] and Xuong [5], a graph (in particular, the point-block incidence graph of a triple system) is upper-embeddable if and only if the graph contains a spanning tree such that each of its co-tree components has an even number of edges.
Let us now look more closely at an upper embedding of a triple system X = (V, B) in an orientable surface E, or, equivalently, at an upper embedding $: G(X) ^ E of the point-block intersection graph of X in E. For any triple B = {u, v, w} e B the (given) orientation of E induces one of the two cyclic permutations (u, v, w) or (u, w, v) when looking at the three points from the 'centre' of the triangular face representing B. Equivalently
T. S. Griggs et al.: On the upper embedding ofSteiner triple systems and Latin squares
129
for any block vertex B of G(T) with point vertex neighbours u, v, w, the orientation of E induces one of the cyclic permutations (u, v, w) or (u, w, v) of the three points 'around' the block vertex B. We refer to any of the two permutations as an orientation of the triple, or equivalently, an orientation of the neighbourhood. In this terminology, the orientation of E induces one of the two possible orientations of every triple (or, of the neighbourhood of every block vertex) in the embedding. It was proved in [1] that every Steiner triple system STS(n) and in [2] that every Latin square LS(n) where n is odd has an upper embedding in an orientable surface. In the Latin square case the restriction that n must be odd is determined by Euler's formula (V + F - E = 2 - 2g). However in both [ ] and [ ] no attention was paid to the orientation of the triples in the upper embeddings.
The driving question of our research is the following question. Which triple systems X = (V, B) have the property that, for every choice of the orientation of all triples B e B, the system X admits an upper embedding in an orientable surface such that the orientation of the surface induces the preassigned orientation of B for every triple B e B? We will refer to this property simply as upper embeddability in every orientation of triples. The main results of this paper are the two theorems below which substantially extend the results in the two papers [1] and [2].
Theorem 1.1. Every Steiner triple system admits an upper embedding in every orientation of triples.
Theorem 1.2. Every Latin square of odd order admits an upper embedding in every orientation oftriples.
2 Spanning tree
In what follows we prove a sufficient condition for a triple system to admit upper embed-dability in every orientation of triples. The result will be stated in terms of the point-block incidence graph of a triple system and, as one expects by Jungerman and Xuong's Theorem [3] and [5], the statement will involve existence of a spanning tree with particular properties. We recall the connectivity assumption of our triple systems.
106
Ars Math. Contemp. 18 (2020) 105-115
Theorem 2.1. Let X be a triple system and let G = G(X) be its point-block incidence graph. If G admits a spanning tree such that every point vertex has even valency in the corresponding co-tree, then X admits an upper embedding in every orientation of triples.
Proof. Let X = (V, B) and suppose that every triple B = {u, v, w} e B has been assigned an orientation, i.e., one of the two cyclic permutations (u, v, w), (u, w, v). Using the ideas of Jungerman and Xuong we will show (by induction) how to build an upper embedding of the point-block incidence graph G = G(X) of X in an oriented surface in such a way that its orientation will induce the preassigned orientation on every B e B.
Let T be a spanning tree of G as in the assumption of our theorem, that is, such that every point vertex of the subgraph of G induced by the set E(G) \ E(T) of co-tree edges has even valency. Since G is bipartite, this assumption implies that the set E(G) \ E(T) has a decomposition into paths of length two that have a point vertex in the centre; in particular, the number of co-tree edges here is even. We note that the quantity fi = |E(G) \ E(T) | is known as the Betti number of G. The set of co-tree edges thus decomposes into fi/2 paths P of the form P = AuB, where A, B are block vertices and u is a point vertex.
To proceed, we prove quite a general auxiliary statement on upper embeddability of extensions of spanning subgraphs of our point-block incidence graph by paths as above. Let H be a connected spanning subgraph of G and let A and B be block vertices and u be a point vertex of H such that P = AuB is a path in G but the edges Au and Bu are not in H. Further, let C be the set of block vertices of G that have valency 3 in H. We will say that H upper embeds in every orientation at C if, for every vertex C eC and every orientation of the neighbourhood of C, there is an embedding of H in an orientable surface such that its orientation induces the preassigned orientation around every vertex C e C. Extending this terminology in a natural way to the graph H' = H U P and the set C of block vertices of valency 3 in H', we prove the following.
Claim. If H upper embeds in every orientation at C, then H' upper embeds in every orientation at C'.
To prove our Claim, let H ^ E be an upper embedding of H in an orientable surface E such that its orientation induces the preassigned orientations of neighbourhoods of block vertices in C. Let P = AuB be a path as above. The boundary of the single face F of this embedding is, without loss of generality, a closed walk in H of the form (uXAYBZ), where X, Y, Z are u ^ A, A ^ B and B ^ u walks of H traversed in the direction induced by the (clockwise) orientation of E, as one can see in Figure 2 when disregarding the arcs (edges with direction) a, b, c, d. We point out that in our considerations the order of appearance of the vertices A and B on the boundary of F will be immaterial.
Ignoring the condition on the set C', the embedding of H can be extended to an upper embedding of H'. Namely, letting a = uA and b = uB denote the arcs from u to A and u to B respectively, one 'adds' the path P = AuB to the single face F of $ in such a way that all the local cyclic orderings of arcs emanating from vertices distinct from A, u, B are kept intact and the local cyclic ordering of neighbours of u is extended from (..., c, d,...) to (..., c, b, a, d,...) as in Figure 2; the local cyclic order of arcs at A and B is obvious from Figure 2.
The single face F' of the new embedding of H' in an oriented surface E' is obtained by tracing down its boundary, which is the closed walk (uXa-bZaYb-), where a- and b- indicate traversals along a and b in the opposite direction. We again emphasize that, for
T. S. Griggs et al.: On the upper embedding ofSteiner triple systems and Latin squares	129
A	B
this construction, the position of A and B on the boundary of F is irrelevant. Note that the genus of E' is equal to the genus of E increased by 1.
We now show that the above construction can be carried out in such a way that the orientation of E' induces the preassigned orientations of neighbours of vertices in C'. This orientation is obviously maintained for block vertices in the subset CcC' and so one only needs to consider the block vertices in C'\C c {A, B}; note that A, B G C. If neither A nor B are in C', we simply use the above construction. If one or both of A, B are in C'\C, then we proceed as follows.
Say, without loss of generality, that A g C', which means that the valency of A in H must have been equal to 2. We know that u g A; let A = {u,v,w} with {v,w} being the point vertices constituting the neighbourhood of A in H. Since the boundary of the single face F in H must contain every edge twice (and traversed in each direction once) and A has valency 2 in H, it follows that the boundary of F must have the form (u ... vAw ... wAv ...), as displayed in Figure 3; the relative position of the vAw and wAv paths is without loss of generality.
Figure 3: Adding the edge uA to control the orientation of the triple A.
106
Ars Math. Contemp. 18 (2020) 105-115
Now, if the preassigned orientation of the block A = {u, v, w} is given by the cyclic permutation (uvw), we will add the arc a = uA pointing to the position of A appearing on the left-hand side of Figure 3; if the preassigned orientation is (uwv) we use the arc a pointing to the occurrence of A on the right-hand side in Figure 3. If the vertex B also has valency 2 in H, we make a similar choice for the position of B for addition of the arc b = uB. We then complete the construction of the single face embedding of H' with the required properties as in the previous paragraph.
Having proved our Claim, the rest of the proof is straightforward. We begin by embedding the spanning tree T in a sphere in such a way that its orientation induces a preassigned orientation at every block vertex that has valency 3 in T. We then apply the construction of our Claim ft/2 times for every path in the decomposition of the set E(G)\E(T) of co-tree edges into ft/2 paths whose middle vertex is a point vertex. As a result we obtain the upper embeddability of G in every orientation at its set B of block vertices.	□
3 Steiner triple systems
We deal first with the case of Steiner triple systems. In view of the previous section, Theorem 1.1 follows immediately from the following Proposition.
Proposition 3.1. Let S = (V, B) be a Steiner triple system of order n and let G = G(S) be its point-block incidence graph. Then G admits a spanning tree such that every point vertex has even valency in the corresponding co-tree.
Proof. If n = 3, the result is true trivially. If n = 7, then S is unique up to isomorphism and G is the Heawood graph. A breadth first search starting from any block gives a tree in which each point has valency 1 or 3 and hence valency 2 or 0 in the co-tree. Now assume that n > 9.
Let V = {0,1,... ,n - 1}. Construct a spanning tree T of the point-block incidence graph G as follows. For convenience, we will refer to point vertices simply as points and block vertices as blocks. Let the root (Level 0) of the tree be the point 0. Connect the point to all (n - 1)/2 blocks containing it, which will be at Level 1. At Level 2 put all the n - 1 points x G V \ {0} and connect these to the blocks at Level 1 which contain them. The remaining n(n — 1)/6 — (n — 1)/2 = (n — 1)(n — 3)/6 blocks are at Level 3. Connect each one of these to a point at Level 2 which is contained in the block. The structure of the spanning tree is shown below.
In the co-tree the point 0 has zero valency and the points at Level 2 have either odd or even valency including zero. We will refer to such points as either odd points or even points respectively. The number of edges in the co-tree is 3n(n — 1)/6 — n(n — 1)/6 — n +1 = (n — 1)(n — 3)/3 which is even. Thus the number of odd points is even. The aim is to construct a spanning tree with no odd points. The proof is in the form of an iterative algorithm. Beginning with a spanning tree constructed as above, at any stage, if there are odd points at Level 2, modify how the blocks at Level 3 are connected to the points at Level 2 in order to reduce the number of odd points until they are absent. Let B3 denote the set of blocks at Level 3, i.e. the blocks that do not contain 0. Each of these blocks is always adjacent in T to exactly one point. Let P be the number of odd points. For any distinct a,b G V let ab be the point so that {a, b, ab} G B.
Claim 1. If {a, b, c} G B3, {a, {a, b, c}} G T, a is odd, and at least one of b or c is odd, then we can reduce P.
T. S. Griggs et al.: On the upper embedding ofSteiner triple systems and Latin squares
129
Figure 4: Spanning tree of G(S).
Proof. Suppose that b is odd. Replace {a, {a,b,c}} by {b, {a,b,c}}.	□
Claim 2. If P > 0 then we may assume that there is {p, q, r} e B3 with p and q odd, r even, and {r, {p, q,r}} e T; otherwise we can reduce P.
Proof. If P > 0 then there are at least two odd points: say a and b are odd.
Suppose that w = ab = 0, so {a, b, w} e B3. If w is odd or {w, {a, b, w}} e T, then we can reduce P by Claim 1. So we may assume that {a, b, w} is the required block, with
p = a, q = b, r = w.
Suppose now that ab = 0, so that {a, {a, b, 0}} e T. Since a does not have valency 0 in the co-tree, there is some block {a, c, x} e B3 with {a, {a, c, x}} e T. Then c,x e V \ {0, a, b} and we may assume that {c, {a, c, x}} e T .If c is odd, then we can reduce P by Claim 1, so assume that c is even. Replace {a, {a, c, x}} in T by {c, {a, c, x}}, so that a becomes even and c becomes odd. There is also some {b, c, y} e B3. If y is odd or {y, {b, c, y}} e T then we can reduce P by Claim 1. So we may assume that {b, c, y} is the required block, with p = b, q = c, r = y.	□
Claim 3. Given a block {p, q, r} as in Claim 2, we can reduce P.
Proof. Let Sp be the set of points z such that {p,z,pz} e B3, z is even, and either {p, {p, z,pz}} eT or {z, {p, z,pz}} e T. Define Sq and Sr similarly.
There are N = (n — 5)/2 blocks {p,z,s} e B\ {{p,q,r}, {p, 0,p0}}, which all belong to B3. Consider such a block {p, z, s}. If {p, {p, z, s}} e T then we can reduce P by Claim 1 unless z and s are both even, so z e Sp. Otherwise we may assume that {z, {p, z, s}} e T, and again we may reduce P by Claim 1 unless z is even, so again z e Sp. Since each of the N blocks {p, z, s} contains an element of Sp, ISp | > N.
Similarly, ISq | > N. Temporarily replacing {r, {p, q, r}} in T by {p, {p, q, r}}, which does not change Sr, we also obtain ISr | > N. Then Sp, Sq, Sr C V \ {0, p, q, r} and since n > 9, we have ISpl + |Sq | + |Sr | > 3N = 3(n — 5)/2 > n — 4. Hence by the pigeonhole principle there is some z belonging to at least two of Sp,Sq ,Sr.
If z e Sp n Sq, replace {p, {p, z,pz}} in T by {z, {p, z,pz}} or vice versa, and replace {q, {q, z, qz}} in T by {z, {q, z, qz}} or vice versa. This makes p and q even, and the
106
Ars Math. Contemp. 18 (2020) 105-115
parity of z is changed twice, so remains even; hence P is reduced. If z £ Sp Pi Sr or
z £ Sq P Sr apply a similar argument after replacing {r, {p, q, r}} in T by {q, {p, q, r}} or {r, {p, q, r}}, respectively.	□
By applying Claims 2 and 3 repeatedly we can reduce P to 0, as required.
□
4 Latin squares
Now we turn our attention to the case of Latin squares of odd order. Let LS(n) be a Latin square of odd order. Denote the sets of row points, column points and entry points by R, C and E respectively. Let B be the set of triples, which we will also for convenience refer to as blocks, {ir , jc, ke} where ir £ R, jc £ C, ke £ E and k = L(i,j). The point-block incidence graph is the bipartite graph with vertex set RuCuEuB and edge set
{(vr, B) : vr £ R, B £ B, vr £ B} U {(vc, B) : vc £ C, B £ B, vc £ B}
U {(ve, B) : ve £ E, B £ B, ve £ B}.
The following result is an exact analogy of Proposition 3.1 above for Steiner triple systems and establishes Theorem 1.2. However the proof is much simpler. We are able to construct the spanning tree with the appropriate property directly rather than by an iterative procedure.
Proposition 4.1. Let L = LS(n) be a Latin square of odd order n and let G = G(L) be its point-block incidence graph. Then G admits a spanning tree such that every point vertex has even valency in the corresponding co-tree.
Proof. Let R = {0r, 1r,..., (n - 1)r }, C = {0c, 1c,..., (n - 1)c} and E = {0e, 1e,..., (n - 1)e}. Construct a spanning tree T of the point-block incidence graph G as follows.
Figure 5: Spanning tree of G(L).
T. S. Griggs et al.: On the upper embedding ofSteiner triple systems and Latin squares
129
For convenience, we will again refer to point vertices simply as points and block vertices as blocks. Let the root (Level 0) of the tree be the point 0r. Connect the point to all n blocks containing it, which will be at Level 1. At Level 2 put all the 2n points x g CUE and connect each of these to the unique block at Level 1 which contains it. At Level 3 put the remaining n - 1 blocks which contain the point 0c and connect these to 0c. Then at Level 4 put the n - 1 points R \ {0r } and connect each of these to the unique block at Level 3 which contains it. In standard form, i.e. L(0, j) = j, the structure of the tree is shown in Figure 5.
At this stage we have a tree which contains all the points but only the blocks which contain the points 0r or 0c. Now consider the point 1c. There are n - 1 blocks containing the point which as yet are not in the tree. Connect all of these to 1c. Repeat this procedure for all of the points in the set C \ {0c, 1c}. We now have a spanning tree of the point-block incidence graph in which the valency of the points 0r and x g C are n and all other points have valency 1. Thus in the co-tree all points have even valency.	□
References
[1]	M. J. Grannell, T. S. Griggs and J. Siran, Maximum genus embeddings of Steiner triple systems, European J. Combin. 26 (2005), 401-416, doi:10.1016/j.ejc.2004.01.014.
[2]	T. S. Griggs, C. Psomas and J. Siran, Maximum genus embeddings of Latin squares, Glasg. Math. J. 60 (2018), 495-504, doi:10.1017/s0017089517000234.
[3]	M. Jungerman, A characterization of upper-embeddable graphs, Trans. Amer. Math. Soc. 241
(1978),	401-406, doi:10.2307/1998852.
[4]	T. P. Kirkman, On a problem in combinations, Cambridge Dublin Math. J. 2 (1847), 191-204, http://resolver.sub.uni-goettingen.de/purl?PPN6004 93 962_0 002.
[5]	N. H. Xuong, How to determine the maximum genus of a graph, J. Comb. Theory Ser. B 26
(1979),	217-225, doi:10.1016/0095-8956(79)90058-3.