Teorema de Erdős-Ko-Rado

En matemáticas, el teorema de Erdős-Ko-Rado limita el número de conjuntos en una familia de conjuntos para los que cada dos conjuntos tienen al menos un elemento en común. Paul Erdős, Chao Ko y Richard Rado demostraron el teorema en 1938, pero no lo publicaron hasta 1961. Es parte del campo de la combinatoria y uno de los resultados centrales de la teoría de conjuntos extremos.

El teorema se aplica a las familias de conjuntos que todos tienen el mismo tamaño, r{displaystyle r}, y son todos los subconjuntos de un conjunto de tamaño más grande n{displaystyle n}. Una forma de construir una familia de conjuntos con estos parámetros, cada dos compartiendo un elemento, es elegir un único elemento para pertenecer a todos los subconjuntos, y luego formar todos los subconjuntos que contienen el elemento elegido. El teorema Erdős–Ko–Rado afirma que cuando n{displaystyle n} es lo suficientemente grande para que el problema no sea ()n≥ ≥ 2r{displaystyle ngeq 2r}) esta construcción produce las mayores familias intersectas posibles. Cuando n=2r{displaystyle n=2r} hay otras familias igualmente grandes, pero para mayores valores n{displaystyle n} sólo las familias construidas de esta manera pueden ser más grandes.

El teorema de Erdős-Ko-Rado también se puede describir en términos de hipergrafías o conjuntos independientes en las gráficas de Kneser. 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. Nuevamente describen las familias de intersección más grandes posibles como formadas al elegir un elemento y formar la familia de todos los objetos que contienen el elemento elegido.

Declaración

Supongamos que A{displaystyle {fnMithcal}} es una familia distinta r{displaystyle r}- Elemento subconjuntos de un n{displaystyle n}- Elemento set con n≥ ≥ 2r{displaystyle ngeq 2r}, y que cada dos subconjuntos comparten al menos un elemento. Entonces el teorema declara que el número de sets en A{displaystyle {fnMithcal}} es en la mayoría del coeficiente binomio

()n− − 1r− − 1).{displaystyle {binom {n-1}{r-1}}

n≥ ≥ 2r{displaystyle ngeq 2r}

r{displaystyle r}- Elemento

r{displaystyle r}- Elemento

tamaño ()nr){fnMicrosoft}}.

El mismo resultado se puede formular como parte de la teoría de los hipergrafos. Una familia de conjuntos también puede llamarse hipergrafía, y cuando todos los conjuntos (que se llaman "hiperedges" en este contexto) son los mismos tamaño r{displaystyle r}, se llama r{displaystyle r}- Único hipergrafía. El teorema da así un límite superior para el número de hiperedges pares superpuestos en un r{displaystyle r}- Único hipergrafía con n{displaystyle n} vertices y n≥ ≥ 2r{displaystyle ngeq 2r}.

El teorema también puede ser formulado en términos de teoría del gráfico: el número de independencia del gráfico Kneser KGn,r{displaystyle KG_{n,r} para n≥ ≥ 2r{displaystyle ngeq 2r} es

α α ()KGn,r)=()n− − 1r− − 1).{displaystyle alpha (KG_{n,r})={binom {n-1}{r-1}}}

r{displaystyle r}- Elemento

n{displaystyle n}- Elemento

