Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Théorème d'Erdős-Ko-Rado
Résumé
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 maximum d'une famille intersectante de parties à r éléments dans un ensemble à n éléments.
Si n ≥ 2r 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
(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, n'a été publié qu'en 1961, 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.
La preuve de 1961 utilisait un raisonnement par récurrence sur n. En 1972, Gyula O. H. Katona a donné la courte preuve suivante, grâce à un de double dénombrement. On peut aussi présenter la preuve comme une application de la méthode probabiliste.
Pour chaque 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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.