Constrained graph processes

Béla Bollobás and Oliver Riordan

Department of Mathematical Sciences University of Memphis, Memphis TN 38152

Trinity College, Cambridge CB2 1TQ, England

                 bollobas@msci.memphis.edu, O.M.Riordan@dpmms.cam.ac.uk

Submitted: 25th June 1999; Accepted: 23rd February 2000

Keywords: random graphs MR Subject Code: 05C80

Abstract

Let Q be a monotone decreasing property of graphs G on n vertices. Erdős, Suen and Winkler [5] introduced the following natural way of choosing a random maximal graph in Q: start with G the empty graph on n vertices. Add edges to G one at a time, each time choosing uniformly from all e ∈ G^{c} such that G + e ∈ Q. Stop when there are no such edges, so the graph G_{∞} reached is maximal in Q. Erdős, Suen and Winkler asked how many edges the resulting graph typically has, giving good bounds for Q = {bipartite graphs} and Q = {triangle free graphs}. We answer this question for C_{4}-free graphs and for K_{4}-free graphs, by considering a related question about standard random graphs G_{p} ∈ G(n, p).

The main technique we use is the ‘step by step’ approach of [3]. We wish to show that G_{p} has a certain property with high probability. For example, for K_{4} free graphs the property is that every ‘large’ set V of vertices contains a triangle not sharing an edge with any K_{4} in G_{p}. We would like to apply a standard Martingale inequality, but the complicated dependence involved is not of the right form. Instead we examine G_{p} one step at a time in such a way that the dependence on what has gone before can be split into ‘positive’ and ‘negative’ parts, using the notions of up-sets and down-sets. The relatively simple positive part is then estimated directly. The much more complicated negative part can simply be ignored, as shown in [3].

1 Introduction

A property R of graphs on n vertices is called monotone increasing (monotone decreasing) if it is preserved by the addition (deletion) of edges. Let V be a fixed set of n vertices, and let N = \binom{n}{2}. A standard random graph process on V is a random sequence G̃ = (G_{t})_{0}^{N} of graphs on V, where G_{t−1} ⊂ G_{t}, e(G_{t}) = t, and all N! such sequences are taken equally likely. A basic question in the theory of random graphs is when does a monotone increasing property R arise in such a process. More precisely, one would like to know as much as possible about the distribution of the hitting time τ_{R}(G̃), the minimum t such that G_{t} ∈ R (see, e.g., [1]).

Here we shall consider monotone decreasing properties Q, and one could consider similarly the leaving time σ_{Q}(G̃) = τ_{Q^{c}}(G̃) − 1, and the random graph G = G_{σ_{Q}(G̃)} ∈ Q.

We wish to consider random maximal graphs in a monotone decreasing property Q. The maximal graphs in Q are of interest both from the point of view of extremal combinatorics, and because they may provide a relatively compact description of the entire property Q. Note that the random G ∈ Q described above does satisfy G + e ∉ Q for some edge e, but need not be a maximal element of Q.

At first sight the most natural measure on maximal G ∈ Q is the uniform one. Another natural possibility would be taking the probability of G proportional to \binom{N}{e(G)}^{−1}. However, both these measures are rather intractable in general—generating a random sample from either seems difficult, as we do not know how many G ∈ Q are maximal, or the distribution of the number of edges of such graphs.

In [5] Erdős, Suen and Winkler introduced a rather different measure on the set of maximal G ∈ Q. This is also very natural, and is defined in terms of the ‘greedy algorithm’ for generating maximal G ∈ Q, and so is easy to sample in practice. The procedure for constructing a random maximal G_{∞} ∈ Q with this measure is as follows. Start with G the empty graph on n vertices. Add edges to G one by one, at each stage choosing uniformly from among all edges e ∈ G^{c} such that G∪{e} ∈ Q. Stop when there are no such edges, i.e., when the graph G_{∞} reached is a maximal graph in Q. From now on when we refer to a random maximal graph from Q we are using this definition. Note that it is very different from any of the other models for random graphs from Q described above.

In [5] Erdős, Suen and Winkler asked the general question of how many edges G_{∞} has on average. For the case Q = {bipartite graphs} they gave a very precise answer, and for Q = {triangle free graphs} the answer to within a log n factor. Here we give answers within powers of log n for the cases of C_{4}-free graphs and K_{4}-free graphs, using the ‘step by step’ methods of [3].

For convenience we shall not work with the process above, but with an equivalent one, G̃_{Q} = (G_{Q}(t))_{0}^{N}, also used in [5]. Fix a set V of n vertices. Let N = \binom{n}{2}, and let e_{1}, …, e_{N} be all elements of V^{(2)}, listed in a uniformly chosen random order. Let G_{Q}(0) = ∅. For 1 ≤ t ≤ N let

