Combinatoire extrémale

La majeure partie de la combinatoire extrémale concerne des classes d'ensembles : c'est la théorie extrémale des ensembles. Par exemple,

• quel est le plus grand nombre de sous-ensembles à k éléments dans un ensemble à n éléments qui peuvent avoir une intersection non vide deux-à-deux ?
• quel est le plus grand nombre de sous-ensembles où aucun ne contient un autre ? Cette question a sa réponse dans le théorème de Sperner, qui a alimenté une grande partie de la théorie extrémale des ensembles.

Autres exemples :

• Combien de personnes peut-on inviter à une fête si, parmi chaque groupe de trois personnes, il y en a deux qui se connaissent, et deux autres qui ne connaissent pas ? La théorie de Ramsey montre que, tout au plus cinq personnes peuvent participer à une telle fête.
• Dans un ensemble fini d'entiers non nuls, quel est le plus grand sous-ensemble dont on peut marquer les éléments avec la condition 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
• Tournesol (mathématiques)

• (en) Stasys Jukna, Extremal Combinatorics, With Applications in Computer Science, Berlin/Heidelberg/New York, Birkhäuser Verlag, 2011, 375 p. (ISBN 978-3-540-66313-3 et 3-540-66313-4, lire en ligne).
• Noga Alon et Michael Krivelevich, Extremal and Probabilistic Combinatorics, 2006 (lire en ligne).
• Peter Frankl et Vojtěch Rödl, « Forbidden intersections », Transactions of the American Mathematical Society, vol. 300, n^o 1,‎ 1987, p. 259–286 (DOI 10.2307/2000598).
• Combinatoire extrémale et optimisation de la diversité : des apports réciproques !
• Yannick Frein, Benjamin Lévèque, András Sebo, « Generating All Sets With Bounded Unions », Combinatorics, Probability and Computing, vol. 17, 641-660, 2008.

• Portail des mathématiques