Combinatoire extrémale
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 de quelle taille une collection d'objets finis (nombres, graphes, vecteurs, ensembles, etc.) peut être, si elle doit répondre à certaines restrictions.
Exemples
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.
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
Références
Bibliographie
- (en) Stasys Jukna, Extremal Combinatorics, With Applications in Computer Science, Berlin/Heidelberg/New York, Birkhäuser Verlag, , 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, (lire en ligne).
- Peter Frankl et Vojtěch Rödl, « Forbidden intersections », Transactions of the American Mathematical Society, vol. 300, no 1, , 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.
