Subgraphs of random k-edge-coloured k-regular graphs
Let G=G(n) be a randomly chosen k-edge-coloured k-regular graph with
2n vertices, where k=k(n). Equivalently, G is the union of a random
set of k disjoint perfect matchings. Let h=h(n) be a graph with
m=m(n) edges such that m2+mk=o(n). Using a switching argument, we
find an asymptotic estimate of the expected number of subgraphs of G
isomorphic to h. Isomorphisms may or may not respect the edge
colouring, and other generalizations are also presented. Special
attention is paid to matchings and cycles.
The results in this paper are essential to a forthcoming paper of
McLeod in which an asymptotic estimate for the number of
k-edge-coloured k-regular graphs for k=o(n5/6) is found.
Last modified: Tue Jan 23 15:29:26 EST 2007