Extremal and additive combinatorics

يعتمد على

عدد المتطلبات السابقة الإلزامية (حتى الأساس): 52

ستتعلّم

• Prove Turán's theorem and the Erdős–Szekeres bound for Ramsey numbers, and use probabilistic lower bounds.
• State Szemerédi's regularity lemma and theorem, and outline Roth's Fourier-analytic proof for three-term progressions.
• Describe the Green–Tao theorem and an application of the polynomial method, separating theorems from open problems.

تعريف

• The Turán number ex(n, H) is the maximum number of edges of an n-vertex graph containing no copy of H.
• The Ramsey number R(s, t) is the least n such that every red–blue colouring of the edges of Kₙ contains a red Kₛ or a blue Kₜ.
• A set A ⊆ ℤ has positive upper density if limsup_{N→∞} |A ∩ [1, N]| / N > 0.

مبرهنة

• Turán: the maximum number of edges in an n-vertex graph with no K_{r+1} is attained by the balanced complete r-partite graph.
• Erdős: R(k, k) > 2^{k/2} for k ≥ 3, by the probabilistic method; also R(k, k) ≤ C(2k − 2, k − 1).
• Szemerédi (1975): every subset of the integers with positive upper density contains arbitrarily long arithmetic progressions.
• Green–Tao (2004): the primes contain arbitrarily long arithmetic progressions.

مفاهيم خاطئة شائعة

• Thinking small Ramsey numbers are easy to compute; R(5, 5) is still unknown.
• Believing Green–Tao says the primes contain infinite arithmetic progressions; it gives arbitrarily long finite ones only.

اكتشافات اختيارية

• Ergodic theory Furstenberg's ergodic-theoretic proof of Szemerédi's theorem opened a new route between dynamics and combinatorics.
• Fourier and harmonic analysis Roth's theorem on three-term progressions is proved with Fourier analysis on ℤ/Nℤ; higher-order Fourier analysis (Gowers norms) extends the method.
• ← Ergodic theory
• ← Analytic number theory

قراءات إضافية

• Terence Tao and Van H. Vu, Additive Combinatorics (2006)
• Stasys Jukna, Extremal Combinatorics (2001)