6Extremal hypergraphs
III Extremal Graph Theory
6 Extremal hypergraphs
Define
K
`
`
(
t
) be the complete
`
-partite
`
-uniform hypergraph with
`
classes of
size t, containing all t
`
edges with one vertex in each class.
Theorem
(Erd¨os)
.
Let
G
be
`
-uniform of order
n
with
p
n
`
edges, where
p ≥ 2n
−1/t
`−1
. Then G contains K
`
`
(t) (provided n is large).
If we take
`
= 2, then this agrees with what we know about the exact value
of the extremal function.
Proof.
Assume that
t ≥
2. We proceed by induction on
` ≥
2. For each (
`−
1)-set
σ ⊆ V (G), let
N(σ) = {v : σ ∪ {v} ∈ E(G)}.
Then the average degree is
n
` − 1
−1
X
|N(σ)| =
n
` − 1
−1
`|E(G)| = p(n − ` + 1).
For each of the
n
t
many t-sets T ⊆ V (G), let
D(T) = {σ : T ⊆ N(σ)}.
Then
X
T
|D(T)| =
X
σ
|N(σ)|
t
≥
n
` − 1
p(n − ` + 1)
t
,
where the inequality follows from convexity, since we can assume that
p
(
n − `
+
1) ≥ t − 1 if n is large.
In particular, there exists a T with
|D(T)| ≥
n
t
−1
n
` − 1
p(n − ` + 1)
t
≥
1
2
p
t
n
` − 1
.
when n is large. By our choice of t, we can write this as
|D(T)| ≥ 2
t−1
n
−1/t
`−2
n
` − 1
.
If ` = 2, then this is ≥ 2
t−1
≥ t. So T is joined to a T -set giving K
t,t
.
If
` ≥
3, then
|D
(
T
)
| ≥
2
n
−1/t
`−2
n
`−1
. So, by induction, the (
` −
1)-uniform
hypergraph induced by the
σ
with
T ⊆ N
(
σ
) contains
K
`−1
`−1
(
t
), giving
K
`
`
(
t
)
with T .
We can do a simple random argument to show that this is a right-order of
magnitude.