Triangular embeddings of complete graphs


The solution of the Heawood problem (see [3]) shows that the complete graph Kn admits a triangular embedding into some surface whenever the obvious necessary condition that n is congruent to 0 or 1 modulo 3 is satisfied. (The number of triangular faces of such an embedding is clearly equal to t = n(n-1)/3, so the condition just says that t is an integer.) 

If the dual graph of a triangular embedding of Kn is bipartite (which is only possible when n is odd), then the bipartition of the faces of the embedding determines two Steiner triple systems. Bonnington et al. [1] have shown that for infinitely many values of n, there are at least exp(n2/78 - O(n)) nonisomorphic triangular embeddings of Kn in orientable surfaces such that the dual is bipartite. In a conversation with Mark Ellingham we formulated the following

Conjecture 1 (Ellingham and Mohar, November 2002): Let S be a Steiner triple system of order n. If n is large enough, then S can be extended to a triangular embedding of Kn in some nonorientable surface.

By "extending" a STS to an embedding we mean an embedding in which all blocks of the triple system form facial cycles. Exceptional values of n are 3, 4, and 7 for which only orientable embeddings exist. It is possible that these are the only exceptions. 

If true, Conjecture 2 would imply that for all admissible large values of n, there are at least exp(n2 log n / 6 - o(n2)) nonisomorphic triangular embeddings of Kn in nonorientable surfaces.

Conjecture 2 (Ellingham and Mohar, November 2002): Let S and S' be Steiner triple systems of odd order n. If n is large enough, then S and an isomorphic copy of S' form a triangular embedding of Kn in some nonorientable surface.

If true, Conjecture 2 would imply that for all admissible large values of n, there are at least exp(n2 log n / 3 - o(n2)) nonisomorphic triangular embeddings of Kn in nonorientable surfaces such that the dual is bipartite. It is easy to see that this bound would be asymptotically best possible. This would also imply that complete graphs may have the biggest face-width-3 flexibility among all graphs of given genus, a property that has been conjectured by Neil Robertson (private communication) some time ago; see also [2].


References:

[1] P. Bonnington, M. Grannell, T. Griggs, and J. Siran, Exponential families of non-isomorphic triangulations of complete graphs, J. Combin. Theory Ser. B 78 (2000) 169-184.

[2] B. Mohar, N. Robertson, Flexibility of polyhedral embeddings of graphs in surfaces, J. Combin. Theory, Ser. B 83 (2001) 38-57.

[3] G. Ringel, Map Color Theorem, Springer-Verlag, Berlin, 1974.


Some comments added in December 2004:

The above problems concerning nonorientable surfaces were earlier studied by Grannell, Griggs and Siran [6] for orientable surfaces. However, it is known [5] that there is a pair of Steiner triple systems with n = 15 that cannot be embedded together on an orientable surface. But perhaps if n is large enough, arbitrary pairs of Steiner triple systems (satisfying obvious necessary parity conditions) could still be embedded on an orientable surface.

Mark Ellingham informed me that [4] contains an upper bound on the number of triangular embeddings of Kn, based on ideas by R. M. Wilson, that is (very slightly) better than the obvious upper bound of (n-2)n(n-1)/3: the improved bound is (n/e)(n^2)/3. This appears in [4].

[4] M. Ellingham and C. Stephens, Triangular embeddings of complete graphs (neighborly maps) with 12 and 13 vertices, submitted to the Journal of Combinatorial Designs.

[5] G. K. Bennett, M. J. Grannell and T. S. Griggs, On the bi-embeddability of certain Steiner triple systems of order 15, Europ. J. Combin. 23 (2002) 499-505.

[6] M. J. Grannell, T. S. Griggs and J. Siran, Surface embeddings of Steiner triple systems, J. Combin. Designs 6 (1998) 325-336.


Send comments to Bojan.Mohar@uni-lj.si


Revised: December 03, 2004.