On the cycle space of a random graph. Issue 1 (20th July 2018) - Baron, Jacob D.; Kahn, Jeff
Abstract: Write C ( G ) for the cycle space of a graph G, C κ ( G ) for the subspace of C ( G ) spanned by the copies of the κ‐cycle C κ in G, T κ for the class of graphs satisfying C κ ( G ) = C ( G ), and Q κ for the class of graphs each of whose edges lies in a C κ . We prove that for every odd κ ≥ 3 and G = G n, p, max p Pr ( G ∈ Q κ ∖ T κ ) → 0 ; so the C κ 's of a random graph span its cycle space as soon as they cover its edges. For κ = 3 this was shown in [6].