Combinatoire extrémale

La majeure partie de la combinatoire extrémale concerne des classes d'ensembles ; cela s'appelle la théorie extrémale des ensembles. Par exemple, dans un ensemble à n éléments, quel est le plus grand nombre de sous-ensembles à k éléments qui peuvent avoir une intersection deux à deux ? Quel est le plus grand nombre de sous-ensembles où aucun ne contient un autre ? La dernière question trouve sa réponse dans le théorème de Sperner, qui a alimenté une grande partie de la théorie extrémale des ensembles.

Un autre exemple : Combien de personnes peut-on inviter à une fête où parmi chaque groupe de trois personnes il y en a deux personnes qui se connaissent, et deux qui ne connaissent pas l'un l'autre ? La théorie de Ramsey montre que, tout au plus cinq personnes peuvent participer à cette fête. Ou, supposons que nous avons un ensemble fini d'entiers non nuls, et que nous sommes invités à marquer le plus grand sous-ensemble possible de cet ensemble sous la restriction que la somme de n'importe quelle paire d'entiers marqués ne soit pas marquée. Il semble que (indépendamment de ce que sont les entiers donnés en fait!) on peut toujours marquer au moins un tiers d'entre eux.

• Théorie des graphes extrémaux
• Lemme de Sauer–Chela
• Théorème d'Erdős-Ko-Rado
• Théorème de Kruskal-Katona
• Inégalité de Fisher
• Conjecture des familles stables par unions
• Graphe de Frankl-Rödl