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 *

August, 1995