exactamente n/k{displaystyle No..

Historia

Paul Erdős, Chao Ko, y Richard Rado probaron este teorema en 1938 después de trabajar juntos en él en Inglaterra. Rado había pasado de Berlín a la Universidad de Cambridge y Erdős de Hungría a la Universidad de Manchester, escapando a la influencia de la Alemania nazi; Ko era estudiante de Louis J. Mordell en Manchester. Sin embargo, no publicaron el resultado hasta 1961, con el largo retraso que ocurre en parte debido a la falta de interés en la teoría de conjunto combinatorio en los años 1930, y mayor interés en el tema en la década de 1960. El documento de 1961 declaró el resultado en una forma aparentemente más general, en la que los subconjuntos sólo tenían que ser de tamaño a la mayoría r{displaystyle r}, y para satisfacer el requisito adicional de que ningún subconjunto esté contenido en cualquier otro. Una familia de subconjuntos que reúnen estas condiciones se puede ampliar a subconjuntos de tamaño exactamente r{displaystyle r} o bien por una aplicación de Teorema de matrimonio de Hall, o eligiendo cada subconjunto agrandado de la misma cadena en una descomposición de cadena simétrica de conjuntos.

Familias máximas y máximas

Familias de tamaño máximo

Una manera sencilla de construir una familia intersecante r{displaystyle r}- Elemento conjuntos cuyo tamaño coincide exactamente con el límite Erdős–Ko–Rado es elegir cualquier tipo fijo elemento x{displaystyle x}, y dejar A{displaystyle {fnMithcal}} consiste en todos r{displaystyle r}- Elemento subconjuntos que incluir x{displaystyle x}. Por ejemplo, para subconjuntos de 2 elementos de los 4 elementos set {}1,2,3,4}{displaystyle {1,2,3,4}}, con x=1{displaystyle x=1}, esto produce la familia

{}1,2}{displaystyle {1,2}}, {}1,3}{displaystyle {1,3}}, y {}1,4}{displaystyle {1,4}}.

Cualquier dos juegos en esta familia se intersectan, porque ambos incluir 1{displaystyle 1}. El número de conjuntos es ()n− − 1r− − 1){displaystyle {tbinom {n-1}{r-1}}, porque después de la elección del elemento fijo queda n− − 1{displaystyle n-1} otros elementos para elegir, y cada conjunto elige r− − 1{displaystyle r-1} de estos elementos restantes.

Cuando 2r}" xmlns="http://www.w3.org/1998/Math/MathML">n■2r{displaystyle n confiado2r}2r}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8fb1d87e80d679fb54fb1010f751d349649a8ef3" style="vertical-align: -0.338ex; width:6.704ex; height:2.176ex;"/> esta es la única familia intersecante de este tamaño. Sin embargo, cuando n=2r{displaystyle n=2r}, hay una construcción más general. Cada uno r{displaystyle r}- Elemento set se puede combinar con su complemento, el único r{displaystyle r}- Elemento establecido desde el cual es descomunal. Luego, elija un conjunto de cada uno de estos pares complementarios. Por ejemplo, para los mismos parámetros arriba, esta construcción más general se puede utilizar para formar la familia

{}3,4}{displaystyle {3,4}}, {}2,4}{displaystyle {2,4}}, y {}2,3}{displaystyle {2,3}},

donde cada dos conjuntos se cruzan a pesar de que ningún elemento pertenece a los tres conjuntos. En este ejemplo, todos los conjuntos se han complementado con los del primer ejemplo, pero también es posible complementar solo algunos de los conjuntos.

Cuando 2r}" xmlns="http://www.w3.org/1998/Math/MathML">n■2r{displaystyle n confiado2r}2r}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8fb1d87e80d679fb54fb1010f751d349649a8ef3" style="vertical-align: -0.338ex; width:6.704ex; height:2.176ex;"/>, las familias de primer tipo (conocidas como estrellas, dictaduras, juntas, familias centradas o familias principales) son las familias máximas únicas. En este caso, una familia de tamaño casi máximo tiene un elemento común a casi todo su Sets. Esta propiedad ha sido llamada estabilidad, Aunque el mismo término también se ha utilizado para una propiedad diferente, el hecho de que (para una amplia gama de parámetros) elimine los bordes escogidos aleatoriamente del gráfico Kneser no aumenta el tamaño de su independiente Sets.

Familias de máxima intersección

Una familia intersectiva de r{displaystyle r}- Elemento los conjuntos pueden ser máximos, ya que no se puede añadir ningún nuevo conjunto (incluso al extender el conjunto de tierra) sin destruir la propiedad de la intersección, pero no de tamaño máximo. Un ejemplo con n=7{displaystyle n=7} y r=3{displaystyle r=3} es el conjunto de siete líneas del avión Fano, mucho menos que el límite Erdős–Ko–Rado of 15. Más generalmente, las líneas de cualquier plano de orden proyector finito q{displaystyle q} forma una familia de intersección máxima que incluye sólo n{displaystyle n} para los parámetros r=q+1{displaystyle r=q+1} y n=q2+q+1{displaystyle n=q^{2}+q+1}. El avión Fano es el caso q=2{displaystyle q=2} de esta construcción.

