DISTRIBUTIONS OF SPARSE SPANNING SUBGRAPHS IN RANDOM GRAPHS

作者：Gao Pu^*

来源：SIAM Journal on Discrete Mathematics, 2013, 27(1): 386-401.

DOI：10.1137/120866300

• spanning subgraphs
• asymptotic distribution
• Hamilton cycle
• triangle-free subgraphs
• triangle-factors
• switching

We describe a general approach of determining the distribution of the number of certain types of spanning subgraphs in the random graph G(n, p). Using this approach, we reprove the distribution of the number of Hamilton cycles with a proof that is much shorter than previously known proofs. We also achieve new results on determining the distribution of the number of spanning triangle-free subgraphs and the number of triangle-factors.

• 出版日期2013