The Lumenary · Research pathways

Extremal and additive combinatorics

Name: ______________________

Date: ______________________

You will learn to

Prove Turán's theorem by Zykov symmetrisation and the Erdős–Szekeres bound for Ramsey numbers, and use random colourings for lower bounds
State Szemerédi's regularity lemma and theorem, deduce Roth's theorem from the triangle removal lemma, and prove the key Fourier lemma of Roth's density-increment argument
Prove Dvir's finite-field Kakeya theorem as an instance of the polynomial method, and describe the cap set and sum–product problems
Describe the Green–Tao theorem and the current frontier, separating theorems from open problems such as the growth of Ramsey numbers

1.
How many edges does the Turán graph $T(10, 3)$ have? (By Turán's theorem, this is the maximum number of edges of a $K_4$ -free graph on $10$ vertices.)
2.
What is the maximum number of edges in a triangle-free graph on $11$ vertices?
3.
What upper bound does the Erdős–Szekeres inequality $R(s, t) \le \binom{s + t - 2}{s - 1}$ give for $R(4, 5)$ ?
4.
In the Zykov symmetrisation proof of Turán's theorem, we replace a vertex $u$ by a copy $v'$ of a vertex $v$ with $u \not\sim v$ (so $v'$ is adjacent exactly to $N(v)$ ). Why does the new graph still contain no $K_{r+1}$ ?
- A.A clique cannot contain both $v$ and $v'$ (they are not adjacent), and a clique through $v'$ but not $v$ turns into a clique of the old graph by replacing $v'$ with $v$ .
- B.Because the new graph has fewer edges than the old one.
- C.Because $u$ had the smallest degree in the graph.
- D.Because non-adjacency is an equivalence relation.
5.
Szemerédi's theorem assumes positive upper density. Which infinite set shows that being infinite is not enough to force even a three-term progression?
- A.The powers of $2$ : $\{1, 2, 4, 8, \dots\}$
- B.The primes
- C.The perfect squares
- D.The even numbers
6.
What exactly does the Green–Tao theorem say?
- A.For every $k$ , there is an arithmetic progression of $k$ primes.
- B.There is an infinite arithmetic progression consisting only of primes.
- C.There are infinitely many twin primes $p, p + 2$ .
- D.Every set of integers of positive density contains long progressions.
7.
In the proof of Lemma 7 (Roth's key lemma) we bounded $\left|\sum_{r \neq 0} \hat f(r)^2 \hat f(-2r)\right| \le \alpha \max_{s \neq 0}|\hat f(s)|$ . Which facts does this step use?
- A.That $r \mapsto -2r$ permutes the non-zero residues (as $N$ is odd), and Parseval's identity $\sum_r |\hat f(r)|^2 = \mathbb{E}|f|^2 = \alpha$ .
- B.Szemerédi's regularity lemma.
- C.That $A$ contains no 3-AP.
- D.That $|\hat f(r)| \le \alpha$ for all $r$ .
8.
Recall RamseyProp α s t m: in every graph on α, every vertex set W with m ≤ W.card contains an s-clique or an independent t-set. Which statement expresses $R(3, 3) \le 6$ , and which theorem of the lesson proves it?
- A.RamseyProp α 3 3 6, which is ramsey_binomial 2 2 since (2 + 2).choose 2 = 6.
- B.RamseyProp α 6 3 3
- C.RamseyProp α 3 3 5
- D.ramsey_diag 2
9.
Dvir's theorem says that a Kakeya set $K \subseteq \mathbb{F}_q^n$ has $|K| \ge \binom{q + n - 1}{n}$ . What lower bound does it give for a Kakeya set in $\mathbb{F}_5^2$ ?
10.
Write three_ap_free(A) (does the set A of integers contain no $a \lt b \lt c$ with $a + c = 2b$ ?) and roth_number(N), the largest size of a 3-AP-free subset of range(N), by trying all subsets from the largest size down. Check $r_3(N)$ for $N \le 12$ .
Computational — Practice

Answer key — Extremal and additive combinatorics

1.
$T(10, 3)$ has parts of sizes $4, 3, 3$ , so it has $4 \cdot 3 + 4 \cdot 3 + 3 \cdot 3 = 33$ edges (equivalently $45 - 6 - 3 - 3$ ). This is below the bound $(1 - \frac13)\frac{100}{2} = 33.\overline 3$ , which is attained only when $3 \mid n$ .
2.
$K_{5,6}$ has $30$ edges and no triangle, and Mantel's theorem gives $\lfloor 11^2/4 \rfloor = 30$ as the maximum.
3.
$R(4, 5) \le \binom{7}{3} = 35$ . The true value is $25$ , so the recursion's bound is far from sharp even for small cases; the gap grows exponentially for diagonal numbers.
4.
$v$ and $v'$ have the same neighbours outside $\{v, v'\}$ and are not adjacent to each other. So a clique contains at most one of them, and if it contains $v'$ , swapping in $v$ gives a clique of the same size in the original graph, which had no $K_{r+1}$ . (Deleting $u$ cannot create cliques.)
5.
The powers of $2$ are 3-AP-free: an average of two distinct powers of $2$ is never a power of $2$ . They have density $0$ . Szemerédi's theorem needs positive density; Green–Tao shows that a density-zero set can still contain long progressions if it is pseudorandom enough, as the primes are.
6.
Green–Tao: for each $k$ the primes contain a $k$ -term arithmetic progression (e.g. $7, 37, 67, 97, 127, 157$ for $k = 6$ ). There is no infinite one, since $a + ad = a(1 + d)$ would be composite.
7.
$\left|\sum_{r \ne 0} \hat f(r)^2\hat f(-2r)\right| \le \max_{r \ne 0}|\hat f(-2r)| \cdot \sum_r |\hat f(r)|^2$ . Since $N$ is odd, $-2r$ runs over the non-zero residues as $r$ does, so the maximum is $\max_{s \ne 0}|\hat f(s)|$ ; and Parseval gives $\sum_r |\hat f(r)|^2 = \mathbb{E}_x 1_A(x)^2 = \alpha$ .
8.
$R(3, 3) \le 6$ is RamseyProp α 3 3 6, the instance ramsey_binomial 2 2 (as $\binom{4}{2} = 6$ ). Since RamseyProp α 3 3 5 fails (pentagon), the bound is sharp: $R(3, 3) = 6$ .
9.
$\binom{5 + 2 - 1}{2} = \binom62 = 15$ : the dimension of the space of polynomials of degree at most $q - 1 = 4$ in two variables. A smaller set would lie in the zero set of such a polynomial, which the proof shows is impossible. The bound is not sharp: for odd $q$ the smallest Kakeya sets in the plane have $\frac{q(q+1)}{2} + \frac{q-1}{2}$ points (Blokhuis and Mazzocca, 2008), which is $17$ for $q = 5$ (a quick exhaustive search over one line per direction confirms this). But Dvir's bound has the right order of magnitude, $q^n/n!$ , in every dimension.

10.

from itertools import combinations

def three_ap_free(A):
    s = set(A)
    return not any((a + c) % 2 == 0 and (a + c) // 2 in s
                   for a, c in combinations(sorted(s), 2))

def roth_number(N):
    for k in range(N, -1, -1):
        if any(three_ap_free(S) for S in combinations(range(N), k)):
            return k

This brute force examines up to $2^N$ subsets, which is why the lesson's experiment uses backtracking with pruning to reach $N = 40$ . Note that for distinct $a \lt c$ the midpoint $(a + c)/2$ is automatically different from both, so the test only finds genuine progressions.