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