Extremal and additive combinatorics
Warm-upHumanHow many edges does the Turán graph have? (By Turán's theorem, this is the maximum number of edges of a -free graph on vertices.)
How many edges does the Turán graph have? (By Turán's theorem, this is the maximum number of edges of a -free graph on vertices.)
What is the maximum number of edges in a triangle-free graph on vertices?
What upper bound does the Erdős–Szekeres inequality give for ?
In the Zykov symmetrisation proof of Turán's theorem, we replace a vertex by a copy of a vertex with (so is adjacent exactly to ). Why does the new graph still contain no ?
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?
What exactly does the Green–Tao theorem say?
In the proof of Lemma 7 (Roth's key lemma) we bounded . Which facts does this step use?
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 , and which theorem of the lesson proves it?
Dvir's theorem says that a Kakeya set has . What lower bound does it give for a Kakeya set in ?
Write three_ap_free(A) (does the set A of integers contain no with ?) 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 for .