G_{Q}(t) = \{ \begin{matrix}G_{Q}(t − 1) ∪ \{e_{t}\} & if G_{Q}(t − 1) ∪ \{e_{t}\} ∈ Q \\ G_{Q}(t − 1) & otherwise, \end{matrix}

and let G_{∞} = G_{Q}(N). This definition is equivalent to the description above, where the edge to be added was chosen from all e ∉ G such that G + e ∈ Q. The reason is that if we do not add the edge e_{t} at stage t, we have G_{Q}(s) ∪ {e_{t}} ∉ Q for all s ≥ t, so we never need to consider adding the edge e_{t} at a later stage.

We shall couple G_{Q}(t) with two processes that are easier to analyze, and which approximate G_{Q}(t). For 0 ≤ t ≤ N let G_{0}(t) = (V, {e_{i}, i ≤ t}), so e(G_{0}(t)) = t, and (G_{0}(t))_{t=0}^{N} is a standard random graph process with G_{Q}(t) ⊂ G_{0}(t). Let M(Q^{c}) consist of all the minimal elements of Q^{c}, so G ∉ Q if and only if G contains some graph in M(Q^{c}). In the cases we consider, Q is all graphs not containing a copy of some fixed graph H, so M(Q^{c}) just consists of all copies of H on V. Let G′_{Q}(t) consist of those edges e of G_{0}(t) which are not contained in some F ⊂ G_{0}(t) with F ∈ M(Q^{c}). Then we have G′_{Q}(t) ⊂ G_{Q}(t)—indeed if e = e_{s} ∈ G_{0}(t) \ G_{Q}(t) then because e was not added at stage s, there is a graph F ⊂ G_{Q}(s − 1) ∪ {e_{s}} with F ∈ M(Q^{c}). But then F ⊂ G_{0}(s) ⊂ G_{0}(t), so e ∉ G′_{Q}(t).

In fact we shall not work with graph processes at all, but rather with a random graph G_{p} ∈ G(n, p) chosen by joining each pair of vertices independently with probability p. We obtain a graph G′_{p} from G_{p} by deleting any edge contained in some F ⊂ G_{p} with F ∈ M(Q^{c}). We can couple the random variables G_{p}, G′_{p} with the processes above: let T ∼ Bi(N, p). Then the graph G_{0}(T) is a random graph G_{p} from G(n, p) with the correct distribution. Also, the graph G′_{Q}(T) has the correct distribution for G′_{p}. Since every G′_{Q}(t) is contained in G_{Q}(t) and thus G_{∞}, we have G′_{p} ⊂ G_{∞}. This is all we shall use from now on, not only for lower bounds but, somewhat surprisingly, even to get upper bounds on e(G_{∞}).

In vague terms, as p increases from 0 to 1 the graphs G′_{p} first get larger, and then smaller again. We shall show that, in the cases we consider, G_{∞} is not much larger than the largest G′_{p}. We suspect that this holds in many other cases, though it is not at all true for Q = {bipartite graphs}, for example.

The rest of the paper is organized as follows. In §2 we state our main results, giving probabilistic upper and lower bounds on e(G_{∞}) for the properties {G is C_{4}-free} and {G is K_{4}-free}. In §3 we give the simple proof of the lower bound. In §4 we quote two basic lemmas needed in the rest of the paper. In §5 we prove a lemma concerning the number of copies of a fixed graph H containing some edge xy ∈ G_{p}. This lemma, which is used in both the subsequent sections, is likely to be of interest in its own right. In §6 we give the upper bound for C_{4}-free graphs, and in §7 that for K_{4}-free graphs. In the final section we briefly discuss possible generalizations.

Throughout the paper we shall assume that the number n of vertices is larger than some very large fixed n_{0}, even when this is not explicitly stated. We shall use the notation f = O(g) to mean that f/g is bounded for n ≥ n_{0}, f = Θ(g) to mean f = O(g) and g = O(f), and f = O^{∗}(g) to mean that f = O((log n)^{k}g) for some fixed k.

2 Results

Throughout we take Q to be Q_{H}, the set of H-free graphs with vertex set V = [n] = {1, 2, …, n}, i.e., the set of graphs on V not containing a copy (induced or otherwise) of a fixed graph H. We shall consider the cases H = C_{4} and H = K_{4}. Parts of the argument are the same for both cases, and work for a much larger class of graphs, which we now describe.

Let H be a fixed graph. For 0 ≤ v < |H| let e_{H}(v) be the maximum number of edges spanned by v vertices of H. Let

α_{H}(v) = \frac{e(H) − e_{H}(v)}{|H| − v}.

We say that H is edge-balanced if H is connected, |H| ≥ 3, and α_{H}(v) > α_{H}(2) for 2 < v < |H|. Writing aut(H) for the number of automorphisms of H, we shall prove the following lower bound on e(G′_{p}) when G′_{p} is defined with respect to Q_{H}.

Theorem 1. Let H be a fixed edge-balanced graph, λ and ϵ positive constants, and

p = λn^{− \frac{|H|−2}{e(H)−1}} .

Then with G′_{p} defined as above with respect to Q = Q_{H},

ℙ (e(G′_{p}) < (1 − ϵ) (\frac{λ}{2} − \frac{λ^{e(H)}e(H)}{aut(H)}) n^{2− \frac{|H|−2}{e(H)−1}} ) = o(1),

as n → ∞.

This has the following immediate corollary.

Corollary 2. Let H be a fixed edge-balanced graph, and let G_{∞} be a random maximal H-free graph. Then there is a constant c = c(H) > 0 such that

ℙ (e(G_{∞}) < cn^{2− \frac{|H|−2}{e(H)−1}} ) = o(1),  (1)

and 𝔼 e(G_{∞}) ≥ (c/2)n^{2− \frac{|H|−2}{e(H)−1}} .

Proof. The second statement follows from the first as e(G_{∞}) ≥ 0. For the first, we have G_{∞} ⊃ G′_{p} for all p. Taking ϵ = \frac{1}{2}, say, and λ = (aut(H)/4e(H))^{1/(e(H)−1)}, Theorem 1 implies (1) with c = λ/8.

In the other direction we shall prove the following results for H = C_{4} and H = K_{4}, writing Δ(G) for the maximum degree of G.

Theorem 3. For G_{∞} a random maximal C_{4}-free graph we have

ℙ (Δ(G_{∞}) > 13(log n)^{3}n^{1/3}) = o(n^{−2}).

In particular,

ℙ (e(G_{∞}) > 7(log n)^{3}n^{4/3}) = o(n^{−2}),

and 𝔼 e(G_{∞}) ≤ 8(log n)^{3}n^{4/3}.

Theorem 4. There is a constant C such that for G_{∞} a random maximal K_{4}-free graph we have

ℙ (Δ(G_{∞}) > 2C(log n)n^{3/5}) = o(n^{−2}).

In particular,

ℙ (e(G_{∞}) > C(log n)n^{8/5}) = o(n^{−2}),

and 𝔼 e(G_{∞}) ≤ 2C(log n)n^{8/5}.

Note that 2 − \frac{|H|−2}{e(H)−1} is equal to \frac{4}{3} for H = C_{4}, and to \frac{8}{5} for H = K_{4}, so by Corollary 2 in these cases we have found e(G_{∞}) to within a log factor for almost every G_{∞}. In fact our proofs of Theorems 3 and 4 give error bounds smaller than n^{−k} for any fixed k, and possibly even n^{−δ log n} for δ > 0 small enough.

In the next section we give the straightforward proof of Theorem 1. The heart of the paper is the proofs of the upper bounds.

3 Proof of the lower bound

We shall use Janson’s inequality [6] in the following form. Let H be a fixed graph, and V a set of n vertices. Let H_{1}, …, H_{h} be all copies of H with vertices in V, so h = (n)_{|H|}/ aut(H). Let X = X_{H}(G_{p}) be the number of copies of H present in G_{p}, so μ = 𝔼 X = hp^{e(H)}, and let

Δ = ∑_{e(H_{i}∩H_{j})>0} ℙ(H_{i} ∪ H_{j} ⊂ G_{p}).

Then for γ > 0,

ℙ(X ≤ (1 − γ)μ) < e^{− \frac{γ^{2}μ}{2+2Δ/μ}} ,  (2)

and for ϵ > 0,

ℙ(X ≥ (1 + ϵ)μ) ≤ \frac{γ + e^{−γ^{2}μ/(2+2Δ/μ)}}{ϵ} .  (3)

Note that (2) implies (3) as

μ ≥ (1 − γ)μ ℙ(X ≥ (1 − γ)μ) + ϵμ ℙ(X ≥ (1 + ϵ)μ)).

Proof of Theorem 1. The graph G′_{p} is formed from G_{p} by deleting the edges of each copy of H in G_{p}, so e(G′_{p}) ≥ e(G_{p}) − e(H)X, where X = X_{H}(G_{p}). Writing N for \binom{n}{2},

𝔼 e(G_{p}) = pN ∼ \frac{λ}{2}n^{2− \frac{|H|−2}{e(H)−1}} ,

while

μ = 𝔼 X ∼ \frac{λ^{e(H)}}{aut H} n^{2− \frac{|H|−2}{e(H)−1}} ,

so it suffices to show that

e(G_{p}) ≥ (1 − o(1)) 𝔼 e(G_{p})  (4)

and

X ≤ (1 + o(1))μ  (5)

hold with probability 1 − o(1).

As pN → ∞, (4) is immediate from standard binomial bounds. For (5) we use Janson’s inequality. Consider one particular copy H_{1} of H on V. Then by symmetry

Δ ≤ hp^{e(H)} ∑_{i:e(H_{i}∩H_{1})>0} ℙ(H_{i} ⊂ G_{p} | H_{1} ⊂ G_{p}).

Writing K for the complete graph on the vertex set of H_{1} we thus have

Δ ≤ μ ∑_{i:V (H_{i}∩K)≥2} ℙ(H_{i} ⊂ G_{p} | K ⊂ G_{p}).

We can choose H_{i} by deciding v, the number of vertices to take from K, which v vertices to take from K, which |H| − v vertices outside K to take, and how to arrange H_{i} on these |H| vertices. As H_{i} has at least e(H) − e_{H}(v) edges outside K, we have

Δ ≤ μ ∑_{v=2}^{|H|} \binom{|H|}{v}\binom{n}{|H| − v}|H|!p^{e(H)−e_{H}(v)}

= O (μ ∑_{v=2}^{|H|} n^{|H|−v}p^{e(H)−e_{H}(v)}) .

For v = 2 or v = |H| the summand above is O(1). Also, as H is edge-balanced, for 2 < v < |H| we have

(e(H) − e_{H}(v))\frac{|H| − 2}{e(H) − 1} > |H| − v,

so the remaining terms of the sum are all o(1). Thus Δ = O(μ). Now fix ϵ > 0 and set γ = ϵ^{2}. Since Δ = O(μ) and μ → ∞, inequality (3) implies that

ℙ(X ≥ (1 + ϵ)μ) ≤ \frac{ϵ^{2} + o(1)}{ϵ},

which is less than 2ϵ for n large. As ϵ was arbitrary, (5) holds almost surely, completing the proof.

Note that Theorem 1 can be strengthened in two ways. We can remove the factor e(H) from the term λ^{e(H)}e(H)/ aut(H) if we define G′_{p} by deleting only one edge from each copy of H in G_{p}. Choosing this edge to be the last edge in a random order on V^{(2)}, we can still couple this larger G′_{p} with G_{∞} so that G′_{p} ⊂ G_{∞}. Independently, we can obtain much smaller error probabilities (for example n^{−k} for any fixed k) by using the Azuma-Hoeffding inequality together with Lemma 8 from §4.

4 Basic lemmas

In the rest of the paper we shall need the following results: Janson’s inequality (2), some standard bounds concerning the binomial distribution, and a lemma from [3] concerning up-sets and down-sets. To bound the tail of the binomial distribution we use the following lemma from [3], itself an immediate consequence of the Chernoff bounds [4] (see also [1], p.11).

Lemma 5. Let X be a Bi(n, p) random variable, with 0 < p ≤ \frac{1}{2}. Then

(a)  ℙ(X < \frac{1}{2}pn) < (\frac{2}{e})^{\frac{pn}{2}} < e^{− \frac{pn}{8}} ,

and if k ≥ 1 and \frac{pn}{k} < e^{−2} then

(b)  ℙ(X > k) < (\frac{epn}{k})^{k} < e^{−k}.

