The Average Genus of a Random Graph 



 Let G be a graph with degrees d_1,….,d_n. It is well-known that the number of different orientable embeddings of the graph on orientable surfaces is Prod((d_i-1)!), where the product is taken over all vertices. Many people have looked at the minimum and maximum genus of these embeddings. We are concerned here with the average genus of these embeddings.

A random graph is one chosen with equal probability among all graphs with a fixed labeled vertex set 1,…,n. The expected value for the minimum genus of a random graph is known; in particular, a random graph has an embedding that is `close’ to a triangulation [AG]. Using permutation-partition pairs, Stahl [S] gives an upper bound on the expected number of faces in a random embedding of a random graph, and then uses this bound to determine that the average genus of a random graph is close to its maximum genus.

We ask for the analogous result for embeddings on nonorientable surfaces.

Conjecture: The average nonorientable genus of a random graph is close to its maximum genus. More specifically, the difference between  average nonorientable genus and the maximum nonorientable genus bounded above by a linear function in the order of the graph.

The model above for a random graph is equivalent to the model where each edge is chosen with probability ˝. What if each edge is chosen with a probability p? Again, the expected value of the minimum genus is known [RT], but to the proposer’s knowledge no one has examined the average genus of such graphs.

References:

[AG] D. Archdeacon and D. Grable, The genus of a random graph, Discrete Math.(need details here)

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

[RT] V. Rodl and R. Thomas, paper on genus with variable probability.


Submitted by: Dan Archdeacon, Dept. of Math. and Stat., University of Vermont, Burlington, VT 05401-1455 USA

Send comments to dan.archdeacon@uvm.edu (with thanks to Saul Stahl).

November 2003