On the triangle space of a random graph

2012/07/28 by DeMarco, Bobby, Hamm, Arran, Kahn, Jeff · 2 citations
#05C35 #05C80 #05D40 #55U10 #60C05 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1207.6717

Abstract

Settling a first case of a conjecture of M. Kahle on the homology of the clique complex of the random graph G=G_n,p, we show, roughly speaking, that (with high probability) the triangles of G span its cycle space whenever each of its edges lies in a triangle (which happens (w.h.p.) when p is at least about √((3/2)ln n/n), and not below this unless p is very small.) We give two related proofs of this statement, together with a relatively simple proof of a fundamental "stability" theorem for triangle-free subgraphs of G_n,p, originally due to Kohayakawa, Łuczak and Rödl, that underlies the first of our proofs.

Cited by

• On graphs whose cycle space is spanned by their Hamilton cycles
• When does a tree activate the random graph?

Related

• Triangle-free subgraphs of random graphs
• On the H-space of a random graph
• Mantel's Theorem for random graphs
• Long paths and cycles in random subgraphs of H-free graphs
• Random triangles in random graphs