El tamaño más pequeño posible de una familia de máxima intersección r{displaystyle r}- Elemento en términos de r{displaystyle r}, se desconoce pero al menos 3r{displaystyle 3r} para r≥ ≥ 4{displaystyle rgeq 4}. Los planos de proyecto producen familias de máxima intersección cuyo número de conjuntos es r2− − r+1{displaystyle r^{2}-r+1}, pero para infinitamente muchas opciones r{displaystyle r} existen familias de intersección máxima más pequeñas tamaño 34r2{displaystyle {tfrac {3}}r^{2}.

Las familias más grandes de intersección r{displaystyle r}- Elemento conjuntos que son maximal pero no máximo tienen tamaño

()n− − 1r− − 1)− − ()n− − r− − 1r− − 1)+1.{benom {binom} {binom}} {binom} {n-r-1}{r-1}+1.}

elemento x{displaystyle x}

r{displaystyle r}- Elemento

set Y{displaystyle Sí.

que contiene x{displaystyle x},

Y{displaystyle Sí.

r{displaystyle r}- Elemento

x{displaystyle x}

de Y{displaystyle Sí..

Pruebas

La prueba original del teorema Erdős–Ko–Rado usó la inducción on n{displaystyle n}. El caso base, para n=2r{displaystyle n=2r}, sigue fácilmente de los hechos que una familia que se intersecte no puede incluir tanto un conjunto como su complemento, y que en este caso el vínculo del teorema Erdős–Ko–Rado es exactamente la mitad del número de todos r{displaystyle r}- Elemento Sets. El paso de la inducción más grande n{displaystyle n} usa un método llamado Cambio, de la sustitución de elementos en la intersección de familias para hacer la familia más pequeña en el orden lexicográfico y reducirla a una forma canónica que es más fácil analizar.

En 1972, Gyula O. H. Katona dio la siguiente prueba corta usando doble conteo.

Vamos A{displaystyle {fnMithcal}} ser cualquier familia intersecting de r{displaystyle r}- Elemento subconjuntos de un n{displaystyle n}- Elemento Listo. Arregla todos n{displaystyle n} elementos en cualquier orden cíclico, y considerar los conjuntos de A{displaystyle {fnMithcal}} que forman intervalos de longitud r{displaystyle r} dentro de este orden cíclico elegido. Por ejemplo si n=8{displaystyle n=8} y r=3{displaystyle r=3}, una posible orden cíclica para los números {}1,2,...,8}{displaystyle {1,2,...,8}} es la orden ()3,1,5,4,2,7,6,8){displaystyle (3,1,5,4,2,7,6,8)}, que tiene ocho intervalos de 3 elementos (incluyendo los que envuelven):

()3,1,5){displaystyle (3,1,5)}, ()1,5,4){displaystyle (1,5,4)}, ()5,4,2){displaystyle (5,4,2)}, ()4,2,7){displaystyle (4,2,7)}, ()2,7,6){displaystyle (2,7,6)}, ()7,6,8){displaystyle (7,6,8)}, ()6,8,3){displaystyle (6,8,3)}, y ()8,3,1){displaystyle (8,3,1)}.

