La combinatoria extrema es un campo de la combinatoria , que en sí misma forma parte de las matemáticas . La combinatoria extrema estudia el tamaño o el tamaño de una colección de objetos finitos ( números , gráficos , vectores , conjuntos , etc.) si tiene que satisfacer determinadas 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 n elementos, ¿cuál es el mayor número de subconjuntos de k elementos que pueden intersecarse por pares? ¿Cuál es el mayor número de subconjuntos de los cuales ninguno contiene ningún otro? La última pregunta es respondida por el teorema de Sperner , que dio lugar a gran parte de la teoría de conjuntos extremos.
Otro tipo de ejemplo: ¿A cuántas personas podemos invitar 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 tal fiesta. O suponga que se nos da un conjunto finito de enteros distintos de cero y se nos pide que marquemos un subconjunto tan grande como sea posible de este conjunto bajo la restricción de que no se puede marcar la suma de dos enteros marcados cualesquiera. Parece que (¡independientemente de los números enteros dados!) Siempre podemos marcar al menos un tercio de ellos.