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 [n1] k ⇥ F⇥ 1 [n1] k1 ⇥ intersecting I.H. |F0| n2 k1 ⇥ |F⇥ 1| n2 k2 ⇥ intersecting? I.H. n2 k1 ⇥ + n2 k2 ⇥ = n1 k1 ⇥
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