Sin embargo, sólo algunos de estos intervalos pueden pertenecer a A{displaystyle {fnMithcal}}, porque no todos intersectan. La observación clave de Katona es que al menos r{displaystyle r} intervalos de una sola orden cíclica pueden pertenecer a A{displaystyle {fnMithcal}}. Esto es porque, si ()a1,a2,...... ,ar){displaystyle (a_{1},a_{2},dotsa_{r}} es uno de estos intervalos, luego cada otro intervalo del mismo orden cíclico que pertenece a A{displaystyle {fnMithcal}} separaciones ai{displaystyle A_{i} desde ai+1{displaystyle a_{i+1}}, para algunos i{displaystyle i}, conteniendo precisamente uno de estos dos elementos. Los dos intervalos que separan estos elementos son descomunados, por lo que a la mayoría de ellos puede pertenecer a A{displaystyle {fnMithcal}}. Así, el número de intervalos en A{displaystyle {fnMithcal}} es a la mayoría de uno más el número r− − 1{displaystyle r-1} de pares que pueden ser separados.

Basado en esta idea, es posible contar el pares ()S,C){displaystyle (S,C)}, Donde S{displaystyle S. es un juego dentro A{displaystyle {fnMithcal}} y C{displaystyle C} es un orden cíclico para el cual S{displaystyle S. es un intervalo, de dos maneras. Primero, para cada conjunto S{displaystyle S. uno puede generar C{displaystyle C} por elegir uno de r!{displaystyle r} permutaciones de S{displaystyle S. y ()n− − r)!{displaystyle (n-r)} permutaciones de los elementos restantes, mostrando que el número de pares es SilencioASilencior!()n− − r)!{displaystyle Silencio{mathcal {A}!. Y segundo, hay ()n− − 1)!{displaystyle (n-1)} órdenes cíclicas, cada una de las cuales tiene r{displaystyle r} intervalos de A{displaystyle {fnMithcal}}, así que el número de pares está en más r()n− − 1)!{displaystyle r(n-1)}. Comparando estos dos cargos da la desigualdad

SilencioASilencior!()n− − r)!≤ ≤ r()n− − 1)!{displaystyle Silencio{mathcal {A} ¡Antes!

y dividir ambos lados por r!()n− − r)!{displaystyle r!(n-r)} da resultado

SilencioASilencio≤ ≤ r()n− − 1)!r!()n− − r)!=()n− − 1r− − 1).{displaystyle Silencio{mathcal {}leq {frac {r(n-1)}{r!(n-r)}}}={n-1 choose r-1}}

También es posible derivar el teorema de Erdős–Ko–Rado como un caso especial del teorema de Kruskal–Katona, otro resultado importante en la teoría de conjuntos extremos. Muchas otras demostraciones son conocidos.

Resultados relacionados

Generalizaciones

Una generalización del teorema se aplica a los subconjuntos que se requieren para tener intersecciones grandes. Esta versión del teorema tiene tres parámetros: n{displaystyle n}, el número de elementos de los subconjuntos se dibujan de, r{displaystyle r}, el tamaño de los subconjuntos, como antes, y t{displaystyle t}, el tamaño mínimo de la intersección de cada dos subconjuntos. Para la forma original del teorema Erdős–Ko–Rado, t=1{displaystyle t=1}. En general, para n{displaystyle n} lo suficientemente grande con respecto a los otros dos parámetros, el teorema generalizado declara que el tamaño de un t{displaystyle t}-intersecante familia de subconjuntos más

()n− − tk− − t).{displaystyle {binom} {n-t} {k-t}}

cuando n≥ ≥ ()t+1)()k− − t+1){displaystyle ngeq (t+1)(k-t+1)},

de n{displaystyle n}.

(t+1)(k-t+1)}" xmlns="http://www.w3.org/1998/Math/MathML">n■()t+1)()k− − t+1){displaystyle n título(t+1)(k-t+1)}(t+1)(k-t+1)}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bb1912b9c716b77bcb27eec9a5c46a6850dc0f5a" style="vertical-align: -0.838ex; width:21.848ex; height:2.843ex;"/>,

t{displaystyle t}-intersecante

t{displaystyle t} elementos

r{displaystyle r}- Elemento

t{displaystyle t}

