TY - JOUR TI - Triangles in random graphs DO - https://doi.org/doi:10.7282/T3ZS2V7Z PY - 2012 AB - We prove four separate results. These results will appear or have appeared in various papers (see [10], [11], [12], [13]). For a gentler introduction to these results, the reader is directed to the first chapter of this thesis. Let G = Gn,p. With ξk = ξn,p k the number of copies of Kk in G, p ≥ n−2/(k−1) and η > 0, we show when k > 1 Pr(ξk > (1 + η)Eξk) < exp [ −Ωη,k min{n2pk−1 log(1/p), nkp(k 2)} ] . This is tight up to the value of the constant in the exponent. For a graph H, denote by t(H) (resp. b(H)) the maximum size of a trianglefree (resp. bipartite) subgraph of H. We show that w.h.p. t(G) = b(G) if p > Cn−1/2 log1/2 n for a suitable constant C, which is best possible up to the value of C. We give a new (simpler) proof of a random analogue of the Erd˝os-Simonovits “stability” version of Mantel’s Theorem, viz.: For each η > 0 there is a C such that if p > Cn−1/2, then w.h.p. each triangle-free subgraph of G of size at least |G|/2 can be made bipartite by deletion of at most ηn2p edges. Let C(H) denote the cycle space and T (H) the triangle space of a graph H. We use the previous result to show that if C > √ 3/2 is fixed and p > C √ log n/n, then w.h.p. T (G) = C(G). The lower bound on p is best possible. KW - Mathematics KW - Random graphs KW - Graph theory LA - eng ER -