Determina la cardinalidad máxima de una familia de subconjuntos de k elementos de un conjunto de n elementos tal que cada par de subconjuntos de la familia tiene intersección no vacía; en la forma clásica, cuando n ≥ 2k la máxima tamaño es el número de k-subconjuntos que contienen un elemento fijo.

Principio

Principio de combinatoria extremal: entre familias uniformes de k-subconjuntos con la restricción de intersección par a par, las familias extremales son muy estructuradas (típicamente estrellas), y operaciones de compresión o desplazamiento conducen a cotas óptimas.

Demostración

Ejemplo: para n = 8 y k = 3 con n ≥ 2k, el tamaño máximo de una familia intersectante es el número de 3-subconjuntos que contienen un elemento fijo, es decir C(7,2) = 21; se construye una familia máxima fijando un elemento y tomando todos los k-conjuntos que lo contienen.

Aplicación incorrecta

Aplicar la cota clásica cuando n < 2k o a familias no uniformes sin modificación; asumir la misma estructura extremal para familias t-intersectantes (intersección de tamaño ≥ t) sin usar la generalización apropiada.

Consecuencia

Cuando procede, el teorema proporciona tanto una cota superior exacta como una caracterización estructural de las familias extremales (estrellas), lo que orienta demostraciones y construcciones en problemas de familias intersectantes.

Inversión

La perspectiva inversa considera familias que deben ser disjuntas dos a dos: maximizar el tamaño bajo disjunción conduce a máximos y construcciones diferentes (acoplamientos), mostrando cómo al invertir la condición de intersección cambia la familia óptima.

Límite

Se aplica a familias uniformes de k-subconjuntos de un conjunto de n elementos; la cota clásica requiere n ≥ 2k para que la estrella sea extremal; son necesarias variantes para n < 2k, condiciones t-intersectantes o colecciones no uniformes.

Tensión semántica

Compite con conceptos cercanos como teoremas sobre familias t-intersectantes o el teorema completo de intersección de Ahlswede–Khachatrian; la tensión está entre 'intersectante' como intersección no vacía y restricciones de intersección más fuertes que cambian la estructura extremal.

Síntesis

Erdős–Ko–Rado cuantifica y caracteriza la mayor familia uniforme cuya cada pareja se intersecta: bajo la condición clásica n ≥ 2k las familias más grandes son las que fijan un elemento común (estrellas), y los métodos de compresión combinatoria certifican la optimalidad.