Théorème d'Erdős-Ko-Rado

Le théorème d'Erdős-Ko-Rado est un théorème de combinatoire dû à Paul Erdős, Chao Ko et Richard Rado, qui précise le cardinal maximum d'une famille intersectante de parties à r éléments dans un ensemble à n éléments.

Deux façons de construire une famille de sous-ensembles de r éléments parmi n, de sorte que tous les sous-ensembles s'intersectent et qu'il y ait autant de sous-ensembles que possible (ce qui correspond à la limite du théorème de Erdős-Ko-Rado) : à gauche, une famille formée en fixant un élément x et en choisissant les r - 1 autres éléments de toutes les manières possibles ; à droite (pour n = 2r), une famille formée en évitant un élément x et en choisissant r des éléments restants de toutes les manières possibles. Dans cet exemple, n = 4 et r = 2 ; les plus grandes familles possibles de sous-ensembles qui s'intersectent ont trois ensembles.

Énoncé

Si n ≥ 2r[1] et si A est un ensemble de parties de {1, 2, … , n}, toutes de cardinal r et deux à deux non disjointes, alors le cardinal de A est au plus égal au coefficient binomial

{\binom {n-1}{r-1}}.

(Un ensemble A de parties peut être considéré comme un hypergraphe, et la condition que toutes ces parties soient de cardinal r s'exprime alors en disant que l'hypergraphe est uniforme de rang r.)

Ce théorème, démontré en 1938[2], n'a été publié qu'en 1961[3], sous une forme légèrement différente : dans l'énoncé de 1961, on demande seulement que les parties soient de cardinal au plus r, mais on ajoute l'hypothèse qu'aucune n'est incluse dans une autre. Cet énoncé est équivalent au précédent : il s'y ramène en grossissant les parties pour leur faire atteindre la taille r.

Démonstrations

Histoire et méthodes

La preuve de 1961 utilisait un raisonnement par récurrence sur n. En 1972, Gyula O. H. Katona[4] a donné la courte preuve suivante, grâce à un « argument particulièrement élégant »[5] de double dénombrement. On peut aussi présenter la preuve comme une application de la méthode probabiliste[6].

Preuve par double dénombrement

Pour chaque ordre circulaire (en) C sur {1, 2, … , n}, parmi les n parties de {1, 2, … , n} qui forment des intervalles de longueur r pour cet ordre, il y en a au plus r qui appartiennent à A. En effet, si S = (a₁, a₂, … , a_r) est un intervalle pour C formant un élément de A alors, tout autre intervalle pour ce même C et formant aussi un élément de A doit intersecter S donc doit séparer a_i et a_{i + 1} pour un certain i < r (c'est-à-dire qu'il doit contenir l'un de ces deux éléments et pas l'autre). Or les deux intervalles de longueur r qui séparent ces deux éléments sont disjoints, donc au plus l'un des deux peut appartenir à A. Ainsi, pour C fixé, au plus 1 + (r – 1) = r éléments de A sont des intervalles.

On compte alors de deux façons le nombre de couples (S, C), où C est un ordre circulaire sur {1, 2, … , n} et S est un élément de A formant un intervalle pour cet ordre. D'une part, pour chaque élément S de A, C est déterminé par le choix de l'une des r! permutations de S et de l'une des (n – r)! permutations des éléments restants, ce qui prouve que le nombre de couples est égal à |A|r!(n – r)!. D'autre part, pour chacun des (n – 1)! ordres circulaires C, il n'y a, comme expliqué plus haut, qu'au plus r éléments S de A formant des intervalles, ce qui prouve que le nombre de couples est inférieur ou égal à (n – 1)!r. En combinant ces deux façons de compter les couples, on obtient l'inégalité

|A|r!(n-r)!\leq (n-1)!r

et l'on conclut :

|A|\leq {\frac {r(n-1)!}{r!(n-r)!}}={n-1 \choose r-1}.

Taille maximum et familles maximales

Le majorant indiqué par le théorème est atteint en fixant un élément dans {1, 2, … , n} et en prenant pour A l'ensemble de toutes les parties à r éléments qui contiennent cet élément fixé.

Si n > 2r, ces n familles intersectantes de parties à r éléments sont les seules de cardinal maximum[5], mais un A peut être maximal pour l'inclusion sans être de cardinal maximum : pour n = 7 et r = 3, l'ensemble des droites du plan de Fano est maximal mais ces droites ne sont pas concourantes. Il n'y a que 7 droites, alors que le cardinal maximum vaut 15.

Pour n = 2r, les familles maximales sont de cardinal maximum $\scriptstyle {\frac {1}{2}}{\binom {n}{r}}={\binom {n-1}{r-1}}$ et s'obtiennent en choisissant une partie dans chaque paire de parties complémentaires à r éléments[5].

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Erdős–Ko–Rado theorem » (voir la liste des auteurs).

Le cas n < 2r est trivial car deux parties de {1, 2, … , n} à r éléments sont alors automatiquement non disjointes, et l'on obtient $\scriptstyle |A|\leq {\binom {n}{r}}.$
(en) P. Erdős, « My joint work with Richard Rado », dans C. Whitehead, Surveys in combinatorics, 1987: Invited Papers for the Eleventh British Combinatorial Conference, CUP, coll. « London Mathematical Society Lecture Note Series » (n^o 123), 1987 (ISBN 978-0-521-34805-8, lire en ligne), p. 53-80
(en) P. Erdős, Chao Ko et R. Rado, « Intersection theorems for systems of finite sets », Quarterly J. Math., 2^e série, vol. 12,‎ 1961, p. 313-320 (lire en ligne)
(en) G. O. H. Katona, « A simple proof of the Erdős-Chao Ko-Rado theorem », JCTB, vol. 13, n^o 2,‎ 1972, p. 183-184 (lire en ligne)
Martin Aigner et Günter M. Ziegler, Raisonnements divins, p. 164-166, ou p. 152-153 de la version en anglais
Yvan Velenik, « Probabilités et statistiques : La méthode probabiliste (p. 227) », sur Université de Genève, 2012.

Articles connexes

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.