ARS MATHEMATICA CONTEMPORANEA Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 8 (2015) 267-273 Further biembeddings of twofold triple systems Diane M. Donovan Centre for Discrete Mathematics and Computing, University of Queensland, St Lucia 4072, Australia Terry S. Griggs Department of Mathematics and Statistics, The Open University, Walton Hall, Milton Keynes MK7 6AA, U.K. James G. Lefevre Centre for Discrete Mathematics and Computing, University of Queensland, St Lucia 4072, Australia Thomas A. McCourt Heilbronn Institute, Department ofMathematics, University ofBristol, University Walk, Bristol BS81TW, U.K. Received 6 December 2012, accepted 25 January 2014, published online 3 February 2015 We construct face two-colourable triangulations of the graph 2Kn in an orientable surface; equivalently biembeddings of two twofold triple systems of order n, for all n = 16 or 28 (mod 48). The biembeddings come from index 1 current graphs lifted under a group Zn/4 x K4. Keywords: Biembedding, orientable surface, twofold triple system. Math. Subj. Class.: 05B07, 05C10 1 Introduction A complete graph Kn has a triangulation in an orientable surface if and only if n = 0,3,4 or 7 (mod 12), [5]. In such a triangulation the number of faces around each vertex is n - 1, and so if n - 1 is even, i.e. n = 3 or 7 (mod 12), it may be possible to colour each face using one of two colours, say black or white, so that no two faces of the same E-mail addresses: dmd@maths.uq.edu.au (Diane M. Donovan), t.s.griggs@open.ac.uk (Terry S. Griggs), jamie.lefevre@gmail.com (James G. Lefevre), tom.a.mccourt@gmail.com (Thomas A. McCourt) Abstract ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/ 268 Ars Math. Contemp. 8 (2015) 235-244 colour are adjacent. In such a case we say that the triangulation is (properly) face two-colourable. In this case the set of faces of each colour class forms a Steiner triple system of order n, STS(n) for short, i.e. a collection of triples which have the property that every pair is contained in precisely one triple. We say that the two STS(n)s are biembedded in the (orientable) surface. An obvious question therefore is whether, for each n = 3 or 7 (mod 12), there is a biembedding of some pair of STS(n)s in an orientable surface. The answer is in the affirmative; the case n = 3 (mod 12) is dealt with in [5] and the case n = 7 (mod 12) in [6]. In [2] an extension of the above was considered. The necessary condition for the graph 2Kn, i.e. the graph on n vertices with each pair of vertices joined by two edges, to have a triangular embedding in an orientable surface is n = 0 or 4 (mod 6). Such triangulations may be face two-colourable, in which case each colour class forms a twofold triple system of order n, TTS(n) for short, i.e. a collection of triples which have the property that every pair is contained in precisely two triples. Again we say that the two TTS(n)s are biembedded in the (orientable) surface. For such biembeddings to admit a cyclic automorphism it is necessary and sufficient that n = 4 (mod 12) [2] and a complete solution was provided in that paper. However the method is rather complex. In this paper, for the case n = 28 (mod 48), we give a much simpler construction based on cyclic biembeddings of Steiner triple systems of order 12m + 7, m > 0. These were found by Youngs [6] and index 1 current graphs corresponding to these solutions are readily accessible. They can be found in [3]. The biembeddings of the TTS(n)s which we obtain from these biembeddings of Youngs however are not cyclic; they have an automorphism group Zi2m+7 x K4 where K4 is the Klein 4-group. Further we extend our method to find new biembeddings of TTS(n)s for n = 16 (mod 48); these have an automorphism group Zi2m+4 x K4. Finally iterating this latter process we obtain biembeddings of twofold triple systems of order 4s (12m + 4) with an automorphism group Zi2m+4 x (K4)s, s > 1, m > 0. We will also construct our biembeddings from index 1 current graphs lifted under the appropriate current group G of order g. These will satisfy the following properties, which are sufficient to construct a biembedding of a pair of TTS(n)s in an orientable surface, [5], [4], [3]. (i) Each vertex has degree 3. (ii) Each edge is assigned a current from the set G \ {0} so that each current appears exactly once. Note that a current of i in one direction is equivalent to a current of —i in the opposite direction. (iii) At each vertex, the sum of the directed currents is the identity (Kirchoff's current law, KCL). (iv) The directions (clockwise or anticlockwise) assigned to each vertex are such that a complete circuit is formed, that is, one in which every edge of the graph is traversed in each direction exactly once. (v) The graph is bipartite. Hence, such a current graph has 2(g — 1)/3 vertices and g — 1 edges. We use a Mobius ladder graph with (g — 1)/3 "rungs". Set u := (g — 1)/3. The formal definition of such a graph is as follows. The vertex set is {xj, y | 0 < i < u — 1} and the edge set is {{xj,yj}, {xj,xi+i}, {^y+i} | 0 < i < u — 2} U {{x„_i, y„_i}, {xo,y„_i}, D. M. Donovan et al.: Further biembeddings of twofold triple systems 269 A B x0 xi x u—2 xu—1 • • • • • • B A y o yi yu—2 yu—i Figure 1: A Möbius ladder graph {x„_i, y0}}. In order to obtain a complete circuit, vertices xj, 0 < i < u - 1, and yu-1 are assigned a clockwise direction and the vertices y^ 0 < i < u - 2, an anticlockwise direction- In this paper we represent these graphs as shown in Figure 1, where the directions of rotation are not indicated but implicit as defined above. We build the Mobius ladder graphs with currents assigned to the edges, so that Conditions (ii) and (iii) are met, from gadgets, i.e. edge labelled subgraphs which we link together by concatenation; we will define the linking of two gadgets D1 followed by D2 by D1 : D2 and the sequential linking of k gadgets by [Dj :]1 0. From [6] there exists a Mobius ladder graph that lifts under Zv to yield a biembedding of a pair of STS(v)s. Let L be such a graph. We begin by labelling Figure 1 as follows, xj = vj, yj = vj+2m+1, 0 < i < 2m. Thus the bipartition of L consists of the sets of even-indexed and odd-indexed vertices respectively. B V2m + 1 V2m+2 V2m+3 V2i+1 V2i+2 V2i+2m + 1 C2i+2 V2i+2m+2 V2i+2m+3 A V2m-2 V2m-1 V2m v4m-1 V4m v4m+1 B A Figure 2: Vertex and edge labels of L. 270 Ars Math. Contemp. 8 (2015) 235-244 Noting that by replacing a directed edge label by its inverse in the opposite direction, we can arrange the directed edge labels so that they point in to even-indexed vertices and out of odd-indexed vertices. Thus the directed edge labels will be taken to be as shown in Figure 2. As L satisfies Kirchoff's current law we have the following equations. ai + bi + ci = 0 (mod 12m + 7), (2.1) ai+2 + bi + Ci+2m+2 = 0 (mod 12m + 7). (2.2) We will require the following gadgets where indices are taken modulo 4m + 2: X (ao, 0) (bo, 0) (a0,x) (a0,z) (c0,0) (bo,0) (0,x) (co,z) (b0,x) (a2,y) (co, 0) A A(c2m+2,z) • > < 4 < 4 > < 4 < 4 > < • , y) (ao, z) (ao, x) (co, y) (bo, y) Yi (0, z) (co, x) (bo, z) (bi,y) • > (ai,z) (bi, x) (ai,y) (ci, 0) y • > < f > < * > < • < * > bi,y) > (ai,z) (bi, x) (ai+2,y) < f > < * > < • Y^ A(Ci+2m+2,z) T (ai, 0) (bi, 0) (ai, x) (bi, z) (ai, 0) (bi, 0) (ai, x) (bi, z) Equations (1.1), (2.1) and (2.2) verify that the gadgets X and, for 1 < j < 2m, Y2j satisfy KCL. Now consider the Mobius ladder graph X : [Y2j :]i 0, with Z12m+7 x K4 as an automorphism group. We conclude this section by giving two examples. Example 2.1. Let m = 0, v = 7 and n = 28. A Mobius ladder graph L, which yields the well known toroidal biembedding of a pair of STS(7)s, has a0 = 1, b0 = 2 and c0 = -3, i.e. A 1 > vo B ■ < * > 2 < b A—3 a 2 vi 1 In this case our construction gives just the gadget X, labelled as follows. (1,0) > (2, 0) < (1.x) > (1,z) (-3,0) > » < (2,0) > (0, x) (-3,z) > » < (2,x) > (i,y) < (-3,0) A —< 1 > < * < * > (1,y) (2, y) (1,z) (1,x) (-3,y) (2,y) (0,z) (-3,x) (2,z) (1,0) 2 Y1? >k(-3>z) < 1 > A B B A D. M. Donovan et al.: Further biembeddings of twofold triple systems 271 Example 2.2. Let m =1, v = 19 and n = 76. A Mobius ladder graph, L, yielding a biembedding of a pair of STS(19), is as follows. A ■ B 1 > 4 V2 —9 > f < B A -9 v3 Thus (a0,b0,c0) = (1,7, -8), (a2,b2,c2) = (-4, -9, -6) and (a4,b4,c4) (-2,5, -3). Our construction gives the following Mobius ladder graph. (1,0) (7,0) (1,x) (1,z) (-8,0) (7,0) (0, x) (-8,z) (7,x) (-4,y) B - (-8, 0) A < 1 > < * < * > 7( Y^ ><(-3,z) (< 1 > (1,y) (7, y) (1,z) (1,x) (-8,y) (7, y) (0, z) (-8,x) (7, z) (-4,0) (-4, y) (-9,y) (-4,z) (-9,x) (-4, y) (-9, y) (-4,z) (-9,x) (-2,y) —< (-6,0) > > f > < - > > - > < ■ - > > - > < ■ - > > - l < k(-8,z) (-4, 0) (-2, y) (-9,0) (5,y) (-4, x) (-2, z) ■ (-9, z) (5,x) (-4, 0) (-2, y) ■ ^ (-9, 0) (5,y) (-4, x) (-2, z) ■ (-9, z) (5,x) (-2,0) (i,y) (-3,0) > > < > < < - - t - co y - t - - I a-6-z) —- (-2,0) (5,0) (-2,x) (5, z) (-2,0) (5,0) (-2,x) (5,z) (1,0) 3 The case n = 16 (mod 48) Let v = n/4 = 12m + 4, m > 0. In [2] a Mobius ladder graph L based on the Colbourn and Colbourn difference triples, [1], on the set Z12m+4 \ {0} was constructed. In that paper the ladders were lifted under the cyclic group Z12m+4 to yield a biembedding of a pair of TTS(v)s. Similarly to Section 2 label the vertices and edges of L as follows (taking indices modulo 8m + 2): B ao b4m bo Aco a4ro+2 a2 C4m+2 b4m+2 V2i V2i+1 AC2 b2i Ac2i a2i+4m+2 V2i+2 a2i+2 C2i+4m+2 b2i+4m+2 >^c2i+2 V4m + 1 V4m+2 V4m+3 v4m-2 V2i+4m + 1 V2i+4m+2 V2i+4m+3 v4m-1 b4m-2 c4m-2 ¡}8m V4m c8m a4m i b8m < B b4„ y \ c4m. Op v8m-1 V8m v8m+1 A A 273 Ars Math. Contemp. 8 (2015) 235-244 where v0 corresponds to the difference triple 3m +1, 3m +1, 6m + 2. Note that this means that the vertices with even indices correspond to the Colbourn and Colbourn difference triples. Without loss of generality, in L, either a0 = c0 = 3m + 1 and b0 = 6m + 2 or a0 = b0 = 3m + 1 and c0 = 6m + 2. Both of these cases occur in the Mobius ladder graphs constructed in [2], depending on the residue class of v modulo 72 and we consider them separately in Subsections 3.1 and 3.2, respectively. We will make use of the following gadget where 2 < i < 8m: Note that in this case, because the initial Mobius ladder L yields a biembedding of a pair of twofold triple systems Vj, is simpler than the gadget used in Section 2. In fact it is "half" that gadget. As L satisfies Kirchoff's current law we have the following two equations. ai + b + ci = 0 (mod 12m + 4), (3.1) «i+2 + bi + Cj+4m+2 = 0 (mod 12m + 4). (3.2) These two equations together with Equation (1.1) verify that Vj also satisfies KCL. 3.1 = co = 3m + 1 and bo = 6m + 2 In this case it follows, from [2], that L yields the following two equations (6m + 2) + c4m+2 + a2 = 0 (mod 12m + 4), bgm + C4m + (3m + 1) = 0 (mod 12m + 4). (3.3) (3.4) In this case we will require the following gadget: (0,y) V V0 (ao,y) < (0,z) h (ao,x) < (bo, 0) > V(ao,x) A(0>x) (bo, x) -< V (c4m (ao,y) (a0, 0) (ao,z) (b0, y) (bo, z) (a2, 0) Equations (1.1) and (3.3) verify that V0 satisfies KCL. As ao = 3m + 1, Equations (1.1), (3.1), (3.2), (3.3) and (3.4) verify that the Mobius ladder graph V0 : [Vj :]i=2j, i—>-( »-<—( >—>-< »—>-( ^(co,x) y >-<-< »-<-o ^(ao,z) V >->-<► 4m+2 z) (ao, y) (ao, 0) (0,x) (co, 0) (ao,z) (a2,0) Equations (1.1) and (3.5) verify that V0' satisfies KCL. As a0 = 3m + 1, Equations (1.1), (3.1), (3.2), (3.5) and (3.6) verify that the Mobius ladder graph V0' : [V :]i=2j-, 1 0. Finally note that the gadget V0 contains a vertex with currents (3m +1, x), (3m +1, x) and (6m + 2,0) pointing outwards. Similarly the gadget V0' contains a vertex with currents (3m +1, z), (3m + 1, z) and (6m + 2,0) also pointing outwards. We call this vertex a. Our constructed Mobius ladder graphs L' contain just one of these two gadgets. By reversing the directions on all of the edges of L', labelling the vertex a as v0 and the edge with label (6m + 2,0) as b0, and extending in the same manner as above, the construction, using the gadget V0, can be reapplied. Repeated application of this process yields (Z12m+4 x (K4)s)-biembeddings of a pair of TTS(4s (12m + 4))s, s > 1, m > 0. References [1] M. J. Colbourn and C. J. Colbourn, Cyclic block designs with block size 3, European J. Combin. 2 (1981), 21-26. [2] D. M. Donovan, T. S. Griggs, J. G. Lefevre and T. A. McCourt, Cyclic biembeddings of twofold triple systems, Ann. Comb. 18 (2014), 57-74. [3] M. J. Grannell and T. S. Griggs, Designs and Topology, in Surveys in Combinatorics 2007, A. J. W. Hilton and J. Talbot (Editors), London Math. Soc. Lecture Note Series 346, Cambridge Univ. Press, Cambridge (2007), 121-174. [4] J. L. Gross and T. W. Tucker, Topological Graph Theory, John Wiley, New York (1987). [5] G. Ringel, Map Color Theorem, Springer-Verlag, New York (1974). [6] J. W. T. Youngs, The mystery of the Heawood conjecture, in Graph Theory and its Applications, Academic Press, New York (1970), 17-50.