Skip to content
The Lumenary

Practice · Research pathways

Extremal and additive combinatorics

Extremal and additive combinatorics

Warm-upHuman

How many edges does the Turán graph T(10,3)T(10, 3) have? (By Turán's theorem, this is the maximum number of edges of a K4K_4-free graph on 1010 vertices.)

Extremal and additive combinatorics

Warm-upHuman

What is the maximum number of edges in a triangle-free graph on 1111 vertices?

Extremal and additive combinatorics

CoreHuman

What upper bound does the Erdős–Szekeres inequality R(s,t)≤(s+t−2s−1)R(s, t) \le \binom{s + t - 2}{s - 1} give for R(4,5)R(4, 5)?

Extremal and additive combinatorics

CoreHuman

In the Zykov symmetrisation proof of Turán's theorem, we replace a vertex uu by a copy v′v' of a vertex vv with u≁vu \not\sim v (so v′v' is adjacent exactly to N(v)N(v)). Why does the new graph still contain no Kr+1K_{r+1}?

Choose one

Extremal and additive combinatorics

CoreHuman

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?

Choose one

Extremal and additive combinatorics

Warm-upHuman

What exactly does the Green–Tao theorem say?

Choose one

Extremal and additive combinatorics

StretchHuman

In the proof of Lemma 7 (Roth's key lemma) we bounded ∣∑r≠0f^(r)2f^(−2r)∣≤αmax⁡s≠0∣f^(s)∣\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?

Choose one

Extremal and additive combinatorics

CoreFormal

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)≤6R(3, 3) \le 6, and which theorem of the lesson proves it?

Choose one

Extremal and additive combinatorics

CoreHuman

Dvir's theorem says that a Kakeya set K⊆FqnK \subseteq \mathbb{F}_q^n has ∣K∣≥(q+n−1n)|K| \ge \binom{q + n - 1}{n}. What lower bound does it give for a Kakeya set in F52\mathbb{F}_5^2?

Extremal and additive combinatorics

StretchComputational

Write three_ap_free(A) (does the set A of integers contain no a<b<ca \lt b \lt c with a+c=2ba + 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 r3(N)r_3(N) for N≤12N \le 12.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.