On the triangle space of a random graph
Bobby DeMarco, Arran Hamm, Jeff Kahn · Journal of Combinatorics · 2013
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 fundamental "stability" theorem for triangle-free subgraphs of G n,p , originally due to Kohayakawa, Luczak and Rödl, that underlies the first of our proofs.