Combinatorial Counting, NDMI015, summer term 2023/24
My plan is to lecture on the following three topics. 1. Ramsey theorem for pairs, simple (lower and upper) bounds. 2. Ramsey
theorem for pairs, the recent spectacular exponential breakthrough. 3. Catalan
numbers (classical enumeration).
lecture notes (preliminary, updated March 24)
Lecture 1 on Feb 24, 2025. The function R_r(k) = the minimum n such that for every r-coloring of the edges of K_n there
is a homogeneous k-element set of vertices. Proof of the bound that for every r, k > 1, the value R_r(k) is at most r^{rk - 2}.
Proof of the bound that R_2(k) is at most binom(2k - 2, k - 1). Statement of the canonical (Erdos - Rado) Ramsey theorem for pairs
and an outline of the ``rooted tree of cliques'' method. (I lectured to the single student in Czech.)
Lecture 2 on March 3, 2025. Let ER(l), the Erd"os - Rado number for pairs, be the minimum n such that for every coloring
chi of the edges of K_n (by colors in N) there is an l-element canonical set of vertices (on which chi
restricts to one of the four canonical types). Theorem (Lefmann - Rodl, 1995): For every l we have 2^{c_1*l^2} < ER(l)
< 2^{c_2*l^2*log l}. I skipped the lower bound completely; the proof is easy and is a reduction to the lower bound in the Ramsey theorem
for pairs and an appropriate number of colors. I presented a large part of the proof of the upper bound. Complete proofs are/will be in the above
lecture notes.
Lecture 3 on March 10, 2025. The Theorem (Erdos, 1947): R_t(l) is at least t^{l/2}. Proof exactly after the Erdos's
1/2 page. I only mentioned the Theorem (Lefmann, 1987): R_{r+s}(l) is at least (R_r(l) - 1)*(R_s(l) - 1), and the
Corollary: R_t(l) is at least 2^{ctl} for some constant c>0. I explained the ideas in the proof of the
Theorem (Klazar, 1993): For every l we have ER(l) < 2^{(3/2)*l^6}, and hope to write the proof in detail in the
lecture notes.
Lecture 4 on March 17, 2025. Theorem (infinite Ramsey theorem for pairs): For every r-coloring chi of the edges of
K_N there exists an infinite subset X of N such that the restriction chi | binom(X, 2) is constant; proof.
Lecture 5 on March 24, 2025. The first part of the proof of the recent spectacular
exponential breakthrough.
Lecture 6 on March 31, 2025. The second part of the proof of the recent spectacular
exponential breakthrough.
Lecture 7 on April 7, 2025. The third part of the proof of the recent spectacular
exponential breakthrough.
April 2025