Partitioning into Complete Graphs



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: If a random graph has an even number of edges, then it 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 on four or more vertices. 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. Some related results are in [M,FR].

References:

[A] D. Archdeacon, Self-dual embeddings of complete multipartite graphs, J. Graph Theory 18 (1994) 735-749.

[FR] A. Frieze, B. Reed, Covering the edges of a random graph by cliques, Combin. 15 (1995) 489-497.

[M] S. McGuinness, The greedy clique decomposition of a graph, J. Graph Theory 18 (1994) 427-430.


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

Send comments to dan.archdeacon@uvm.edu

August, 1995. Modified November, 1998, and February 2000