combinatoire extrémale

La combinatoire extrémale étudie jusqu’où peut aller la taille d’un ensemble lorsque des conditions lui sont imposées. Elle recherche donc une taille maximale ou minimale compatible avec ces conditions.

Ce qu’elle étudie

Le problème consiste à considérer des ensembles soumis à des contraintes données, puis à déterminer les limites que ces contraintes imposent à leur taille. Une question maximale demande quelle est la plus grande taille encore possible. Une question minimale cherche, au contraire, la plus petite taille qui respecte les mêmes exigences. La discipline s’intéresse ainsi aux cas situés aux extrêmes, sans perdre de vue les conditions qui définissent les ensembles admis.

À quoi elle sert

• Formuler des problèmes de taille sous contraintes.
• Rechercher une limite maximale compatible avec des conditions données.
• Rechercher une limite minimale dans le même cadre.

Où elle se place

La combinatoire extrémale est une branche de la combinatoire. La théorie des graphes extrémaux constitue elle-même l’une de ses branches.

flowchart TD
  P0[Combinatoire] --> D([combinatoire extrémale])
  D --> E0[Théorie des graphes extrémaux]