**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