III Extremal Graph Theory - Supersaturation

3Supersaturation

III Extremal Graph Theory

3 Supersaturation

Suppose we have a graph

with

(

)

> ex

(

n, F

). Then by definition, there is

at least one copy of

. But can we tell how many copies we have? It turns

out this is not too difficult to answer, and in fact we can answer the question for

any hypergraph.

Recall that an

-uniform hypergraph is a pair (

V, E

), where

E ⊆ V

(`)

. We

can define the extremal function of a class of hypergraphs F by

ex(n, F) = max{e(G) : |G| = n, G contains no f ∈ F}.

Again we are interested in the limiting density

π(F) = lim

n→∞

ex(n, F)





It is an easy exercise to show that this limit always exists. We solved it explicitly

for graphs explicitly previously, but we don’t really need the Erd¨os–Stone theorem

just to show that the limit exists.

The basic theorem in supersaturation is

Theorem

(Erd¨os–Simonovits)

Let

be some

-uniform hypergraph. Then

for all

ε >

0, there exists

(

H, ε

) such that every

-uniform hypergraph

with

|G| = n and

e(G) > (π(H) + ε)





contains bδn

|H|

c copies of H.

Note that

|H|

is approximately the number of ways to choose

|H|

vertices

from n, so it’s the number of possible candidates for subgraphs H.

Proof.

For each

-set

M ⊆ V

(

), we let

[

] be the sub-hypergraph induced

by these vertices. Let the number of subsets

with

(

[

])



π(H) +





be η





. Then we can estimate

(π(H) + ε)





≤ e(G) =

e(G[M])



n−`

m−`



≤







+ (1 − η)





π(H) +







n−`

m−`



So if n > m, then

π(H) + ε ≤ η + (1 + η)



π(H) +



η ≥

1 − π(H) −

> 0.

The point is that it is positive, and that’s all we care about.

We pick m large enough so that

ex(m, H) <



π(H) +







Then H ⊆ G[M ] for at least η





choices of M. Hence G contains at least







n−|H|

m−|H|





|H|





|H|



copies of

, and we are done. (Our results hold when

is large enough, but we

can choose δ small enough so that δn

|H|

< 1 when n is small)

Let

(

) be the number of copies of

. Ramsey’s theorem tells us

(

) +

(

)

0 if

|G|

is large (where

is the complement of

). In the

simplest case where

= 3, it turns out we can count these monochromatic

triangles exactly.

Theorem (Lorden, 1961). Let G have degree sequence d

, . . . , d

. Then

(G) + k

(

G) =





− (n − 2)e(G) +

i=1





Proof. The number of paths of length 2 in G and

G is precisely

i=1







n − 1 − d



= 2

i=1





− 2(n − 2)e(G) + 3





since to find a path of length 2, we pick the middle vertex and then pick the

two edges. A complete or empty

contains 3 such paths; Other sets of three

vertices contain exactly 1 such path. Hence





+ 2(k

(G) + k

(

G)) = number of paths of length 2.

Corollary (Goodman, 1959). We have

(G) + k

(

G) ≥

n(n − 1)(n − 5).

In particular, the Ramsey number of a triangle is at most 6.

Proof. Let m = e(G). Then

(G) + k

(

G) ≥





− (n − 2)m + n



2m/n



Then minimize over m.

This shows the minimum density of a monochromatic

in a red/blue

colouring of

(for

large) is

∼

. But if we colour edges monochromatic, then

is the probability of having a triangle being monochromatic. So the density

is achieved by a “random colouring”. Recall also that the best bounds on the

Ramsey numbers we have are obtained by random colourings. So we might think

the best way of colouring if we want to minimize the number of monochromatic

cliques is to do so randomly.

However, this is not true. While we do not know what the minimum density

of monochromatic

in a red/blue colouring of

, it is already known to be

(while

is what we expect from a random colouring). It is also known by

flag algebras to be >

. So we are not very far.

Corollary. For m = e(G) and n = |G|, we have

(G) ≥

(4m − n

Proof. By Lorden’s theorem, we know

(G) + k

(

G) =





− (n − 2)e(

G) +





where

is the degree sequence in

G. But

(

G) ≤





since the sum is counting the number of paths of length 2. So we find that

(G) ≥





− (n − 2) ¯m −



2 ¯m/n



and ¯m =





− m.

Observe that equality is almost never attained. It is attained only for regular

graphs with no subgraphs looking like

So non-adjacency is an equivalence relation, so the graph is complete multi-partite

and regular. Thus it is T

(n) with r | n.

Theorem.

Let

be a graph. For any graph

, let

(

) be the number of

induced copies of

, i.e. the number of subsets

M ⊆ V

(

) such that

G[M]

∼

F . So, for example, i

(G) = k

(G).

Define

f(G) =

(G),

with the sum being over a finite collection of graphs

, each being complete

multipartite, with

∈ R

and

≥

0 if

is not complete. Then amongst

graphs of given order,

(

) is maximized on a complete multi-partite graph.

Moreover, if α

> 0, then there are no other maxima.

Proof.

We may suppose

0, because the case of

= 0 follows from a

limit argument. Choose a graph

maximizing

and suppose

is not complete

multipartite. Then there exist non-adjacent vertices

x, y

whose neighbourhoods

X, Y differ.

There are four contributions to i

(G), coming from

(i) F’s that contain both x and y;

(ii) F’s that contain y but not x;

(iii) F’s that contain x but not y;

(iv) F’s that contain neither x nor y.

We may assume that the contribution from (iii)

≥

(ii), and if they are equal,

then |X| ≤ |Y |.

Consider what happens when we remove all edges between

and

, and add

edges from y to everything in X. Clearly (iii) and (iv) are unaffected.

–

If (iii)

(ii), then after this move, the contribution of (ii) becomes equal to

the contribution of (iii) (which didn’t change), and hence strictly increased.

The graphs

that contribute to (i) are not complete, so

≥

0. Moreover,

since

is complete multi-partite, it cannot contain a vertex in

∆

. So

making the move can only increase the number of graphs contributing to

(i), and each contribution is non-negative.

–

If (iii) = (ii) and

|X| ≤ |Y |

, then we make similar arguments. The

contribution to (ii) is unchanged this time, and we know the contribution

of (i) strictly increased, because the number of

’s contributing to (i) is

the number of points not connected to x and y.

In both cases, the total sum increased.

Perhaps that theorem seemed like a rather peculiar one to prove. However,

it has some nice consequences. The following theorem relates

(

) with

(

)

for different p and r:

Theorem

(Bollob´as, 1976)

Let 1

≤ p ≤ r

, and for 0

≤ x ≤





, let

(

) be a

maximal convex function lying below the points

{(k

(n)), k

(n))) : q = r − 1, r, . . .} ∪ {(0, 0)}.

Let G be a graph of order n. Then

(G) ≥ ψ(k

(G)).

Proof. Let f(G) = k

(G) − ck

(G), where c > 0.

Claim. It is enough to show that f is maximized on a Tur´an graph for any c.

Indeed, suppose we plot out the values of (k

(n)), k

(n)):

(G)

r−1

(n))

r+1

(n))

r+1

(n))

If the theorem doesn’t hold, then we can pick a

such that (

(

)

, k

(

))

lies below

. Draw a straight line through the point with slope parallel to

. This

has slope

0 for some

. The intercept on the

-axis is then

(

)

− ck

(

which would be greater than

(

any Tur´an graph

) by convexity, a contradiction.

Now the previous theorem immediately tells us

is maximized on some

complete multi-partite graph. Suppose this has

class, say of sizes

≤ a

≤

··· ≤ a

. It is easy to verify

q ≥ r −

1. In fact, we may assume

q ≥ r

, else the

maximum is on a Tur´an graph T

r−1

(n).

Then we can write

f(G) = a

A − ca

B + C,

where

A, B, C

are rationals depending only on

, . . . , a

q−1

and

(

and

count the number of ways to pick a

and

respectively in a way that

involves terms in both the first and last classes).

We wlog assume c is irrational. Hence a

A − ca

= a

(A − cB) 6= 0.

–

A−cB <

0, replace

and

by 0 and

. This would then increase

f, which is impossible.

–

A −cB >

0 and

≤ a

−

2, then we can replace

, a

+ 1

, a

−

to increase f.

Hence a

≥ a

− 1. So G = T

(n).