Théorème de Erdös Ko Rado Emeline

Développement : 158 -
Théorème de Erdös – Ko- Rado :
!
Soit 𝑛 ≥ 2 et 𝑘 ≤ ! des entiers naturels. Soit ℱ une famille de parties de {1, … , 𝑛} telle
que :
∀ 𝐴 ∈ ℱ, 𝑐𝑎𝑟𝑑 𝐴 = 𝐴 = 𝑘

∀ 𝐴, 𝐵 ∈ ℱ, 𝐴 ∩ 𝐵 ≠ ∅
Alors :
𝑛−1
𝑐𝑎𝑟𝑑 ℱ ≤

𝑘−1

Soit :
- 𝒞! l’ensemble des cycles de longueur 𝑛 de 𝔖!
- 𝐴 ∈ ℱ est un intervalle de 𝜎 ∈ 𝒞! = (𝑎! , … , 𝑎! ) si il existe 𝑖 ∈ {1, … , 𝑛} tel que
𝐴 = 𝑎! , 𝑎!!! , … , 𝑎!!!!!

Calculons de deux façons différentes :

𝐼=

𝕀

!,! ,! !"#$%!"##$ !" !



!∈𝒞! !∈ℱ


1

𝐼=

𝑐𝑎𝑟𝑑 𝐴 ∈ ℱ, 𝐴 𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙𝑙𝑒 𝑑𝑒 𝜎
!∈𝒞!

Soit 𝜎 ∈ 𝒞! = (𝑎! , … , 𝑎! ). Plaçons 𝜎 autour d’un cercle.
Notons 𝐴! , … , 𝐴! les familles de ℱ telles que :
𝑐𝑎𝑟𝑑 𝐴! = 𝑘 ∶ 𝑡𝑜𝑢𝑠 𝑙𝑒𝑠 𝑎𝑟𝑐𝑠 𝑑𝑒 𝑙𝑜𝑛𝑔𝑢𝑒𝑢𝑟 𝑘


∀𝑖 ≠ 𝑗, 𝐴! ∩ 𝐴! ≠ ∅ ∶ 𝑎𝑢 𝑚𝑜𝑖𝑛𝑠 𝑢𝑛 𝑎! 𝑒𝑛 𝑐𝑜𝑚𝑚𝑢𝑛

Alors 𝐴! , … , 𝐴! n’ont pas d’extrémités en commun sinon ∃ 𝑖, 𝑗 ∈ {1, … , 𝑡} tels que
𝐴! ∩ 𝐴! = ∅ ou 𝐴! ∩ 𝐴! = 𝐴! = 𝐴!
Une fois 𝐴! fixé, on ne peut « tourner que dans un sens » autour du cercle pour placer les
𝐴! suivants. On a donc 𝑘 − 1 possibilités pour les autres 𝐴! .
(Sur notre dessin décidons de tourner dans le sens des aiguilles d’une montre, on peut avoir
𝐴! qui recouvre 𝑎! , 𝑎! , 𝑎! et 𝐴! qui recouvre 𝑎! , 𝑎! , 𝑎! ; on aurait pu choisir les deux autres
possibilités en tournant dans l’autre sens.)
On a donc :
𝑡 − 1 ≤ 𝑘 − 1 ⇒ 𝑡 ≤ 𝑘
D’où puisque 𝑡 = 𝑐𝑎𝑟𝑑 𝐴 ∈ ℱ, 𝐴 𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙𝑙𝑒 𝑑𝑒 𝜎 :

𝑰=

𝑐𝑎𝑟𝑑 𝐴 ∈ ℱ, 𝐴 𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙𝑙𝑒 𝑑𝑒 𝜎 =
!∈𝒞!


2

𝑡≤
!∈𝒞!

𝐼=

𝑘 = 𝑘 𝑐𝑎𝑟𝑑 𝒞! = 𝒌 𝒏 − 𝟏 !
!∈𝒞!

𝑐𝑎𝑟𝑑 𝜎 ∈ 𝒞! , 𝐴 𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙𝑙𝑒 𝑑𝑒 𝜎
!∈ℱ


Soit 𝐴 = 𝑎! , … 𝑎! ∈ ℱ, 𝜎 ∈ 𝒞! , 𝐴 𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙𝑙𝑒 𝑑𝑒 𝜎. Sans perte de généralité on peut
écrire : 𝜎 = (𝑎! , … 𝑎! , 𝑎!!! , … , 𝑎! ) (car le cycle 𝑎! , … . , 𝑎! = (𝑎! , 𝑎! , … 𝑎!!! ))
On a donc 𝑘! choix pour 𝑎! , … 𝑎! et 𝑛 − 𝑘 ! choix pour 𝑎!!! , … , 𝑎! . Donc :
𝑰=

𝑐𝑎𝑟𝑑 𝜎 ∈ 𝒞! , 𝐴 𝑖𝑛𝑡𝑒𝑟𝑣𝑎𝑙𝑙𝑒 𝑑𝑒 𝜎 =
!∈ℱ

𝑘! 𝑛 − 𝑘 ! = 𝒌! 𝒏 − 𝒌 ! 𝒄𝒂𝒓𝒅 𝓕
!∈ℱ

Développement : 158 -
On a donc :
𝐼

≤𝑘 𝑛−1 !

= 𝑘! 𝑛 − 𝑘 ! 𝑐𝑎𝑟𝑑 ℱ

D’où
𝑐𝑎𝑟𝑑 ℱ ≤

𝑘 𝑛−1 !
𝑛−1 !
𝑛−1
=
=

𝑘! 𝑛 − 𝑘 !
𝑘−1 ! 𝑛−𝑘 !
𝑘−1