The Expected Number of Regions in a Random Embedding of the Complete Graph

Let r_avg(G) denote the expected number of regions in a randomly selected orientable embbedding of the graph G (two embeddings are considered different iff they have a different rotation at some vertex). Let K_n denote the complete graph on n vertices.

Conjecture: r_avg( K_n ) = 2 ln(n) + O(1).

Lee and White [LW] computed the embedding distributions of K_4, K_5, K_6, as well as their average genus. Bruce Richter [R] asked me about the average genus of K_n, and I expect the same question had occurred to everyone who has worked on the average genus parameter. In [S] I proved that for each epsilon > 0 there exists a real number b(epsilon) such that r_avg(K_n) is at most (1+epsilon)(n-1) + b(epsilon).

The conjecture is supported by a random sampling experiment for the embeddings of K_n for various values of n up to 180 [MS].

References:

[LW] S.H. Lee and A.T. White, Random topological graph theory, Proceedings of the Second International Conference in Graph Theory, Combinatorics, Algorithms, and Applications (Y. Alavi, F.R.K. Chung, R.L. Graham, and D.F. Hsy, Editors) SIAM 1991.

[MS] C. Mauk and S. Stahl, Cubic graphs whose averave number of regions is small, Discrete Mathematics (to

appear).

[R] R.B. Richter, private communication, Fourth Vermont Summer Workshop on Combinatorics and Graph Theory, June 1990.

[S] S. Stahl, On the average genus of the random graph, J. Graph Theory 20 (1995)1-18.

Submitted by: Saul Stahl, Department of Mathematics, University of Kansas, Lawrence KS, USA 66045

Send comments to dan.archdeacon@uvm.edu