Voir la source de Théorème d'Erdős-Ko-Rado

{{Homon|Théorème d'Erdős|Théorème de Rado}}
[[Fichier:Intersecting set families 2-of-4.svg|vignette|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.]]
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 d'un ensemble fini|cardinal]] [[maximum]] d'une [[famille intersectante]] de [[Sous-ensemble|parties]] à ''r ''éléments dans un ensemble à ''n ''éléments.

== Énoncé ==
Si ''n ''≥ 2''r''<ref>Le cas ''n ''< 2''r ''est [[trivial]] car deux parties de {1, 2, … , ''n''} à ''r ''éléments sont alors automatiquement non disjointes, et l'on obtient <math>\scriptstyle|A|\le\binom nr.</math></ref> et si ''A ''est un ensemble de parties de {1, 2, … , ''n''}, toutes de cardinal ''r ''et deux à deux non [[disjoint]]es, alors le cardinal de ''A ''est au plus égal au [[coefficient binomial]]
<center><math>\binom{n-1}{r-1}.</math></center>

(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<ref>{{chapitre|lang=en|prénom=P.|nom1=Erdős|titre=My joint work with Richard Rado|auteurs ouvrage=C. Whitehead|titre ouvrage=Surveys in combinatorics, 1987: Invited Papers for the Eleventh British Combinatorial Conference|collection=London Mathematical Society Lecture Note Series|numéro dans collection=123|lien éditeur=Cambridge University Press|éditeur=CUP|année=1987|passage=53-80|isbn=978-0-521-34805-8|url=http://www.renyi.hu/~p_erdos/1987-12.pdf}}</ref>, n'a été publié qu'en 1961<ref>{{article|lang=en|prénom=P.|nom=Erdős|prénom2=Chao|nom2=Ko|prénom3=R.|nom3=Rado|titre=Intersection theorems for systems of finite sets|revue=Quarterly J. Math.|série=2|vol=12|année=1961|p.=313-320|url=http://www.renyi.hu/~p_erdos/1961-07.pdf}}</ref>, 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]]<ref>{{article|lang=en|prénom=G. O. H.|nom=Katona|titre=A simple proof of the Erdős-Chao Ko-Rado theorem|lien périodique=Journal of Combinatorial Theory|revue=JCTB|vol=13|année=1972|p.=183-184|url=http://www.renyi.hu/~ohkatona/paper_20.pdf|numéro=2}}</ref> a donné la courte preuve suivante, grâce à un {{citation|argument particulièrement élégant}}<ref name=RD>[[Martin Aigner]] et [[Günter M. Ziegler]], ''[[Raisonnements divins]]'', [https://books.google.fr/books?id=0p4z8ptz6GkC&pg=PA164 p. 164-166], ou [https://books.google.fr/books?id=KvQr9l0wgf8C&pg=PA152 p. 152-153] de la version en anglais</ref> de [[Preuve par double dénombrement|double dénombrement]]. On peut aussi présenter la preuve comme une application de la [[méthode probabiliste]]<ref>{{lien web|url=http://www.unige.ch/math/folks/velenik/papers/LN-PS.pdf|titre=Probabilités et statistiques : La méthode probabiliste (p. 227)|auteur=Yvan Velenik | date=2012|site=Université de Genève}}.</ref>.

=== Preuve par double dénombrement ===
Pour chaque {{Lien|langue=en|trad=Cyclic order|fr=ordre circulaire}} ''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 {{nobr|''S ''{{=}} (''a''{{ind|1}}, ''a''{{ind|2}}, … , ''a{{ind|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{{ind|i}}'' et ''a''{{ind|''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é
<center><math>|A|r!(n-r)!\le(n-1)!r</math></center>
et l'on conclut :
<center><math>|A|\le\frac{r(n-1)!}{r!(n-r)!}={n-1\choose r-1}.</math></center>

== 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 ''> 2''r'', ces ''n ''familles intersectantes de parties à ''r ''éléments sont les seules de cardinal maximum<ref name=RD/>, mais un ''A ''peut être [[Élément maximal|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 ''= 2''r'', les familles maximales sont de cardinal maximum <math>\scriptstyle\frac12\binom nr=\binom{n-1}{r-1}</math> et s'obtiennent en choisissant une partie dans chaque paire de parties [[Complémentaire (théorie des ensembles)|complémentaires]] à ''r ''éléments<ref name=RD/>.

== Notes et références ==
{{Traduction/Référence|en|Erdős–Ko–Rado theorem|505183091|type=note}}
{{reflist}}

== Articles connexes ==
* [[Théorème de Kruskal-Katona]]
* [[Famille de Sperner]]
* [[Tournesol (mathématiques)]]

{{Portail|mathématiques}}

{{DEFAULTSORT:Theoreme d'Erdos-Ko-Rado}}
[[Catégorie:Système d'ensembles]]
[[Catégorie:Théorème de combinatoire|Erdos-Ko-Rado]]