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