Teorema de Erdös-Ko-Rado
Paul Erdős, Chao Ko y Richard Rado demostraron el teorema en 1938, pero no lo publicaron hasta 1961.
Una forma de construir una familia de conjuntos con estos parámetros, cada dos que comparten un elemento, es elegir un único elemento que pertenezca a todos los subconjuntos y, a continuación, formar todos los subconjuntos que contengan el elemento elegido.
es lo suficientemente grande para que el problema no sea trivial
esta construcción produce las mayores familias de intersección posibles.
Varios teoremas análogos se aplican a otros tipos de objetos matemáticos distintos de los conjuntos, incluidos los subespacios lineales, las permutaciones y las cadenas.
También describen las familias de intersección más grandes posibles como las que se forman eligiendo un elemento y formando la familia de todos los objetos que contienen el elemento elegido.
es necesario para que el problema no sea trivial: cuando
Un conjunto independiente es una colección de vértices que no tiene aristas entre sus pares, y el número de independencia es el tamaño del mayor conjunto independiente.
[5] Paul Erdős, Chao Ko y Richard Rado demostraron este teorema en 1938 tras trabajar juntos en él en Inglaterra.
, y cumplir el requisito adicional de que ningún subconjunto esté contenido en otro.
Dos conjuntos cualesquiera de esta familia se intersecan, porque ambos incluyen
de otros elementos que escoger, y cada conjunto elige
forman una familia de intersección máxima que incluye sólo a conjuntos
Este resultado se denomina teorema de Hilton-Milner, en honor a su demostración por Anthony Hilton y Eric Charles Milner en 1967.
H. Katona dio la siguiente prueba breve utilizando la doble contabilidad.
La observación clave de Katona es que a lo sumo intervalos
[19] Una generalización del teorema se aplica a subconjuntos que deben tener intersecciones grandes.
suficientemente grande con respecto a los otros dos parámetros, el teorema generalizado afirma que el tamaño de una familia de subconjuntos que intersecan
, y no se mantiene para valores más pequeños de
elementos corresponden a los emparejamientos perfectos de un grafo bipartito completo
y el teorema afirma que, entre las familias de emparejamientos perfectos cada par de los cuales comparte 𝑡 aristas, las familias más grandes están formadas por los emparejamientos que contienen todos 𝑡 aristas elegidas.
En una geometría parcial, el mayor sistema de rectas que se intersecan por pares puede obtenerse a partir del conjunto de rectas que pasan por un único punto.
[26] Para cadenas de longitud 𝑛 sobre un alfabeto de tamaño 𝑞, se puede definir que dos cadenas se intersecan si tienen una posición en la que ambas comparten el mismo símbolo.
cadenas, y son las únicas familias de este tamaño que se cruzan por pares.
En términos más generales, las mayores familias de cadenas en las que cada dos tienen 𝑡 posiciones con símbolos iguales se obtienen eligiendo
, y construyendo la familia de cadenas que tienen cada una al menos
Estos resultados pueden interpretarse teóricamente en términos del método de Hamming.
[27] Una conjetura no demostrada, planteada por Gil Kalai y Karen Meagher, se refiere a otro análogo para la familia de triangulaciones de un polígono convexo con 𝑛 vértices.
puede obtenerse cortando un solo vértice del polígono por un triángulo, y eligiendo todas las formas de triangular el resto del polígono de vértices restantes
sea cualquier combinación convexa fija de estas variables.
