On the Cycle Space of a Random Graph

Abstract

Write $\mathcal{C}(G)$ for the cycle space of a graph $G$, ${\mathcal{C}}_{\kappa }(G)$ for the subspace of $\mathcal{C}(G)$ spanned by the copies of the $\kappa$-cycle $C_{\kappa }$ in $G$, ${\mathcal{T}}_{\kappa }$ for the class of graphs satisfying ${\mathcal{C}}_{\kappa }(G)=\mathcal{C}(G)$, and ${\mathcal{Q}}_{\kappa }$ for the class of graphs each of whose edges lies in a $C_{\kappa }$. We prove that for every odd $\kappa \ge 3$ and $G=G_{n,p}$, \[\max_p \, \Pr(G \in \mathcal{Q}_κ\setminus \mathcal{T}_κ) \rightarrow 0;\] so the $C_{\kappa }$'s of a random graph span its cycle space as soon as they cover its edges. For $\kappa =3$ this was shown by DeMarco, Hamm and Kahn (2013).

38 pages

References in corpus (1)

• Extremal results in random graphs

Cited by in corpus (1)

• Counting extensions revisited