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 6)
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 - R"odl, 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.
March 2025