The main tool in the proofs of Theorems 3 and 4 will be the ‘step by step’ approach of [3], making use of up-sets and down-sets. An up-set U on a set W is a collection of subsets of W such that A ∈ U and A ⊂ B ⊂ W imply B ∈ U. A down-set D is one where A ∈ D and B ⊂ A imply B ∈ D. In the graph context, W is just the set V^{(2)} of possible edges.

We wish to check that G_{p} satisfies a certain rather complicated condition with very high probability. We do this by considering a (completely impractical) algorithm which checks whether G_{p} satisfies this condition ‘a bit at a time’. At each stage the algorithm tests whether the edges in a certain set E are all present in G_{p}, basing its subsequent behaviour on the yes/no answer. We design the algorithm so that the event A that the algorithm reaches any particular state has the form A = U ∩ D, where U is a very simple up-set, and D is some down-set. We can then bound the probability that E ⊂ G_{p} given A using the following lemma from [3], itself a simple consequence of Kleitman’s Lemma [7], which states that up-sets are positively correlated (see also [2], §19).

Lemma 6. Let p = (p_{1}, …, p_{N}), where each p_{i} lies between 0 and 1. Let Q_{p} be the weighted cube, i.e., the probability space with underlying set P([N]) where a random subset X ⊂ W = [N] is obtained by selecting elements of W independently, with ℙ(i ∈ X) = p_{i}, i = 1, …, N. Let U_{1} and U_{2} be up-sets with ℙ(U_{1} ∩ U_{2}) = ℙ(U_{1}) ℙ(U_{2}) and let D be a down-set. Then

ℙ(U_{1} ∩ U_{2} ∩ D) ≤ ℙ(U_{1}) ℙ(U_{2} ∩ D).

For the rest of the paper we work with the probability space G(n, p) of graphs on a fixed vertex set V. In this context an up-set (down-set) is just a monotone increasing (decreasing) property of graphs on V. Note that we shall not distinguish sets A of graphs on V from the corresponding events {G_{p} ∈ A}. With this notation the most convenient form of Lemma 6 is the following.

Lemma 7. Let G_{p} be a random graph from G(n, p), let A, B be fixed graphs on V and let D be a down-set. Then

ℙ(G_{p} ⊃ B | {G_{p} ⊃ A} ∩ D) ≤ p^{e(B\A)}.

Proof. We identify G(n, p) with the weighted cube Q_{p}, where W = [N], N = \binom{n}{2}, and all p_{i} are equal to p. Let U_{1} = {G_{p} ⊃ B \ A}, U_{2} = {G_{p} ⊃ A}, so U_{1}, U_{2} are independent up-sets. From Lemma 6 we have

ℙ(G_{p} ⊃ B | {G_{p} ⊃ A} ∩ D) = ℙ(G_{p} ⊃ B \ A | {G_{p} ⊃ A} ∩ D)
≤ ℙ(G_{p} ⊃ B \ A) = p^{e(B\A)},

as required.

In the next section we present an application of this lemma common to the cases H = C_{4} and H = K_{4}, and in fact much more general.

5 Subgraphs containing a given edge

In this section we shall show that if H is edge-balanced, then copies of H containing a particular edge of G_{p} arise ‘more or less independently’.

For x, y ∈ V (G_{p}), let H(x, y) be the set of graphs S on V such that xy ∉ S and S ∪ {xy} is isomorphic to H. Let U_{H}(G_{p}, x, y) be the union of all subgraphs S of G_{p} with S ∈ H(x, y), and let X_{H}(G_{p}, x, y) be the number of such subgraphs S. Thus for H = C_{4}, the graph U_{H}(G_{p}, x, y) is the union of all x-y paths of length three in G_{p}, and X_{H}(G_{p}, x, y) is the number of such paths; if the edge xy is present in G_{p}, then U_{H}(G_{p}, x, y) is the union of all C_{4}s in G_{p} containing xy, and X_{H}(G_{p}, x, y) the number of such C_{4}s. As before we write X_{H}(G_{p}) for the total number of copies of H in G_{p}, and N for \binom{n}{2}.

Lemma 8. Let H be a fixed edge-balanced graph. Suppose that p = p(n) is chosen such that

𝔼(X_{H}(G_{p})) = λpN,

with λ = λ(n) bounded as n tends to infinity. Then with probability 1 − o(n^{−2}) we have (i) e(U_{H}(G_{p}, x, y)) ≤ log n for all x, y ∈ V (G_{p}), and (ii) X_{H}(G_{p}, x, y) ≤ log n for all x, y ∈ V (G_{p}).

Proof. Fix distinct vertices x, y ∈ V, and consider H = H(x, y). Note that we shall never consider graphs with isolated vertices, so we may identify a graph S with the set E of its edges.

The idea of the proof is as follows. It is easy to bound the maximum number X_{0} of disjoint E ∈ H present in G_{p}. We consider an algorithm for finding U_{H}(G_{p}, x, y) that proceeds as follows. First find H_{0} ⊂ G_{p}, where H_{0} is a union of X_{0} disjoint E ∈ H, E ⊂ G_{p}. We will define a random variable M_{t} ⊂ G_{p}, the set of ‘marked edges’, starting with M_{0} = H_{0}. The variable M_{t} will represent the set of edges known to be present in G_{p} after t steps of the algorithm. At each step the algorithm considers an E ∈ H not yet considered, and tests whether E ⊂ G_{p}. If so, the edges of E are also marked. Thus U_{H}(G_{p}, x, y) is the set of edges marked when we have considered all E ∈ H. The key point is that the event that the algorithm reaches a particular state will be such that we can apply Lemma 7. This will give an upper bound on the conditional probability that E ⊂ G_{p} at each stage.

Note that we expect H_{0} to be almost all of U_{H}(G_{p}, x, y). The reason is that H is edge-balanced. This means that the increase in the conditional probability that E ⊂ G_{p} due to E containing marked edges is outweighed by the reduction in the number of choices for such E ∈ H—such E must share at least three vertices (including x and y) with the marked edges.

In what follows we often consider both a random subgraph of G_{p}, and possible values of this subgraph. We shall use bold type for the former, and italics for the latter. Thus H_{0} ⊂ G_{p} will be a random variable, and H_{0} will represent any possible value of this random variable. We now turn to the proof itself.

As described above we first consider disjoint sets E ∈ H. For each E ∈ H the probability that E ⊂ G_{p} is p^{e(H)−1}. Thus, counting the expectation of e(H)X_{H}(G_{p}) in two different ways, we have e(H)λpN = e(H) 𝔼 X_{H}(G_{p}) = pN|H|p^{e(H)−1}. Writing X_{0} = X_{0}(G_{p}, x, y) for the maximum number of disjoint E ∈ H contained in G_{p}, we have

ℙ(X_{0} ≥ C) ≤ \binom{|H|}{C}p^{C(e(H)−1)}

≤ (\frac{e|H|p^{e(H)−1}}{C} )^{C} = (\frac{eλe(H)}{C})^{C} = o(n^{−4}),

if C ≥ log n/2e(H), since then eλe(H)/C ≤ e^{−9e(H)}, for n large. We thus have

ℙ(X_{0} ≥ log n/2e(H)) = o(n^{−4}).  (6)

In order to start the algorithm described above we need an event to condition on which is in a suitable form for Lemma 7. Let A_{1}, A_{2}, …, A_{k} = ∅ be all edge sets that are disjoint unions of sets E ∈ H. We order the A_{i} so that their sizes decrease, but otherwise arbitrarily. Let H_{0} = H_{0}(G_{p}) be the subgraph of G_{p} defined by E(H_{0}) = A_{i} for i = min{j : A_{j} ⊂ G_{p}}. Then E(H_{0}) is the union of a largest collection of disjoint E ∈ H, E ⊂ G_{p}, so e(H_{0}) = X_{0}(e(H) − 1). Thus, from (6),

ℙ(|H_{0}| > log n) = o(n^{−4}).  (7)

Note that the event {H_{0} = A_{i}} is of the form {A_{i} ⊂ G_{p}} ∩ D, where D = ⋂_{j<i}{A_{j} ⊄ G_{p}} is a down-set. This is needed in the analysis of the algorithm outlined at the start of the proof, which we now describe precisely.

Enumerate the sets E ∈ H in an arbitrary way, so H = {E_{1}, E_{2}, …, E_{h}}. Set M_{0} = H_{0}, n_{0} = 0, and for 1 ≤ t ≤ h define M_{t}, n_{t} by

