La combinatoria extrema es un campo de la combinatoria , que es en sí misma una parte de las matemáticas . La combinatoria extrema estudia cuán grande o cuán pequeña puede ser una colección de objetos finitos ( números , gráficos , vectores , conjuntos , etc.) si tiene que satisfacer ciertas restricciones.
Gran parte de la combinatoria extrema se ocupa de las clases de conjuntos; esto se llama teoría de conjuntos extremales . 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 de los cuales ninguno contiene a otro? La última pregunta se responde con el teorema de Sperner , que dio origen a gran parte de la teoría de conjuntos extremales.
Otro tipo de ejemplo: ¿cuántas personas pueden ser invitadas a una fiesta en la que entre cada tres personas hay dos que se conocen y dos que no se conocen? La teoría de Ramsey muestra que, como máximo, cinco personas pueden asistir a una fiesta de este tipo. O supongamos que se nos da un conjunto finito de números enteros distintos de cero y se nos pide que marquemos un subconjunto lo más grande posible de este conjunto bajo la restricción de que no se puede marcar la suma de dos números enteros marcados cualesquiera. Parece que (independientemente de cuáles sean realmente los números enteros dados) siempre podemos marcar al menos un tercio de ellos.