南京大学：《组合数学 Combinatorics》课程教学资源（课件讲稿）Ramsey Theory

Shifting lsoperimetric problem: With fixed perimeter, what plane figure has the largest area?

With fixed perimeter, what plane figure has the largest area? Shifting Isoperimetric problem:

Shifting lsoperimetric problem: With fixed area, what plane figure has the smallest perimeter? Steiner symmetrization

With fixed area, what plane figure has the smallest perimeter? Shifting Steiner symmetrization Isoperimetric problem:

Erdos-Ko-Rado Theorem Let FC(),n≥2k. vS,TeF,SnT≠0→Fl≤（ k-1 induction on n F1={S∈F|n∈S Fo={S∈F|m主S} F1={S\{n|S∈F1} F() I.H. FH(-) intersecting 1Fo≤(-) intersecting? F引≤(-2》 1F=Fol+F=1Fol+1F引≤(-)+(-)=(-)

Let F ￾ ￾[n] k ⇥ , n ⇥ 2k. |F| ⇥ ￾n ￾ 1 k ￾ 1 ⇥ Erdős-Ko-Rado Theorem ⇤S, T ￾ F, S ⌃ T ⇥= ⌅ induction on n F0 = {S ￾ F | n ⇥￾ S} F1 = {S ￾ F | n ￾ S} |F| = |F0| + |F1| F￾ 1 = {S \ {n} | S ￾ F1} = |F0| + |F￾ 1| F0 ￾ ￾[n￾1] k ⇥ F⇥ 1 ￾ ￾[n￾1] k￾1 ⇥ intersecting I.H. |F0| ￾ ￾n￾2 k￾1 ⇥ |F⇥ 1| ￾ ￾n￾2 k￾2 ⇥ intersecting? I.H. ￾ ￾n￾2 k￾1 ⇥ + ￾n￾2 k￾2 ⇥ = ￾n￾1 k￾1 ⇥

Shifting (compression) speckal(） F remains intersecting after deleting n n

Shifting (compression) special F ￾ ￾[n] k ⇥ F remains intersecting after deleting n n i

Shifting (compression) FC2n for1≤i<j≤m VTEF,write Tij=(T)Uti (i,)-shift::S（) T∈F, -任 ifj∈T,i年T,and Tij年F, otherwise. S(F)={S(T)|T∈F}

Shifting (compression) Sij (T) = ￾ Tij if j ￾ T,i ⇥￾ T, and Tij ⇥￾ F, T otherwise. F ￾ 2[n] for 1 ￾ i<j ￾ n ⇥T ￾ F, write Tij = (T \ {j}) ⌅ {i} (i, j)-shift: Sij (·) ⇥T ￾ F, Sij (F) = {Sij (T) | T ￾ F}

1≤i Ai∩B=0 contradiction!

Sij (T) = ￾ Tij if j ￾ T,i ⇥￾ T, and Tij ⇥￾ F, T otherwise. 1 ￾ i<j ￾ n ⇥T ￾ F, write Tij = (T \ {j}) ⌅ {i} Sij (F) = {Sij (T) | T ￾ F} (2) the only bad case: A, B ￾ F A ￾ B = {j} i ⇥￾ B Aij ⇥ B = ￾ Aij = A \ {j} ⇤ {i} ￾ F Bij = B \ {j} ⌅ {i} ⇥￾ F contradiction! |Sij (T)| = |T| F intersecting Sij (F) intersecting 1. and 2. |Sij (F)| = |F|

1≤i<)≤nT∈F,write Tii=(T\{})U{} m-8 ifj∈T,itT,andT年F, otherwise. S(F)={S(T)|T∈F} 1.lS(T)川=T and|Si(F)川=lF到 2.F intersecting Si(F)intersecting repeat applying (i,))-shifting Sis(F)for 1<i<jn eventually,F is unchanged by any Sj(F) called:F is shifted

Sij (T) = ￾ Tij if j ￾ T,i ⇥￾ T, and Tij ⇥￾ F, T otherwise. 1 ￾ i<j ￾ n ⇥T ￾ F, write Tij = (T \ {j}) ⌅ {i} Sij (F) = {Sij (T) | T ￾ F} repeat applying (i, j)-shifting Sij (F) for 1 ￾ i<j ￾ n eventually, F is unchanged by any Sij (F) called: F is shifted |Sij (T)| = |T| F intersecting Sij (F) intersecting 1. and 2. |Sij (F)| = |F|

Let F(),n≥2k. -1 S,T∈F,SnT≠0>IF|≤ k-1 Erdos-Ko-Rado's proof: true for k=1; when n 2k, vS∈() at most one of S and s is in F n! 代) 2·k!(m-k)川 (n-1)！ = (k-1)(m-k)！

Erdős-Ko-Rado’s proof: Let F ￾ ￾[n] k ⇥ , n ⇥ 2k. |F| ⇥ ￾n ￾ 1 k ￾ 1 ⇥ ⇤S, T ￾ F, S ⌃ T ⇥= ⌅ when n = 2k, ⇥S ￾ ￾[n] k ⇥ at most one of S and S¯ is in F |F| ￾ 1 2 ￾n k ⇥ = n! 2 · k!(n ￾ k)! = (n ￾ 1)! (k ￾ 1)!(n ￾ k)! = ￾n ￾ 1 k ￾ 1 ⇥ true for k=1;

Let F(),n≥2k. m-1 VS,T∈F,SnT卡0>IF≤ k-1 arbitrary IF=FI intersecting F shifted keep intersecting ↓ <(i》

Let F ￾ ￾[n] k ⇥ , n ⇥ 2k. |F| ⇥ ￾n ￾ 1 k ￾ 1 ⇥ ⇤S, T ￾ F, S ⌃ T ⇥= ⌅ F arbitrary intersecting shifted F￾ |F| = |F￾ | keep intersecting |F| ⇥ ￾n ￾ 1 k ￾ 1 ⇥ |F￾ | ⇥ ￾n ￾ 1 k ￾ 1 ⇥

Let FC(),n≥2k. -1 S,T∈F,SnT卡0|F≤ k-1 when n>2k,induction on n WLOG:F is shifted F1={S∈F|n∈S}F1={S\{n}|S∈F} Fis intersecting otherwise, 3A,B∈F A0B={n} |AUB|≤2k-1 Ji<n,ig AUB C=A\{n}U{}∈F☐ F is shifted C∩B=0 contradiction!

Let F ￾ ￾[n] k ⇥ , n ⇥ 2k. |F| ⇥ ￾n ￾ 1 k ￾ 1 ⇥ ⇤S, T ￾ F, S ⌃ T ⇥= ⌅ when n > 2k, induction on n F1 = {S ￾ F | n ￾ S} WLOG: F is shifted F￾ 1 = {S \ {n} | S ￾ F1} is intersecting otherwise, < n ￾ 1 ￾ F = ￾ ⇥A, B ￾ F A ￾ B = {n} |A ⇤ B| ⇥ 2k ￾ 1 C = A \ {n} ￾ {i} C ￾ B ⇤i < n, i ⇥￾ A ⌅ B F is shifted contradiction! F￾ 1