Journal of Combinatorics

Volume 4 (2013)

Number 2

On the triangle space of a random graph

Pages: 229 – 249

DOI: http://dx.doi.org/10.4310/JOC.2013.v4.n2.a4

Authors

B. Demarco (Department of Mathematics, Rutgers University, Piscataway, New Jersey, U.S.A.)

A. Hamm (Department of Mathematics, Rutgers University, Piscataway, New Jersey, U.S.A.)

J. Kahn (Department of Mathematics, Rutgers University, Piscataway, New Jersey, U.S.A.)

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 $\sqrt{(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, Łuczak and Rödl, that underlies the first of our proofs.

Keywords

Kahle’s conjecture, homology of the clique complex, threshold, stability theorem

2010 Mathematics Subject Classification

05C35, 05C80, 05D40, 55U10, 60C05

Full Text (PDF format)