La formulación gráfica-teorética correspondiente de esta generalización implica gráficos de Johnson en lugar de Kneser Gráficos. Para valores suficientemente grandes n{displaystyle n} y en particular para {tfrac {1}{2}}k^{2}}" xmlns="http://www.w3.org/1998/Math/MathML">n■12k2{displaystyle n confía{tfrac {1} {2}k^{2}}{tfrac {1}{2}}k^{2}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a9c6ab19d8d406e7240266d513667f0d88d11b01" style="vertical-align: -1.171ex; width:8.417ex; height:3.509ex;"/>, tanto el teorema Erdős–Ko–Rado como su generalización pueden fortalecerse del número de independencia a la capacidad Shannon de un gráfico: el gráfico Johnson correspondiente al gráfico t{displaystyle t}-intersecante r{displaystyle r}- Elemento subconjuntos tiene Shannon capacidad ()n− − tk− − t){displaystyle {tbinom} {n-t} {k-t}}.

El teorema también se puede generalizar a las familias en las que cada h{displaystyle h} los subconjuntos tienen una intersección común. Debido a que esto fortalece la condición de que cada par intersecta (para el cual h=2{displaystyle h=2}), estas familias tienen el mismo límite en su tamaño máximo, ()n− − 1r− − 1){displaystyle {tbinom {n-1}{r-1}} cuando n{displaystyle n} es suficientemente grande. Sin embargo, en este caso el significado de "suficientemente grande" se puede relajar de n≥ ≥ 2r{displaystyle ngeq 2r} a n≥ ≥ hh− − 1r{displaystyle ngeq {tfrac {h}{h-1}r}.

Análogos

Se conocen muchos resultados análogos al teorema de Erdős-Ko-Rado, pero para otras clases de objetos además de conjuntos finitos. Estos generalmente implican una declaración de que las familias más grandes de objetos que se intersecan, para alguna definición de intersección, se obtienen eligiendo un elemento y construyendo la familia de todos los objetos que incluyen ese elemento elegido. Los ejemplos incluyen lo siguiente:

Hay un q-analogo del teorema Erdős–Ko–Rado para la intersección de familias de subespacios lineales sobre campos finitos. Si S{displaystyle {fnMithcal}} es una familia intersecting de k{displaystyle k}-dimensional subespacios de un n{displaystyle n}-dimensional espacio vectorial sobre un campo finito orden q{displaystyle q}, y n≥ ≥ 2k{displaystyle ngeq 2k}, entonces

SilencioSSilencio≤ ≤ ()n− − 1k− − 1)q,{displaystyle Silencio {fnMitcal {fnh} {binom} {n-1}{k-1}_{q},}

Dos permutaciones en el mismo conjunto de elementos se definen para estar intersectiendo si hay algún elemento que tiene la misma imagen bajo ambas permutaciones. En una n{displaystyle n}- Elemento set, hay una familia obvia ()n− − 1)!{displaystyle (n-1)} intersección de permutaciones, las permutaciones que fijan uno de los elementos (el subgrupo estabilizador de este elemento). El teorema analógico es que ninguna familia intersecante de permutaciones puede ser más grande, y que las únicas familias intersectas de tamaño ()n− − 1)!{displaystyle (n-1)} son los cosets de estabilizadores de un elemento. Estos pueden describirse más directamente como las familias de permutaciones que mapean algún elemento fijo a otro elemento fijo. Más generalmente, para cualquier t{displaystyle t} y suficientemente grandes n{displaystyle n}, una familia de permutaciones cada par de que tiene t{displaystyle t} elementos en común tiene tamaño máximo ()n− − t)!{displaystyle (n-t)}, y las únicas familias de este tamaño son cosets de punta estabilizadores. Alternativamente, en términos teóricos gráficos, n{displaystyle n}- Elemento permutaciones corresponden a los perfectos emparejamientos de un gráfico bipartito completo Kn,n{displaystyle K_{n,n} y el teorema declara que, entre familias de perfectas coincidencias cada par de los cuales comparten t{displaystyle t} bordes, las familias más grandes están formadas por las coincidencias que todos contienen t{displaystyle t} elegido bordes. Otro analógico del teorema, para particiones de un conjunto, incluye como un caso especial las coincidencias perfectas de un gráfico completo Kn{displaystyle K_{n} (con n{displaystyle n} incluso). Hay ()n− − 1)!!{displaystyle (n-1)} coincidencias, donde !!{displaystyle!} denota el doble factorial. La familia más grande de emparejamientos que se intersecten pares (que significa que tienen un borde en común) tiene tamaño ()n− − 3)!!{displaystyle (n-3)! y se obtiene mediante la fijación de un borde y la elección de todas las formas de emparejar el resto n− − 2{displaystyle n-2} vertices.

Una geometría parcial es un sistema de un número finito de líneas y puntos abstractos, que satisface ciertos axiomas, incluido el requisito de que todas las líneas contengan el mismo número de puntos y que todos los puntos pertenezcan al mismo número de líneas. En una geometría parcial, se puede obtener un sistema más grande de líneas que se intersecan por pares a partir del conjunto de líneas a través de cualquier punto.

Un conjunto firmado consiste en un conjunto junto con la función de signo que mapea cada elemento a {}1,− − 1}{displaystyle {1,-1}}. Se puede decir que dos conjuntos firmados intersectan cuando tienen un elemento común que tiene el mismo signo en cada uno de ellos. Entonces una familia intersecante r{displaystyle r}- Elemento conjuntos firmados, extraídos de n{displaystyle n}- Elemento universo, consiste en la mayoría

