A random graph on n vertices has a fixed vertex set 1,…,n with each edge selected with probability 1/2. That is, we consider the probability space having as equally probable events all 2^{n(n-1)/2} labeled graphs on vertices 1,…,n. We say that a random graph almost always has a property P if the proportion of graphs in P approaches 1 as n approaches infinity.

Conjecture: A random graph almost always has an edge partition into K_4's and K_5's.

I have shown [A] that if a graph has an edge partition into K_4's and K_5's, then it has an orientable self-dual embedding. That is, there is an embedding of G into some orientable surface so that the geometric dual is isomorphic to G^* = G. (These are isomorphic as graphs, the embeddings may be different.) The above conjecture would imply that a random graph almost always has an orientable self-dual embedding.

A weaker conjecture would be that a random graph almost always has an edge partition into some complete graphs. This would still imply that a graph almost always has a self-dual embedding, but not necessarily in an orientable surface (see [A] for a proof of this claim).

I think this conjecture is true but suspect that it is hard. In particular, most techniques in random graph theory are of the flavor ``there are K_4's and K_5's partitioning almost all edges of a random graph''. But I don't know if even that is known.

[A] D. Archdeacon, Self-dual embeddings of complete multipartite graphs, J. Graph Theory.

Submitted by: Dan Archdeacon, Department of Mathematics and Statistics, University of Vermont, Burlington VT 05405 USA.

Send comments to dan.archdeacon@uvm.edu