La combinatoire extrémale est un domaine de la combinatoire, qui est elle-même une partie des mathématiques. La combinatoire extrémale étudie la taille possible d'une collection d'objets finis (nombres, graphes, vecteurs, ensembles, etc.), si elle doit répondre à certaines restrictions.
Exemples 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.
Voir aussi 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)
Références
Bibliographie . . . 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.
Catégorie:Combinatoire