Détermine la cardinalité maximale d'une famille de sous-ensembles à k éléments d'un ensemble à n éléments telle que chaque paire de sous-ensembles de la famille a une intersection non vide ; dans la forme classique, si n ≥ 2k la taille maximale est le nombre de k-sous-ensembles contenant un élément fixé.

Principe

Principe d'extrémalité en combinatoire : parmi les familles uniformes de k-ensembles soumises à une contrainte d'intersection, les familles extrêmes sont fortement structurées (typiquement des étoiles), et des opérations de compression ou de déplacement conduisent aux bornes optimales.

Démonstration

Exemple : pour n = 8 et k = 3 avec n ≥ 2k, la taille maximale d'une famille intersectante est le nombre de 3-ensembles contenant un élément fixé, soit C(7,2) = 21 ; on construit une famille maximale en fixant un élément et en prenant tous les k-ensembles qui le contiennent.

Mauvaise application

Appliquer la borne classique lorsque n < 2k ou à des familles non uniformes sans modification ; supposer la même structure extrême pour des familles t-intersectantes (intersection de taille ≥ t) sans utiliser la généralisation appropriée.

Conséquence

Lorsque la condition est satisfaite, le théorème fournit une borne numérique exacte et une caractérisation structurelle des familles extrêmes (étoiles), guidant les preuves et les constructions dans les problèmes de familles intersectantes.

Inversion

La perspective inverse considère des familles exigées d'être deux à deux disjointes : maximiser la taille sous la disjonction entraîne des maxima et constructions combinatoires différents (appariements), ce qui montre comment inverser la condition d'intersection modifie les familles optimales.

Limite

S'applique aux familles uniformes de k-sous-ensembles d'un ensemble à n éléments ; la borne classique requiert n ≥ 2k pour que l'étoile soit extrême ; des variantes sont nécessaires pour n < 2k, les conditions t-intersectantes ou les collections non uniformes.

Tension sémantique

Concurrence avec des résultats voisins tels que les théorèmes sur les familles t-intersectantes ou le théorème complet d'Ahlswede–Khachatrian ; la tension porte sur la différence entre 'intersectant' (intersection non vide) et des contraintes d'intersection plus fortes qui modifient la structure extrême.

Synthèse

Erdős–Ko–Rado quantifie et caractérise la plus grande famille uniforme dont chaque paire se rencontre : sous la condition classique n ≥ 2k, les familles maximales sont celles qui fixent un élément commun (étoiles), et les méthodes de compression combinatoire valident l'optimalité.