On the cycle space of a random graph. Issue 1 (20th July 2018)

• Record Type: Journal Article
• Authors: Baron, Jacob D.; Kahn, Jeff
• Is Part Of: Random structures & algorithms. Volume 54:Issue 1(2019)
• Page Start: 39
• Page End: 68
• Publication Date: 2018-07-20
• Subjects: cycle space -- random graphs -- sparse random graphs; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20785
• Languages: English
• ISSNs: 1042-9832

Abstract

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].