La combinatoria extremal es un campo de la combinatoria, que a su vez forma parte de las matemáticas. Estudia cuán grande o pequeña puede ser una colección de objetos finitos (números, grafos, vectores, conjuntos, etc.) si debe cumplir ciertas restricciones.
Gran parte de la combinatoria extremal se ocupa de clases de conjuntos, lo que se denomina teoría extremal de conjuntos. Por ejemplo, en un conjunto de n elementos, ¿cuál es el mayor número de subconjuntos de k elementos que pueden intersecarse entre sí por pares? ¿Cuál es el mayor número de subconjuntos tales que ninguno contenga a otro? La respuesta a esta última pregunta la dio el teorema de Sperner, lo que dio origen a gran parte de la teoría extremal de conjuntos.
Otro tipo de ejemplo: ¿A cuántas personas se puede invitar a una fiesta donde, entre cada tres personas, haya dos que se conozcan y dos que no se conozcan? La teoría de Ramsey demuestra que a dicha fiesta pueden asistir como máximo cinco personas (véase teorema de la amistad). O bien, supóngase que se tiene un conjunto finito de enteros distintos de cero y se pide marcar el mayor subconjunto posible de este conjunto, bajo la restricción de que la suma de dos enteros marcados cualesquiera no pueda estar marcada. Resulta que (independientemente de cuáles sean los enteros dados) siempre es posible marcar al menos un tercio de ellos.
Véase también Teoría de grafos extremales Lema de Sauer–Shelah (en inglés) Teorema de Erdös-Ko-Rado Teorema de Kruskal-Katona (en inglés) Desigualdad de Fisher Conjetura de los conjuntos cerrados bajo unión (en inglés)
Referencias
Bibliografía . . .
Combinatoria extremal * Categoría:Optimización combinatoria