Department of
Applied
Mathematics

Distribution of certain types of spanning subgraphs in G(n,p)

Jane Gao

Abstract

The distributions of subgraphs with fixed sizes in various random graph models have been investigated by many authors. A general approach by Ruci\'{n}ski showed that the numbers of subgraphs with fixed sizes in the binomial model $G(n,p)$ are asymptotically normal for a large range of $p$. However, the distributions of subgraphs with growing sizes, for instance, the spanning subgraphs, behave significantly differently.

In this work we describe a general approach of determining the distribution of the number of spanning subgraphs in the random graph $G(n,p)$. In particular, we determine the distribution of the number of $d$-factors, of spanning triangle-free subgraphs, of Hamilton cycles and of spanning subgraphs that are isomorphic to a collection of vertex disjoint triangles.