M_{t} = \{ \begin{matrix}M_{t−1} & if E_{t} ⊄ G_{p} \\ M_{t−1} ∪ E_{t} & if E_{t} ⊂ G_{p} \end{matrix}
n_{t} = \{ \begin{matrix}n_{t−1} & if M_{t} = M_{t−1} \\ n_{t−1} + 1 & otherwise. \end{matrix}

Thus n_{t} = n_{t−1} unless E_{t} ⊂ G_{p} and E_{t} ⊄ M_{t−1}. Now the event that H_{0} = A_{i} and M_{t} = M ⊃ A_{i} is the event

{M ⊂ G_{p}} ∩ ⋂_{j<i}{A_{j} ⊄ G_{p}} ∩ ⋂_{s<t:E_{s}⊄M}{E_{s} ⊄ G_{p}},

which is of the form {M ⊂ G_{p}} ∩ D, where D is a down-set. Lemma 7 thus tells us that for any possible H_{0} and M, and any E ⊂ V^{(2)}, we have

ℙ(E ⊂ G_{p} | H_{0} = H_{0}, M_{t} = M) ≤ p^{e(E\M)}.

Considering the first t for which n_{t} ≥ s shows that the event that H_{0} = H_{0} and n_{h} ≥ s is a disjoint union of events of the form

A = {H_{0} = H_{0}, M_{t} = M},

where 0 ≤ t ≤ h, and M is a union of H_{0} and s sets E ∈ H, so e(M) ≤ e(H_{0}) + se(H). Given such an A, we have n_{h} ≥ s + 1 if and only if there is some E ⊂ G_{p} with E ∈ H and E ⊄ M. Any such E must meet H_{0} ⊂ M, from the definition of H_{0}. We thus have

p_{s,A} = ℙ(n_{h} ≥ s + 1 | A) ≤ ∑ ℙ(E ⊂ G_{p} | A) ≤ ∑ p^{e(E\M)},

where the sums are over E ∈ H with E ⊄ M and E ∩ M ≠ ∅. We split this sum according to the number v of vertices that E shares with M, noting that e(E \ M) ≥ e(H) − e_{H}(v) if v < |H|, while in any case e(E \ M) ≥ 1. This gives, being very generous,

p_{s,A} ≤ |M|^{|H|}p + ∑_{v=3}^{|H|−1} |M|^{v}n^{|H|−v}p^{e(H)−e_{H}(v)}.

Suppose that |M| = n^{o(1)}. Since n^{|H|−2}p^{e(H)−1} = Θ(λ) ≤ n^{o(1)}, and α_{H}(v) > α_{H}(2) for 2 < v < |H|, there is a positive ϵ such that every term in the above sum is bounded by n^{−2ϵ}, say, taking n sufficiently large. Thus p_{s,A} < n^{−ϵ}. Since this holds for every A we are almost done: for every H_{0} with |H_{0}| = n^{o(1)} we have for s = n^{o(1)} that

ℙ(n_{h} ≥ s + 1 | n_{h} ≥ s, H_{0} = H_{0}) ≤ n^{−ϵ},

and hence that

ℙ(n_{h} ≥ 5/ϵ | H_{0} = H_{0}) = o(n^{−4}).

Now this holds for every H_{0} with |H_{0}| = n^{o(1)}, so using (7) we obtain

ℙ(n_{h} ≥ 5/ϵ) = o(n^{−4}).  (8)

Recalling that U_{H}(G_{p}, x, y) is the union of H_{0} and n_{h} sets E ∈ H we have

e(U_{H}(G_{p}, x, y)) ≤ (e(H) − 1)(X_{0} + n_{h}),

and from (6) and (8),

ℙ(e(U_{H}(G_{p}, x, y)) ≥ log n) = o(n^{−4}).

As this holds for all x and y ∈ V (G_{p}), we have proved part (i) of the lemma.

For the second part we decompose H_{0} as H_{1} ∪ H_{2}, where H_{1} is the union of those E ∈ H, E ⊂ H_{0} that share no edge with any other E ∈ H, E ⊂ G_{p}, and H_{2} = H_{0} \ H_{1}. Thus the sets E ∈ H, E ⊂ H_{0} are all disjoint from each other, but those contained in H_{2} each meet some E′ ∈ H with E′ ⊂ G_{p}. Since any E′ ∈ H, E′ ⊂ G_{p} is by definition contained in U_{H}(G_{p}, x, y), we have that each of the E ∈ H, E ⊂ H_{2} shares an edge with U_{H}(G_{p}, x, y) \ H_{0}, which consists of at most n_{h}(e(H) − 1) edges. Since the sets E are edge disjoint, we have e(H_{2}) ≤ n_{h}(e(H) − 1)^{2}. Now any E ∈ H, E ⊂ G_{p} is either one of at most X_{0} disjoint such sets in H_{1} ⊂ H_{0}, or is formed from edges of U_{H}(G_{p}, x, y) \ H_{1} = H_{2} ∪ (U_{H}(G_{p}, x, y) \ H_{0}). Thus,

X_{H}(G_{p}, x, y) ≤ X_{0} + \binom{n_{h}(e(H) − 1)^{2} + n_{h}(e(H) − 1)}{e(H)},

which, with probability 1 − o(n^{−4}), is at most X_{0} plus a large constant depending on H. Together with (6) this completes the proof of the lemma.

Remarks. (i) In the particular cases H = C_{4} and H = K_{4}, Lemma 8 can be proved much more simply. We give the proof above for two reasons: it is much more general, and it gives a simple illustration of the techniques used in the rest of the paper.

(ii) The same proof works with 𝔼 X_{H}(G_{p}) = λpN where λ → ∞, as long as λ < n^{ϵ} for some ϵ > 0 depending on H. Also, the probability that e(U_{H}(G_{p}, x, y)) exceeds its expectation by a factor C can be bounded by 2 (\frac{e}{C} )^{C} for C up to n^{ϵ}. Thus copies of H containing xy do arise ‘almost independently’ in a rather strong sense.

(iii) Essentially the same proof can be applied to copies of H ⊂ G_{p} containing a particular set of k vertices, with 0 ≤ k < |H|. The edge-balanced condition must be replaced by α_{H}(v) > α_{H}(k) for |H| > v > k. A weak form of the special case H = K_{r} was Lemma 13 of [3]. Note that the condition on α_{H} is necessary, otherwise once we find a suitable K_{k+1} in G_{p} we find many more copies of H than expected.

6 The upper bound for C_{4}-free graphs

In this section we prove Theorem 3. Throughout the section we take p = \frac{1}{2}n^{−2/3}, m = ⌊n^{1/3}(log n)^{3}⌋, and G_{p} a random graph from G(n, p). As before, the graph G′_{p} is formed from G_{p} by deleting any edge contained in a C_{4} in G_{p}. Recall that we shall always assume that n is larger than some very large fixed n_{0}, even when this is not explicitly stated. The result we shall actually prove is the following.

Lemma 9. With probability 1−o(n^{−2}) the graph G_{p} is such that every C_{4}-free graph G′′ ⊃ G′_{p} has maximum degree at most 13m.

This implies Theorem 3 since, using the coupling described in the introduction, G_{∞} is a C_{4}-free graph containing G′_{p}.

The condition described in Lemma 9 is rather complicated when we express it in terms of G_{p}, which we need to do in order to calculate. We start by establishing some global properties of G_{p} that hold almost surely. Then we shall finish with the ‘step by step’ approach described in §4. Most of the time we shall work with G_{p} itself, rather than with G′_{p}. Thus, any graph theoretic notation we use, such as Γ(x) for the set of neighbours of x, or d(x) for the degree of x, will refer to the graph G_{p} unless explicitly stated otherwise.

As before, we write V for V (G_{p}), a fixed set of n vertices. Let B_{1} be the event that some set X ⊂ V with 100 ≤ k = |X| ≤ n^{2/5} spans at least 3k edges of G_{p}. Then we have

ℙ(B_{1}) ≤ ∑_{k=100}^{n^{2/5}} \binom{n}{k}\binom{\binom{k}{2}}{3k}p^{3k}

≤ ∑_{k=100}^{n^{2/5}} (\frac{ne}{k})^{k} (\frac{ke}{6})^{3k} p^{3k}

≤ ∑_{k=100}^{n^{2/5}}(e^{4}nk^{2}p^{3})^{k}.

For k ≤ n^{2/5} we have nk^{2}p^{3} = O(n^{1+4/5−6/3}) = O(n^{−1/5}), so ℙ(B_{1}) = o(n^{−2}).

For a set X ⊂ V let Γ_{2}(X) be the set of vertices y ∉ X with |Γ(y) ∩ X| ≥ 2, recalling that Γ(y) is the set of neighbours of y in the graph G_{p}. For X ⊂ V with |X| = 2m, each y ∉ X has probability p_{0} ≤ \binom{2m}{2}p^{2} ≤ 2m^{2}p^{2} of sending at least two edges to X. These events are independent, so

|Γ_{2}(X)| ∼ Bi(n − 2m, p_{0})

with mean at most np_{0} ≤ 2m^{2}p^{2}n = O^{∗}(m). Thus by Lemma 5(b) we have

ℙ(|Γ_{2}(X)| > mn^{1/100}) ≤ e^{−mn^{1/100}}.

Let B_{2} be the event that some set X ⊂ V with |X| = 2m has |Γ_{2}(X)| > mn^{1/100}. Then

ℙ(B_{2}) ≤ \binom{n}{2m}e^{−mn^{1/100}} ≤ e^{2m log n−mn^{1/100}} = o(n^{−2}).

If neither B_{1} nor B_{2} holds, then every set X with |X| = 13m contains a set of m vertices that is rather well behaved. To formulate this precisely call a set X ⊂ V good if it is an independent set (in G_{p}), and every x ∈ X sends at most n^{1/50} edges (of G_{p}) to Γ_{2}(X).

Lemma 10. Suppose that neither B_{1} nor B_{2} holds, X_{0} ⊂ V and |X_{0}| = 13m. Then X_{0} contains a good set X with |X| = m.

Proof. As B_{1} does not hold, every Y ⊂ X_{0} with 100 ≤ |Y | ≤ n^{2/5} induces a graph G_{p}[Y] with minimum degree less than 6. We may thus number the vertices of X_{0} as x_{1}, x_{2}, … so that each of the first 13m−100 ≥ 12m vertices x_{i} sends at most 5 edges to later x_{j}. We can properly colour G_{p}[X_{0}] as follows: colour the last m vertices arbitrarily, and proceed backwards, colouring x_{i} with one of the colours 1 to 6 which does not appear among its later neighbours. One of the colour classes 1 to 6 in this colouring has at least 12m/6 = 2m vertices, so we have found X_{1} ⊂ X_{0} spanning no edges of G_{p}, with |X_{1}| = 2m.

We claim that there is a set X ⊂ X_{1} with |X| = m, such that each x ∈ X sends at most n^{1/50} edges to Γ_{2}(X). Such an X would be a suitable good set. Suppose that the claim is false. For any X ⊂ X_{1} we have Γ_{2}(X) ⊂ Z = X_{1} ∪ Γ_{2}(X_{1}). More than m vertices of X_{1} must have degree at least n^{1/50} in G_{p}[Z], as we could otherwise take m other vertices of X_{1} to form X. Thus Z spans at least \frac{1}{2}mn^{1/50} edges of G_{p}. As B_{2} does not hold, we have |Z| ≤ 2m + mn^{1/100} ≤ 2mn^{1/100}. But then Z spans more than 3|Z| edges, while 100 ≤ 2m ≤ |Z| ≤ n^{2/5}, contradicting the assumption that B_{1} does not hold, and proving the claim, and hence the lemma.

We shall define two further ‘bad’ events, B_{3} and B_{4}. Let B_{3} be the event that for some edge e = xy ∈ E(G_{p}) the graph U_{C_{4}}(G_{p}, x, y) defined in §4 has more than log n edges. Then by Lemma 8 we have ℙ(B_{3}) = o(n^{−2}).

Given X ⊂ V we shall consider paths xyz ⊂ G_{p} with x, z ∈ X, y ∉ X. We shall need these paths not to share more vertices than necessary; we say that a set A of such paths is independent (with respect to X) if any two paths in A have distinct midpoints, and share at most one endpoint. We write a(X) for the maximum number of paths in such a set A. Let X have size m. We can find a set A as above in the following way: start with A = ∅ and consider each y ∉ X in turn. If y is joined to exactly two vertices x, z of X, and x, z are not the endpoints of a path in A, add xyz to A and continue to the next y ∉ X. Otherwise just continue. Having found a paths, for each vertex y considered the probability of adding a new path is exactly

(\binom{m}{2} − a) p^{2}(1 − p)^{m−2}.

If a < c_{0} = nm^{2}p^{2}/8 then a ≪ \binom{m}{2}, and as mp = o(1) this probability is at least m^{2}p^{2}/3. As we have n − m vertices to consider, the probability that a(X) < c_{0} is at most the probability that a Bi(n − m, m^{2}p^{2}/3) random variable is less than c_{0}. By Lemma 5(a) this is at most e^{−nm^{2}p^{2}/32}.

Let B_{4} be the event that some set X ⊂ V with |X| = m has a(X) < c_{0}. Then

ℙ(B_{4}) ≤ \binom{n}{m}e^{−nm^{2}p^{2}/32} ≤ e^{m log n−nm^{2}p^{2}/32} = o(n^{−2}),

as nmp^{2} ≫ log n.

The significance of the paths counted by a(X) is shown by the next definition. We say that a set X ⊂ V is unusable if G′_{p} contains two paths x_{1}y_{1}z_{1}, x_{2}y_{2}z_{2} with x_{i}, z_{i} ∈ X and y_{1} ≠ y_{2}. We say that X is usable if it is not unusable. If G′′ ⊃ G′_{p} is C_{4}-free and x ∈ V, then X = Γ_{G′′}(x) must be usable—otherwise there are paths as above in G′_{p} ⊂ G′′ with at least one y_{i} distinct from x. But then xx_{i}y_{i}z_{i} is a C_{4} in G′′. To prove Lemma 9 it thus suffices to show that, with high probability, every set of 13m vertices is unusable.

Recall that a set X ⊂ V is good if X spans no edges of G_{p}, and every x ∈ X sends at most n^{1/50} edges to Γ_{2}(X). We shall show that for a fixed X ⊂ V, |X| = m, we have

ℙ(X is good and usable, ⋂_{i=1}^{4} B_{i}^{c}) = o(n^{−m}).  (9)

The events B_{i}^{c}, 1 ≤ i ≤ 3, and the event that X is good are all down-sets, so we are happy to condition on these events. The event B_{4}^{c} is not a down-set, however, so we must treat this event differently. In particular, instead of (9) we prove the stronger statement

ℙ(X is usable, B_{4}^{c} | X is good ∩ ⋂_{i=1}^{3} B_{i}^{c}) = o(n^{−m}).  (10)

Before turning to the proof of (10) we show that (9), and hence (10), does indeed imply Lemma 9. Suppose that (9) holds, and let B_{5} be the event that there is some X ⊂ V with |X| = m which is good and usable. Then (9) implies that ℙ(B_{5} \ (⋃_{i=1}^{4} B_{i})) = o(\binom{n}{m}n^{−m}) = o(n^{−2}). We have already shown that ℙ(B_{i}) = o(n^{−2}) for i = 1, …, 4, so we have ℙ(⋃_{i=1}^{5} B_{i}) = o(n^{−2}). Suppose now that no B_{i} holds. If X_{0} is a set of 13m vertices, then X_{0} contains a good set X with |X| = m by Lemma 10. If X_{0} is usable, then X is good and usable, contradicting the assumption that B_{5} does not hold. Hence, if no B_{i} holds, no set of 13m vertices is usable. As described above, if G′′ ⊃ G′_{p} is C_{4}-free, then the neighbourhood in G′′ of any vertex x is usable. In summary, if (10) holds, so does (9). Then ℙ(⋃_{i=1}^{5} B_{i}) = o(n^{−2}), and with probability 1 − o(n^{−2}) any C_{4}-free graph G′′ ⊃ G′_{p} has maximum degree less than 13m. To prove Lemma 9, and hence Theorem 3, it thus suffices to prove (10).

Proof of Lemma 9. Fix X ⊂ V with |X| = m. We consider all possible sets A ⊂ X ×(V \X) that are unions of independent paths as described in the definition of a(X). Let A_{1}, A_{2}, … be these sets listed in decreasing order of size, and define a random variable A by A = A_{i} where i = min{j : A_{j} ⊂ G_{p}}. Then A is a largest such set present in G_{p}, and by definition A consists of a(X) independent paths. Our goal is to prove (10); since the event that X is good and ⋂_{i=1}^{3} B_{i}^{c} holds is a disjoint union of events E of the form

E = {A = A, X is good, ⋂_{i=1}^{3} B_{i}^{c}},

it suffices to show that

ℙ(X is usable, B_{4}^{c} | E) = o(n^{−m})  (11)

separately for each E. Note that as

{A = A} = {A ⊂ G_{p}} ∩ ⋂_{j<i}{A_{j} ⊄ G_{p}}

when A = A_{i}, and the events {X is good} and B_{i}^{c}, i ≤ 3 are down-sets, each event E is of the form

E = {A ⊂ G_{p}} ∩ D,  (12)

with D a down-set.

We must prove (11) for each possible event E. Suppose first that the set A that defines E consists of fewer than c_{0} = nm^{2}p^{2}/8 paths. Then E implies that a(X) < c_{0} and hence that B_{4} holds, so (11) holds in this case—the conditional probability is actually zero.

From now on we suppose that A consists of at least c_{0} paths, and that E holds. Let P_{1}, …, P_{c_{0}} be the first c_{0} paths in A in some fixed order. We shall examine each P_{t} in turn, looking for a C_{4} in G_{p} sharing an edge with P_{t}; whenever there is no such C_{4}, the path P_{t} is present in G′_{p}. As before we inductively define a set of ‘marked’ edges, and examine the graph in such a way that at each stage the information we have is that the marked edges are present, and some other ‘negative’ information. This will allow us to use Lemma 7. We now make this precise.

Suppose that the event E holds. Let M_{0} = A. At stage t, 1 ≤ t ≤ c_{0}, we define M_{t} as follows.

1. If M_{t−1} contains a C_{4} sharing an edge with P_{t}, set M_{t} = M_{t−1}; otherwise continue to step 2.

2. If the midvertex of P_{t} lies in n^{1/50} edges of M_{t−1}, set M_{t} = M_{t−1}; otherwise continue to step 3.

3. Form a list E_{t,1}, …, E_{t,ℓ_{t}} of all edge sets E ⊂ V^{(2)} that satisfy E ≅ C_{4}, E ⊄ M_{t−1} and E ∩ P_{t} ≠ ∅. If one of these sets is present in G_{p}, set M_{t} = M_{t−1} ∪ E_{t,i_{t}}, with i_{t} = min{i : E_{t,i} ⊂ G_{p}}; otherwise continue to step 4.

4. Set M_{t} = M_{t−1} and continue to stage t + 1, noting that P_{t} ⊂ G′_{p}.

We shall show that when running this procedure we reach step 3 at least c_{0}/(5 log n) times, and that each time we do, we have at least a 50% chance of proceeding to step 4. This will show that, almost certainly, many P_{t} are present in G′_{p}.

Let n_{i}, i = 1, …, 4, be the number of times we reach step i above, so n_{1} = c_{0} and there are at least n_{4} paths P_{t} in G′_{p}. Suppose that for some particular t we stop at step 1. Then there must be a four-cycle C ⊂ M_{t−1} sharing an edge with P_{t}. As there are no C_{4}s in M_{0} = A (using the independence of the paths), C shares an edge with E_{s,i_{s}} for some s for which we reached step 3. In other words, there is an edge in

P_{t} ∩ ⋃_{xy∈E_{s,is}} U_{C_{4}}(G_{p}, x, y).

But as we assume B_{3} does not hold, each U_{C_{4}}(G_{p}, x, y) has at most log n edges. As the P_{t} are edge disjoint, we stop at step 1 at most 4 log n times for each of the n_{3} possible s, so

n_{2} ≥ c_{0} − 4(log n)n_{3}.

Suppose now that for some particular t we stop at step 2. Then the midpoint y_{t} of P_{t} lies on n^{1/50} edges of M_{t−1} ⊂ M_{c_{0}}. As the y_{t} are distinct this happens at most 2e(M_{c_{0}})/n^{1/50} times. Now as B_{2} does not hold

e(M_{0}) = 2a(X) ≤ 2|Γ_{2}(X)| ≤ 2mn^{1/100}.

Hence, as e(M_{s} \ M_{s−1}) ≤ 3 for all s, we have e(M_{c_{0}}) ≤ 2mn^{1/100} + 3c_{0} = O^{∗}(c_{0}n^{1/100}). Thus n_{2} − n_{3} = O^{∗}(c_{0}n^{−1/100}) = o(c_{0}), and we have

n_{3} ≥ c_{0} − 4(log n)n_{3} − o(c_{0}),

so

n_{3} ≥ \frac{c_{0}}{5 log n},

completing the first part of the argument.

To show that each time we reach step 3 we have a reasonable chance of continuing to step 4 we need to know a little more about the set M_{t}.

For x ∈ X let

S_{1} = {xy ∈ E(M_{c_{0}}) : y ∈ Γ_{2}(X)},
S_{2} = {xy ∈ E(M_{c_{0}}) : y ∉ Γ_{2}(X)}.

We are assuming that X is good, so |S_{1}| ≤ n^{1/50}. For xy ∈ S_{2} the vertex y necessarily has only the one neighbour x in X. This means that xy ∉ M_{0}, so there is a unique t, 1 ≤ t ≤ c_{0}, with xy ∈ M_{t} \ M_{t−1}. For this t we have xy ∈ E = E_{t,i_{t}} ⊂ G_{p}. Using the assumption that X spans no edges of G_{p} we see that E must be of the form xyzw with y, z, w ∉ X. Now E shares an edge with P_{t}, which must be the edge xw. Thus |S_{2}| is at most the number of t for which P_{t} contains x. As X is good, this is at most n^{1/50}. We thus have that for every x and t

d_{M_{t}}(x) ≤ d_{M_{c_{0}}} (x) ≤ |S_{1}| + |S_{2}| ≤ 2n^{1/50}.

Suppose that when considering P_{t} we reach step 3. We claim that the probability that some E_{t,i} is in G_{p} is at most 1/2, given everything we know at that stage. More precisely, let

p_{t} = p_{t}(A, M_{1}, …, M_{t−1}) = ℙ(∃i : E_{t,i} ⊂ G_{p} | E, M_{s} = M_{s} for all s < t).

Then for any possible sequence M_{1}, …, M_{t−1},

p_{t} ≤ ∑_{i=1}^{ℓ_{t}} ℙ(E_{t,i} ⊂ G_{p} | E, M_{s} = M_{s} for all s < t).

If we know M_{s} for s < t then we know which sets E_{s,i} were considered by the algorithm, and which ones are present in G_{p}. In particular we know that M_{t−1} ⊂ G_{p}, and that certain other sets of edges are not contained in G_{p}. Thus from (12) the event E ∩ {M_{s} = M_{s}, s < t} is of the form {M_{t−1} ⊂ G_{p}} ∩ D′, where D′ is a down-set. Hence, from Lemma 7,

p_{t} ≤ ∑_{i=1}^{ℓ_{t}} p^{e(E_{t,i}\M_{t−1})}.  (13)

We split the sum above according to the relationship between E_{t,i} and M_{t−1}, noting that by definition we have E_{t,i} ⊄ M_{t−1}. We write E = E_{t,i} as xyzw with x ∈ X and xy an edge of P_{t}.

For E with E ∩ M_{t−1} = {xy} we have two choices for the edge xy of P_{t}, then at most n choices for each vertex z, w. As e(E \ M_{t−1}) = 3, such terms contribute at most 2n^{2}p^{3} ≤ 1/4 to the sum in (13). As we shall see, this is actually the main term. In fact almost all the work in the proof is to show that the other terms are insignificant.

For E with zw ∈ M_{t−1} we have two choices for the edge xy, at most e(M_{t−1}) = O^{∗}(n^{1/3+1/100}) choices for zw, two ways of completing the C_{4}, and e(E \ M_{t−1}) ≥ 1. Such terms thus contribute at most O^{∗}(n^{1/3+1/100}p) = o(1) to the sum.

For E with E ∩ M_{t−1} = {xy, xw} we have two choices for xy, at most d_{M_{t−1}}(x) ≤ 2n^{1/50} choices for w, and n choices for z. We have e(E \ M_{t−1}) = 2, so such terms contribute at most 4n^{1+1/50}p^{2} = o(1).

For E with E ∩ M_{t−1} = {xy, yz}, since we reached step 3 we have d_{M_{t−1}}(y) ≤ n^{1/50}. Thus such terms contribute at most 2n^{1+1/50}p^{2} = o(1).

Finally for E with E ∩ M_{t−1} = {xy, yz, xw} we have at most 4n^{1/25} choices, so such terms contribute at most 4n^{1/25}p = o(1) to the sum in (13).

Putting all this together, we have that if n is large enough, then p_{t} ≤ 1/2. Thus for each of the n_{3} ≥ c_{0}/(5 log n) times we reach step 3 we have a chance of at least 1/2 of proceeding to step 4. Thus, given E, the distribution of n_{4} stochastically dominates a Bi(⌈c_{0}/(5 log n)⌉, 1/2) distribution. From Lemma 5(a) we have

ℙ(n_{4} < 2 | E) ≤ e^{c_{0}/(80 log n)} = o(n^{−m}),

as c_{0} ≫ m(log n)^{2}. As X usable implies n_{4} < 2, we have thus proved (11). As this holds for all E we have proved (10), and thus (9), completing the proof of the lemma, and hence of Theorem 3.

We now turn to the proof of Theorem 4, which is slightly simpler, but uses many of the same ideas.

7 The upper bound for K_{4}-free graphs

Throughout this section we consider the probability space G(n, p) with p = \frac{1}{2}n^{−2/5}, and write m for ⌊C(log n)n^{3/5}⌋, for some large constant C. As in the previous section we take n larger than some very large fixed n_{0}, even when this is not explicitly stated. We shall redefine the concepts of ‘usable’ and ‘good’, as well B_{1} to B_{4}, keeping a close correspondence with the previous section whenever possible. We first prepare the ground, showing that certain ‘bad’ events have small probability. Then we shall prove Theorem 4 by the ‘step by step’ method.

Let B_{0} be the event that some set X ⊂ V with |X| = m contains 2m edge disjoint K_{4}s. For a fixed X there are \binom{m}{4} ≤ m^{4} possible K_{4}s, and so at most \binom{m^{4}}{2m} ≤ (em^{3})^{2m} choices for the union of 2m edge disjoint ones. Each such union has 12m edges, so the probability that one is present is at most

(em^{3})^{2m}p^{12m} = (em^{3}p^{6})^{2m} = o(n^{−m}),

as m^{3}p^{6} = O^{∗}(n^{−3/5}) = o(n^{−1/2}). Thus

ℙ(B_{0}) ≤ \binom{n}{m}n^{−m} = o(n^{−2}).

By a k-book we mean k triangles sharing a common edge e, the spine of the book. Such a graph has k + 2 vertices and 2k + 1 edges. Let B_{1} be the event that some set X ⊂ V with |X| = 4m contains m 25-books with vertex disjoint spines. Since books with vertex disjoint spines are edge disjoint we have

ℙ(B_{1}) ≤ \binom{n}{4m}(4m)^{27m}p^{51m}
≤ (O(n^{4}m^{27}p^{51}))^{m}
= (O(n^{−1/5}))^{m} = o(n^{−2}).

For a set X ⊂ V let dt(X) be the maximum number of edge disjoint triangles in G_{p}[X]. For X with |X| = 2m we have

ℙ(dt(X) ≥ k) ≤ \binom{\binom{2m}{3}}{k}p^{3k}

≤ \binom{8m^{3}}{k}p^{3k} ≤ (\frac{8em^{3}p^{3}}{k} )^{k} .

As m^{3}p^{3} = O(m(log n)^{2}), taking k = m(log n)^{3} we have

ℙ(dt(X) ≥ m(log n)^{3}) ≤ e^{−m(log n)^{3}} ≤ n^{−2m}.

Let B_{2} be the event that some set X ⊂ V with |X| = 2m has dt(X) ≥ m(log n)^{3}. Then

ℙ(B_{2}) ≤ \binom{n}{2m}n^{−2m} = o(n^{−2}).

This time we say that a set X ⊂ V is good if X contains no 25-book, and no vertex of X lies in (log n)^{4} triangles in X.

Lemma 11. Suppose that B_{1}, B_{2} do not hold, X_{0} ⊂ V and |X_{0}| = 4m. Then X_{0} contains a good set X with |X| = m.

Proof. We claim that some set X_{1} ⊂ X_{0} with |X_{1}| = 2m contains no 25-book. If this is not the case, then X_{0} contains a 25-book with spine {x_{1}, y_{1}}, say. As |X_{0} \ {x_{1}, y_{1}}| > 2m, the set X_{0} \ {x_{1}, y_{1}} contains a 25-book with spine {x_{2}, y_{2}} disjoint from {x_{1}, y_{1}}. Continuing in this way we find m 25-books in X_{0} with disjoint spines, contradicting the assumption that B_{1} does not hold.

Fix a set X_{1} ⊂ X_{0} with |X_{1}| = 2m that contains no 25-book. We are done unless m vertices of X_{1} each lie in (log n)^{4} triangles in X_{1}. But then X_{1} contains m(log n)^{4}/3 triangles. As X_{1} contains no 25-book, each of these triangles shares an edge with at most 3 × 23 = 69 others, and using the greedy algorithm we can find at least m(log n)^{4}/210 > m(log n)^{3} edge disjoint triangles in X_{1}, contradicting the assumption that B_{2} does not hold, and completing the proof.

Continuing our preparation for the proof of Theorem 4, we shall define two further ‘bad’ events. Let B_{3} be the event that for some edge e = xy ∈ E(G_{p}) the graph U_{K_{4}}(G_{p}, x, y) defined in §4 has more than log n edges. Then by Lemma 8 we have ℙ(B_{3}) = o(n^{−2}).

Let B_{4} be the event that some set X ⊂ V with |X| = m does not contain ⌊μ/2⌋ triangles, where

μ = \binom{m}{3}p^{3} = Θ(n^{3/5}(log n)^{3}).

Fixing an m-set X and considering all possible triangles T_{i} ∈ X^{(3)} we have

Δ = ∑_{e(T_{i}∩T_{j})>0} ℙ(T_{i} ∪ T_{j} ⊂ G_{p})

= \binom{m}{2}\binom{m − 2}{2}p^{5}
= O^{∗}(m^{4}p^{5}) = O^{∗}(n^{2/5}) = o(μ).

Thus applying (2) with γ = 1/2 we have

ℙ(B_{4}) ≤ \binom{n}{m}e^{−μ/10}
= e^{O(n^{3/5}(log n)^{2})−Θ(n^{3/5}(log n)^{3})}
= o(n^{−2}).

This time we say that a set X ⊂ V is unusable if X contains a triangle in G′_{p}, and that X is usable if it is not unusable. If G′′ ⊃ G′_{p} is K_{4}-free and x ∈ V, then X = Γ_{G′′}(x) must be usable—otherwise there is a triangle in G′_{p}[X] ⊂ G′′[X], and hence a K_{4} in G′′.

Proof of Theorem 4. Fix a set X ⊂ V with |X| = m. We claim that

ℙ(X is good and usable, ⋂_{i=0}^{4} B_{i}^{c}) = o(n^{−m})  (14)

implies Theorem 4. The argument is exactly analogous to that following equation (10) in the previous section. Indeed, let us write B_{5} for the event that there is some X ⊂ V with |X| = m which is good and usable. Then (14) implies that ℙ(B_{5} \ (⋃_{i=0}^{4} B_{i})) = o(\binom{n}{m}n^{−m}) = o(n^{−2}), so ℙ(⋃_{i=0}^{5} B_{i}) = o(n^{−2}). If no B_{i} holds, then every set X_{0} of 4m vertices is unusable, since a usable set of this size would contain a good, usable m-set by Lemma 11, contradicting the assumption that B_{5} does not hold. Thus G_{∞}, which is a K_{4} free graph containing G′_{p}, has maximum degree at most 4m ≤ 4C(log n)n^{3/5}. This proves Theorem 4 with C replaced by 2C.

As before we wish to condition on a simple up-set U intersected with some down-set D. The events B_{i}^{c}, 0 ≤ i ≤ 3 are all down-sets, but B_{4}^{c} is not, so we treat B_{4} differently. We shall show that

ℙ(X is usable, B_{4}^{c} | X is good, ⋂_{i=0}^{3} B_{i}^{c}) = o(n^{−m}),

which implies (14).

Let c_{0} = ⌊μ/4⌋, where μ = \binom{m}{3}p^{3} as above. We consider all possible sets A ⊂ X^{(2)} that are unions of at most c_{0} triangles in X^{(3)} and contain no K_{4}. Let A_{1}, A_{2}, … be these sets listed in decreasing order of size, and define a random variable A by A = A_{i} where i = min{j : A_{j} ⊂ G_{p}}. The event that X is good and ⋂_{i=0}^{3} B_{i}^{c} holds is a disjoint union of events E of the form

E = {A = A, X is good, ⋂_{i=0}^{3} B_{i}^{c}},

so it suffices to show that

ℙ(X is usable, B_{4}^{c} | E) = o(n^{−m})  (15)

separately for each E.

As before, each event E is of the form

E = {A ⊂ G_{p}} ∩ D,

with D a down-set.

All that remains is to prove (15) for each possible event E. We assume from now on that E holds.

Suppose first that the set A that defines E contains fewer than c_{0} triangles. We claim that in this case B_{4} holds, proving (15). Indeed, suppose B_{4} does not hold, so X contains 2c_{0} triangles. As we are assuming that B_{0} does not hold, X does not contain 2m edge disjoint K_{4}s, and there is a set of at most 12m edges in X meeting every K_{4} in X. As X is good, these edges together meet at most 24 × 12m = o(c_{0}) triangles, so there is some set A_{i} ⊂ G_{p} containing at least c_{0} triangles and no K_{4}. Thus A must contain at least c_{0} triangles, contradicting our assumption.

From now on we suppose that A contains at least c_{0} triangles, and is hence the union of exactly c_{0} distinct triangles T_{1}, …, T_{c_{0}}. We shall examine each T_{t} in turn, looking for a K_{4} in G_{p} sharing an edge with T_{t}; whenever there is no such K_{4}, the triangle T_{t} is present in G′_{p}.

Let M_{0} = A. At stage t, 1 ≤ t ≤ c_{0}, we define M_{t} as follows.

1. If M_{t−1} contains a K_{4} sharing an edge with T_{t}, set M_{t} = M_{t−1}; otherwise continue to step 2.

2. Form a list E_{t,1}, …, E_{t,ℓ_{t}} of all edge sets E ⊂ V^{(2)} that satisfy E ≅ K_{4}, E ⊄ M_{t−1} and E ∩ T_{t} ≠ ∅. If one of these sets is present in G_{p}, set M_{t} = M_{t−1} ∪ E_{t,i_{t}}, with i_{t} = min{i : E_{t,i} ⊂ G_{p}}; otherwise continue to step 3.

3. Set M_{t} = M_{t−1} and continue to stage t + 1, noting that T_{t} ⊂ G′_{p}, so X is unusable.

As before let n_{i}, i = 1, …, 3, be the number of times we reach step i above, so n_{1} = c_{0} and there are n_{3} triangles T_{t} in G′_{p}. Suppose that for some particular t we stop at step 1. Then there must be a K_{4} in M_{t−1} sharing an edge with T_{t}. As there are no K_{4}s in M_{0} = A (by definition of A), this K_{4} is in the union of U_{K_{4}}(G_{p}, x, y) over xy ∈ E_{s,i_{s}} for all s such that we reach step 2. Since we are assuming B_{3} does not hold, this union has at most 6(log n)n_{2} edges. As X is good, each edge is in at most 24 triangles T_{t}, so n_{1} − n_{2} ≤ 150(log n)n_{2}, and

n_{2} ≥ \frac{c_{0}}{151 log n}.

We have shown that we reach step 2 a reasonable number of times. It only remains to show that each time we have probability at least 1/2 of continuing to step 3. Again we need to bound both the total size of M_{t} and the degrees in M_{t} of vertices in X. Now

e(M_{c_{0}}) ≤ e(A) + 5c_{0} ≤ 8c_{0} = O^{∗}(n^{3/5}),  (16)

using the fact that A is the union of c_{0} triangles. Fix x ∈ X. As X is good, there are at most 2(log n)^{4} edges xy contained in triangles in X. We count the number of edges xy ∈ M_{c_{0}} not contained in a triangle in X. Each such edge must be in one of the E_{t,i_{t}}. If the edge zw that E_{t,i_{t}} shares with T_{t} does not contain x, then xzw is a triangle in X—this can happen at for at most (log n)^{4} values of t, as X is good. On the other hand, if one of z, w is equal to x, then x is a vertex of T_{t}. Again this can happen for at most (log n)^{4} values of t. As each E_{t,i_{t}} contributes at most 3 to the degree of x in M_{c_{0}} we have

d_{M_{s}}(x) ≤ d_{M_{c_{0}}} (x) ≤ 2(log n)^{4} + 3(log n)^{4} + 3(log n)^{4},

so the degree of x in M_{s} is at most 8(log n)^{4} = n^{o(1)} for all s.

As in the previous section, if we reach step 2 for T_{t} with M_{t−1} = M_{t−1}, the probability p_{t} that we find some E_{t,i} in G_{p} satisfies

p_{t} ≤ ∑_{i=1}^{ℓ_{t}} p^{e(E_{t,i}\M_{t−1})}.  (17)

We split the sum above according to the relationship between E_{t,i} and M_{t−1}, noting that by definition we have E_{t,i} ⊄ M_{t−1}. We label the vertices of E = E_{t,i} as x, y, z, w, with x, y ∈ X and xy an edge of T_{t}. We say that an edge is marked if it is in M_{t−1}.

For E with E ∩ M_{t−1} = {xy} we have three choices for the edge xy of T_{t}, then at most n choices for each vertex z, w. As e(E \ M_{t−1}) = 5, such terms contribute at most 3n^{2}p^{5} ≤ 1/4 to the sum in (17). As before this will be the main term.

For E with zw ∈ M_{t−1} we have three choices for xy, and, from (16), at most e(M_{t−1}) = O^{∗}(n^{3/5}) choices for zw. Such terms with at least two unmarked edges thus contribute o(1) to the sum. With only one unmarked edge, say xz, then as yw and yz are marked and the number of marked edges from y is at most n^{o(1)}, there are only n^{o(1)} choices for E. The single factor of p ensures that such terms contribute o(1) to (17).

For E with zw not marked, suppose first that one or more of xz, yz is marked, and one or more of xw, yw. Then we again have n^{o(1)} choices, so such terms contribute o(1). Otherwise, one or more of xz, yz is marked, say, and none of xw, yw. We then have n^{o(1)} choices for z, n choices for w, and at least 3 factors of p, from the edges xw, yw, zw. Such terms thus contribute o(1) to (17).

The above case checking shows that p_{t} ≤ 1/2 for n large. Thus

ℙ(n_{3} = 0, B_{4}^{c} | E) ≤ (\frac{1}{2})^{c_{0}/(151 log n)} ≤ e^{−c_{0}/(300 log n)}.  (18)

Now c_{0} = ⌊μ/4⌋ ∼ C^{3}(log n)^{3}n^{3/5}/192. Since n^{−m} = e^{−C(log n)^{2}n^{3/5}}, and X usable implies n_{3} = 0, we have that (18) implies (15) for C = 1000, completing the proof of Theorem 4.

8 Conclusions

Theorems 3 and 4 have a very natural interpretation in vague terms. These results show that for H = C_{4} and H = K_{4} a random maximal H-free graph G_{∞} has roughly the number of edges at which a random graph would be expected to contain an average of one copy of H per edge. Erdős, Suen and Winkler [5] showed that this is also the case for H = C_{3}. Thus, in these cases, the random process constructing G_{∞} proceeds by adding edges more or less uniformly at random until a significant number of possible conflicts (copies of H) arise, and beyond this point not very many more edges are added. In other words, the constrained random process does not ‘organize’ itself significantly as the set of possible edges to add becomes smaller. This contrasts strongly with the case of bipartite graphs, where the graph G_{∞} is highly ‘organized’—it is a complete bipartite graph with nearly equal class sizes, as shown in [5]. It is thus natural to ask for which properties these two kinds of behaviour arise, and what happens in between.

On the one hand, it should be fairly straightforward to show that a random maximal k-colourable graph will be almost as large as it can be. On the other hand, we would expect results like Theorems 3 and 4 for H-free graphs, for many fixed graphs H. When H is edge-balanced, a case which includes complete graphs, cycles and complete bipartite graphs, the basic method used here may well be applicable. However, this application may not be easy: in the proof of Lemma 8, which applies to all edge-balanced H, the configurations M_{t} found by the algorithm had n^{o(1)} edges. This meant that ‘new’ copies of H would almost always share at most one edge with M_{t}, as H is edge-balanced. In the proofs of Theorems 3 and 4, however, configurations with n^{α} edges were considered, for some fixed α > 0. This meant that separate arguments were needed in each case to deal with ‘new’ copies of H sharing more than one edge with M_{t}, so it may not be so easy to extend these proofs to all edge-balanced H.

References

[1] B. Bollobás, Random Graphs, Academic Press, London 1985, xvi+447pp.

[2] B. Bollobás, Combinatorics, Cambridge University Press, 1986, xii+177pp.

[3] B. Bollobás and O. Riordan, Colorings generated by monotone properties, Random Structures and Algorithms 12 (1998), 1–25.

[4] H. Chernoff, A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, Ann. Math. Statistics 23 (1952) 493–507.

[5] P. Erdős, S. Suen and P. Winkler, On the size of a random maximal graph, Random Structures and Algorithms 6 (1995), 309–318.

[6] S. Janson, Poisson approximation for large deviations, Random Structures and Algorithms 1 (1990), 221–229.

[7] D. J. Kleitman, Families of non-disjoint subsets, J. Combin. Theory 1 (1966), 153–155.