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 la taille possible d'une collection d'objets finis (nombres, graphes, vecteurs, ensembles, etc.), si elle doit répondre à certaines restrictions.
Exemples modifier
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 modifier
Références modifier
(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Extremal combinatorics » (voir la liste des auteurs).
Bibliographie modifier
- (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.
