La combinatoire extrémale cherche la taille maximale (ou minimale) d'un objet vérifiant une contrainte : nombre maximal d'arêtes sans triangle (Mantel), nombre maximal d'ensembles deux à deux non disjoints (Erdős-Ko-Rado), etc.
Combinatoire extrémale — Résumé de cours
1ère Année Collège — Atlasmaths.ma
Cours complet
Contenu du cours
🔑 Formules clés à retenir
- Mantel : un graphe à sommets sans triangle a au plus arêtes (atteint pour le biparti complet ).
- Turán : généralisation pour l'absence de .
- Erdős-Ko-Rado : pour , une famille intersectante de -ensembles dans a au plus éléments.
⚠️
Astuces & Pièges à éviter
Les erreurs classiques — à lire avant les exercices !
- Argument de "shifting" : transformer la famille en gardant la propriété et en augmentant un paramètre, jusqu'à atteindre la configuration extrémale.
- Méthode probabiliste : tirer aléatoirement et calculer l'espérance.
- Borner par le degré : donne souvent une borne sur .
— Exercice bonus
—
Cet exercice a été ajouté récemment. Besoin d'aide ? Demande à Mentor →