2r− − 1()n− − 1r− − 1){displaystyle 2^{r-1}{binom} {n-1}{r-1}}

r− − 1{displaystyle r-1}

Para cuerdas de longitud n{displaystyle n} sobre un alfabeto tamaño q{displaystyle q}, dos cadenas se pueden definir para intersegir si tienen una posición donde ambos comparten el mismo símbolo. Las familias más grandes de intersección se obtienen eligiendo una posición y un símbolo fijo para esa posición, y dejando que el resto de las posiciones varían arbitrariamente. Estas familias consisten en qn− − 1{textstyle q^{n-1} cuerdas, y son las únicas familias pares que intersectan de este tamaño. Más generalmente, las familias más grandes de cadenas en las que cada dos tienen t{displaystyle t} posiciones con símbolos iguales se obtienen eligiendo t+2i{displaystyle t+2i} posiciones y símbolos para esas posiciones, para un número i{displaystyle i} que depende de n{displaystyle n}, q{displaystyle q}, y t{displaystyle t}, y la construcción de la familia de cuerdas que cada uno tiene al menos t+i{displaystyle t+i} de los símbolos elegidos. Estos resultados se pueden interpretar gráficamente en términos de Un plan de adelgazamiento.

Una conjetura no probada, planteada por Gil Kalai y Karen Meagher, se refiere a otro análogo para la familia de triangulación de un polígono convexo con n{displaystyle n} vertices. El número de todas las triangulaciones es un Número catalán Cn− − 2{displaystyle C_{n-2}, y la conjetura declara que una familia de triangulación cada par de las cuales comparte un borde tiene el máximo tamaño Cn− − 3{displaystyle C_{n-3}. Una familia de tamaño que intersecte exactamente Cn− − 3{displaystyle C_{n-3} puede obtenerse cortando un solo vértice del polígono por un triángulo, y eligiendo todas las formas de triangular el restante ()n− − 1){displaystyle (n-1)}-vertex poligonal.

Aplicaciones

El teorema Erdős–Ko–Rado se puede utilizar para probar el siguiente resultado en la teoría de probabilidad. Vamos xi{displaystyle x_{i}} ser independiente 0–1 variables aleatorias con probabilidad p≥ ≥ 12{displaystyle pgeq {tfrac {1}{2}}} de ser uno, y dejar c()x→ → ){displaystyle c({vec {x})} ser cualquier combinación convexa fija de estas variables. Entonces...

Pr[c()x→ → )≥ ≥ 12]≥ ≥ p.{displaystyle Pr left[c({vec {x})geq {tfrac {1}{2}right]geq P.}

Las propiedades de estabilidad del teorema de Erdős-Ko-Rado juegan un papel clave en un algoritmo eficiente para encontrar bordes monocromáticos en coloraciones incorrectas de gráficos de Kneser. El teorema de Erdős-Ko-Rado también se ha utilizado para caracterizar las simetrías del espacio de los árboles filogenéticos.