Combinatoria extrema

Combinatoria extrema es un campo de la combinatoria, que en sí mismo forma parte de las matemáticas. La combinatoria extrema estudia qué tan grande o 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 refiere a clases de conjuntos; esto se llama teoría de conjuntos extremos. Por ejemplo, en un conjunto de elementos n, ¿cuál es el mayor número de subconjuntos de elementos k que pueden cruzarse entre sí por pares? ¿Cuál es el mayor número de subconjuntos de los cuales ninguno contiene a otro? La última pregunta es respondida por el teorema de Sperner, que dio origen a gran parte de la teoría de conjuntos extremos.

Otro tipo de ejemplo: ¿Cuántas personas se pueden invitar a una fiesta donde entre cada tres personas hay dos que se conocen y dos que no se conocen? La teoría de Ramsey muestra que a una fiesta de este tipo pueden asistir como máximo cinco personas. 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 con la restricción de que la suma de dos enteros marcados cualesquiera no se puede marcar. Parece que (independientemente de cuáles sean realmente los números enteros dados) siempre podemos marcar al menos un tercio de ellos.