Teorema de Erdős-Ko-Rado

Límite superior en familias de conjuntos que se cruzan

Dos familias que se cruzan de subconjuntos de dos elementos de un conjunto de cuatro elementos. Todos los conjuntos de la familia izquierda contienen el elemento inferior izquierdo. Los decorados de la familia adecuada evitan este elemento.

En matemáticas, el teorema de Erdős-Ko-Rado limita el número de conjuntos en una familia de conjuntos para los cuales 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 . ^[1]

El teorema se aplica a familias de conjuntos que tienen el mismo tamaño, y ${\displaystyle r}$ son todos subconjuntos de algún conjunto mayor de tamaño . Una forma de construir una familia de conjuntos con estos parámetros, cada uno de los cuales comparte un elemento, es elegir un solo elemento para que pertenezca a todos los subconjuntos y luego formar todos los subconjuntos que contienen el elemento elegido. El teorema de Erdős-Ko-Rado establece que cuando es lo suficientemente grande como para que el problema no sea trivial ( ), esta construcción produce las familias que se cruzan más grandes posibles. Cuando hay otras familias igualmente grandes, pero para valores mayores solo las familias construidas de esta manera pueden ser más grandes. ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n\geq 2r}$ ${\displaystyle n=2r}$ ${\displaystyle n}$

El teorema de Erdős-Ko-Rado también se puede describir en términos de hipergrafos o conjuntos independientes en gráficos de Kneser . Varios teoremas análogos se aplican a otros tipos de objetos matemáticos además de los conjuntos, incluidos los subespacios lineales , las permutaciones y las cadenas . Nuevamente describen que las familias que se cruzan más grandes posibles se forman eligiendo un elemento y formando la familia de todos los objetos que contienen el elemento elegido.

Declaración

Supongamos que es una familia de subconjuntos de elementos distintos de un conjunto de elementos con y que cada dos subconjuntos comparten al menos un elemento. Entonces el teorema establece que el número de conjuntos es como máximo el coeficiente binomial ${\displaystyle {\mathcal {A}}}$ ${\displaystyle r}$ ${\displaystyle n}$ ${\displaystyle n\geq 2r}$ ${\displaystyle {\mathcal {A}}}$

$${\displaystyle {\binom {n-1}{r-1}}.}$$

cuando ,los elementoslos elementostamaño . ^[2] ${\displaystyle n\geq 2r}$ ${\displaystyle n<2r}$ ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle {\tbinom {n}{r}}}$

El mismo resultado puede formularse como parte de la teoría de los hipergrafos . Una familia de conjuntos también puede denominarse hipergrafo, y cuando todos los conjuntos (que en este contexto se denominan "hiperbordes") tienen el mismo tamaño , ${\displaystyle r}$ se denomina hipergrafo uniforme . Por tanto, el teorema proporciona un límite superior para el número de hiperbordes superpuestos por pares en un hipergrafo uniforme con vértices y . ^[3] ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle n}$ ${\displaystyle n\geq 2r}$

El gráfico de Kneser , con un vértice para cada subconjunto de 2 elementos del conjunto de 5 elementos {1,2,3,4,5} y una arista para cada par de subconjuntos disjuntos. Según el teorema de Erdős-Ko-Rado, los conjuntos independientes en este gráfico tienen como máximo cuatro vértices. ${\displaystyle KG_{5,2}}$

El teorema también puede formularse en términos de teoría de grafos : el número de independencia del gráfico de Kneser para es ${\displaystyle KG_{n,r}}$ ${\displaystyle n\geq 2r}$

$${\displaystyle \alpha (KG_{n,r})={\binom {n-1}{r-1}}.}$$

de elementosde elementosconjuntos disjuntosconjunto independienteconjunto independiente más grande. ^[4]gráficos transitivos de vérticesnúmero cromático fraccionarioexactamente . ^[5] ${\displaystyle r}$ ${\displaystyle n}$ ${\displaystyle n/r}$

Historia

Paul Erdős , Chao Ko y Richard Rado demostraron este teorema en 1938 después de trabajar juntos en él en Inglaterra. Rado se había trasladado de Berlín a la Universidad de Cambridge y Erdős de Hungría a la Universidad de Manchester , ambos escapando de la influencia de la Alemania nazi; Ko fue alumno de Louis J. Mordell en Manchester. ^[6] Sin embargo, no publicaron el resultado hasta 1961, ^[7] y el largo retraso se debió en parte a la falta de interés en la teoría combinatoria de conjuntos en la década de 1930 y al aumento del interés en el tema en la década de 1960. ^[6] El artículo de 1961 expresó el resultado en una forma aparentemente más general, en la que solo se requería que los subconjuntos tuvieran un tamaño como máximo de , ${\displaystyle r}$ y que cumplieran el requisito adicional de que ningún subconjunto estuviera contenido en ningún otro. ^[7] Una familia de subconjuntos que cumplen estas condiciones se puede ampliar a subconjuntos de tamaño exactamente ${\displaystyle r}$ mediante una aplicación del teorema de matrimonio de Hall , ^[8] o eligiendo cada subconjunto ampliado de la misma cadena en una descomposición de conjuntos en cadena simétrica. ^[9]

Familias máximas y máximas.

Familias de tamaño máximo

El gráfico de Johnson , con un vértice para cada subconjunto de dos elementos de {1,2,3,4} y un borde que conecta pares de subconjuntos que se cruzan, dispuestos geométricamente como un octaedro con conjuntos disjuntos en vértices opuestos. Las familias que se cruzan más grandes provienen de las caras triangulares de este octaedro. Reemplazar un conjunto de una de estas familias por su complemento corresponde a pasar de un triángulo a uno de sus tres triángulos vecinos. ${\displaystyle J(4,2)}$ ${\displaystyle r=2}$ ${\displaystyle n=2r=4}$

Una forma sencilla de construir una familia de conjuntos de elementos que se cruzan cuyo tamaño coincida exactamente con el límite de Erdős-Ko-Rado es elegir cualquier elemento fijo y dejar que esté formado por todos los subconjuntos de elementos que incluyan . Por ejemplo, para subconjuntos de 2 elementos del conjunto de 4 elementos , con , esto produce la familia ${\displaystyle r}$ ${\displaystyle x}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle r}$ ${\displaystyle x}$ ${\displaystyle \{1,2,3,4\}}$ ${\displaystyle x=1}$

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

Dos conjuntos cualesquiera de esta familia se cruzan porque ambos incluyen . ${\displaystyle 1}$El número de conjuntos es , porque después de elegir el elemento fijo quedan otros elementos para elegir, y cada conjunto elige entre estos elementos restantes. ^[10] ${\displaystyle {\tbinom {n-1}{r-1}}}$ ${\displaystyle n-1}$ ${\displaystyle r-1}$

Cuando esta es la única familia que se cruza de este tamaño. Sin embargo, cuando , hay una construcción más general. Cada conjunto de elementos se puede hacer coincidir con su complemento , el único conjunto de elementos del que está separado. Luego, elige un conjunto de cada uno de estos pares complementarios. Por ejemplo, para los mismos parámetros anteriores, esta construcción más general se puede utilizar para formar la familia ${\displaystyle n>2r}$ ${\displaystyle n=2r}$ ${\displaystyle r}$ ${\displaystyle r}$

${\displaystyle \{3,4\}}$, , y , ${\displaystyle \{2,4\}}$ ${\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 a partir de los del primer ejemplo, pero también es posible complementar solo algunos de los conjuntos. ^[10]

Cuando , ${\displaystyle n>2r}$ las familias del primer tipo (conocidas también como estrellas, ^[1] dictaduras, ^[11] juntas, ^[11] familias centradas, ^[12] o familias principales ^[13] ) son las únicas familias máximas. En este caso, una familia de tamaño casi máximo tiene un elemento común a casi todos sus conjuntos. ^[14] Esta propiedad se ha denominado estabilidad , ^[13] 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) eliminar bordes elegidos aleatoriamente del gráfico de Kneser no aumenta la tamaño de sus conjuntos independientes. ^[15]

Familias máximas que se cruzan

Los siete puntos y las siete líneas (una dibujada como un círculo) del plano de Fano forman una familia de intersección máxima.

Una familia de conjuntos de elementos que se cruzan puede ser máxima, en el sentido de que no se puede agregar ningún conjunto adicional (incluso extendiendo el conjunto básico) sin destruir la propiedad de intersección, pero no del tamaño máximo. Un ejemplo con y es el conjunto de siete líneas del plano de Fano , mucho menos que el límite de 15 de Erdős-Ko-Rado ^{. [16]} De manera más general, las líneas de cualquier plano de orden proyectivo finito forman una familia de intersección máxima que incluye sólo establece, para los parámetros y . El avión de Fano es el caso de esta construcción. ^[17] ${\displaystyle r}$ ${\displaystyle n=7}$ ${\displaystyle r=3}$ ${\displaystyle q}$ ${\displaystyle n}$ ${\displaystyle r=q+1}$ ${\displaystyle n=q^{2}+q+1}$ ${\displaystyle q=2}$

Se desconoce el tamaño más pequeño posible de una familia máxima de conjuntos de elementos que se cruzan , en términos de , pero al menos para . ^[18] Los planos proyectivos producen familias máximas que se cruzan cuyo número de conjuntos es , pero para infinitas opciones de existen familias máximas que se cruzan más pequeñas de tamaño . ^[17] ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle 3r}$ ${\displaystyle r\geq 4}$ ${\displaystyle r^{2}-r+1}$ ${\displaystyle r}$ ${\displaystyle {\tfrac {3}{4}}r^{2}}$

Las familias más grandes de conjuntos de elementos que se cruzan y que son máximas pero no máximas tienen tamaño ${\displaystyle r}$

$${\displaystyle {\binom {n-1}{r-1}}-{\binom {n-r-1}{r-1}}+1.}$$

elemento ${\displaystyle x}$conjunto de elementoscontienen ,de elementosde . teorema de Hilton-MilnerAnthony HiltonEric Charles Milner1967. ^[19] ${\displaystyle r}$ ${\displaystyle Y}$ ${\displaystyle x}$ ${\displaystyle Y}$ ${\displaystyle r}$ ${\displaystyle x}$ ${\displaystyle Y}$

Pruebas

La prueba original del teorema de Erdős-Ko-Rado utilizó la inducción en . ${\displaystyle n}$El caso base, para , ${\displaystyle n=2r}$ se desprende fácilmente del hecho de que una familia que se interseca no puede incluir tanto un conjunto como su complemento , y que en este caso la cota del teorema de Erdős-Ko-Rado es exactamente la mitad del número de conjuntos de todos elementos . El paso de inducción para tamaños más grandes utiliza un método llamado desplazamiento , que consiste en sustituir elementos en familias que se cruzan para hacer la familia más pequeña en orden lexicográfico y reducirla a una forma canónica que sea más fácil de analizar. ^[20] ${\displaystyle r}$ ${\displaystyle n}$

En 1972, Gyula OH Katona dio la siguiente breve prueba utilizando doble conteo . ^[21]

Sea cualquier familia que se cruce de subconjuntos de elementos de un conjunto de elementos . Organice todos los elementos en cualquier orden cíclico y considere los conjuntos de ese formulario en intervalos de longitud dentro de este orden cíclico elegido. Por ejemplo, si y , un posible orden cíclico para los números es el orden , que tiene ocho intervalos de 3 elementos (incluidos los que se enrollan): ${\displaystyle {\mathcal {A}}}$ ${\displaystyle r}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle r}$ ${\displaystyle n=8}$ ${\displaystyle r=3}$ ${\displaystyle \{1,2,...,8\}}$ ${\displaystyle (3,1,5,4,2,7,6,8)}$

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

Sin embargo, sólo algunos de estos intervalos pueden pertenecer a , ${\displaystyle {\mathcal {A}}}$ porque no todos se cruzan. La observación clave de Katona es que en la mayoría de los intervalos de un único orden cíclico pueden pertenecer a . Esto se debe a que, si es uno de estos intervalos, entonces cualquier otro intervalo del mismo orden cíclico al que pertenece se separa de , para algunos , al contener precisamente uno de estos dos elementos. Los dos intervalos que separan estos elementos son disjuntos, por lo que como máximo uno de ellos puede pertenecer a . Así, el número de intervalos es como máximo uno más el número de pares que se pueden separar. ^[21] ${\displaystyle r}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle (a_{1},a_{2},\dots ,a_{r})}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle a_{i}}$ ${\displaystyle a_{i+1}}$ ${\displaystyle i}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle r-1}$

Con base en esta idea, es posible contar los pares , ${\displaystyle (S,C)}$ donde es un conjunto y es un orden cíclico para el cual es un intervalo, de dos maneras. Primero, para cada conjunto se puede generar eligiendo una de las permutaciones de y permutaciones de los elementos restantes, lo que demuestra que el número de pares es . Y en segundo lugar, hay órdenes cíclicas, cada una de las cuales tiene como máximo intervalos de , por lo que el número de pares es como máximo . La comparación de estos dos recuentos da la desigualdad ${\displaystyle S}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle C}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle C}$ ${\displaystyle r!}$ ${\displaystyle S}$ ${\displaystyle (n-r)!}$ ${\displaystyle |{\mathcal {A}}|r!(n-r)!}$ ${\displaystyle (n-1)!}$ ${\displaystyle r}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle r(n-1)!}$

$${\displaystyle |{\mathcal {A}}|r!(n-r)!\leq r(n-1)!}$$

y dividiendo ambos lados por da el resultado ^[21] ${\displaystyle r!(n-r)!}$

$${\displaystyle |{\mathcal {A}}|\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 . ^[22] Se conocen muchas otras pruebas . ^[23]

Resultados relacionados

Generalizaciones

Se aplica una generalización del teorema a subconjuntos que deben tener intersecciones grandes. Esta versión del teorema tiene tres parámetros: , el número de elementos de los que se extraen los subconjuntos, , el tamaño de los subconjuntos, como antes, y , el tamaño mínimo de la intersección de dos subconjuntos cualesquiera. Para la forma original del teorema de Erdős-Ko-Rado, . En general, para valores suficientemente grandes con respecto a los otros dos parámetros, el teorema generalizado establece que el tamaño de una familia de subconjuntos que se cruzan es como máximo ^[24] ${\displaystyle n}$ ${\displaystyle r}$ ${\displaystyle t}$ ${\displaystyle t=1}$ ${\displaystyle n}$ ${\displaystyle t}$

$${\displaystyle {\binom {n-t}{k-t}}.}$$

cuando , ${\displaystyle n\geq (t+1)(k-t+1)}$de . ${\displaystyle n}$,que se cruzanelementoslos. ^[25]tAhlswedeteorema de Ahlswede-Khachatrian^[26] ${\displaystyle n>(t+1)(k-t+1)}$ ${\displaystyle t}$ ${\displaystyle t}$ ${\displaystyle r}$ ${\displaystyle t}$ ${\displaystyle n<(t+1)(k-t+1)}$

La correspondiente formulación teórica de grafos de esta generalización implica gráficos de Johnson en lugar de gráficos de Kneser. ^[27] Para valores suficientemente grandes de y en particular para , tanto el teorema de Erdős-Ko-Rado como su generalización pueden fortalecerse desde el número de independencia hasta la capacidad de Shannon de un gráfico : el gráfico de Johnson correspondiente a los subconjuntos de elementos que se cruzan tiene capacidad de Shannon . ^[28] ${\displaystyle n}$ ${\displaystyle n>{\tfrac {1}{2}}k^{2}}$ ${\displaystyle t}$ ${\displaystyle r}$ ${\displaystyle {\tbinom {n-t}{k-t}}}$

El teorema también se puede generalizar a familias en las que todos los subconjuntos tienen una intersección común. Debido a que esto fortalece la condición de que cada par se cruza (para lo cual ), estas familias tienen el mismo límite en su tamaño máximo, cuando es suficientemente grande. Sin embargo, en este caso el significado de "suficientemente grande" se puede relajar de a . ^[29] ${\displaystyle h}$ ${\displaystyle h=2}$ ${\displaystyle {\tbinom {n-1}{r-1}}}$ ${\displaystyle n}$ ${\displaystyle n\geq 2r}$ ${\displaystyle n\geq {\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 los conjuntos finitos. Generalmente implican una afirmación de que las familias más grandes de objetos que se cruzan, 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 los siguientes:

Existe un q -análogo del teorema de Erdős-Ko-Rado para la intersección de familias de subespacios lineales sobre campos finitos . Si es una familia que se cruza de subespacios dimensionales de un espacio vectorial dimensional sobre un campo finito de orden , y , entonces ${\displaystyle {\mathcal {S}}}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle q}$ ${\displaystyle n\geq 2k}$

$${\displaystyle |{\mathcal {S}}|\leq {\binom {n-1}{k-1}}_{q},}$$

qcoeficiente binomial gaussianoespacio vectorialorden q . vector elegido. ^[30]

Se define que dos permutaciones en el mismo conjunto de elementos se cruzan si hay algún elemento que tiene la misma imagen en ambas permutaciones. En un conjunto de elementos , existe una familia obvia de permutaciones que se cruzan, las permutaciones que fijan uno de los elementos (el subgrupo estabilizador de este elemento). El teorema análogo es que ninguna familia de permutaciones que se cruzan puede ser más grande, y que las únicas familias de tamaño que se cruzan son las clases laterales de los estabilizadores de un elemento. Estos pueden describirse más directamente como familias de permutaciones que asignan un elemento fijo a otro elemento fijo. De manera más general, para cualquier y suficientemente grande , una familia de permutaciones cada par de las cuales tiene elementos en común tiene un tamaño máximo , y las únicas familias de este tamaño son las clases laterales de estabilizadores puntuales. ^[31] Alternativamente, en términos de teoría de grafos, las permutaciones de elementos corresponden a los emparejamientos perfectos de un grafo bipartito completo y el teorema establece que, entre familias de emparejamientos perfectos, cada par de los cuales comparte aristas, las familias más grandes están formadas por los emparejamientos. que todos contienen bordes elegidos . ^[32] Otro análogo del teorema, para particiones de un conjunto , incluye como caso especial los emparejamientos perfectos de un gráfico completo (con pares). Hay emparejamientos, donde denota el doble factorial . La familia más grande de coincidencias que se cruzan por pares (lo que significa que tienen una arista en común) tiene tamaño y se obtiene fijando una arista y eligiendo todas las formas de hacer coincidir los vértices restantes. ^[33] ${\displaystyle n}$ ${\displaystyle (n-1)!}$ ${\displaystyle (n-1)!}$ ${\displaystyle t}$ ${\displaystyle n}$ ${\displaystyle t}$ ${\displaystyle (n-t)!}$ ${\displaystyle n}$ ${\displaystyle K_{n,n}}$ ${\displaystyle t}$ ${\displaystyle t}$ ${\displaystyle K_{n}}$ ${\displaystyle n}$ ${\displaystyle (n-1)!!}$ ${\displaystyle !!}$ ${\displaystyle (n-3)!!}$ ${\displaystyle n-2}$

Una geometría parcial es un sistema de un número finito de puntos y líneas abstractos, que satisfacen 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 cruzan por pares a partir del conjunto de líneas que pasan por cualquier punto. ^[34]

Un conjunto con signo consta de un conjunto junto con una función de signo que asigna cada elemento a . ${\displaystyle \{1,-1\}}$Se puede decir que dos conjuntos con signo se cruzan cuando tienen un elemento común que tiene el mismo signo en cada uno de ellos. Entonces, una familia de conjuntos con signo de elementos que se cruzan , extraída de un universo de elementos , consta como máximo de ${\displaystyle r}$ ${\displaystyle n}$

$${\displaystyle 2^{r-1}{\binom {n-1}{r-1}}}$$

. ^[35] ${\displaystyle r-1}$

Para cadenas de longitud ${\displaystyle n}$ sobre un alfabeto de tamaño , ${\displaystyle q}$ se pueden definir dos cadenas para que se crucen si tienen una posición en la que ambas comparten el mismo símbolo. Las familias de intersección más grandes se obtienen eligiendo una posición y un símbolo fijo para esa posición, y dejando que el resto de las posiciones varíen arbitrariamente. Estas familias constan de cadenas y son las únicas familias de este tamaño que se cruzan por pares. De manera más general, las familias más grandes de cadenas en las que cada dos tienen posiciones con símbolos iguales se obtienen eligiendo posiciones y símbolos para esas posiciones, para un número que depende de , y , y construyendo la familia de cadenas que cada una tiene al menos de los símbolos elegidos. Estos resultados se pueden interpretar gráficamente en términos del esquema de Hamming . ^[36] ${\textstyle q^{n-1}}$ ${\displaystyle t}$ ${\displaystyle t+2i}$ ${\displaystyle i}$ ${\displaystyle n}$ ${\displaystyle q}$ ${\displaystyle t}$ ${\displaystyle t+i}$

Problema no resuelto en matemáticas :

¿Se obtiene la familia más grande de triangulaciones que se cruzan de un polígono convexo cortando un vértice y eligiendo todas las triangulaciones del polígono restante?

(más problemas sin resolver en matemáticas)

Una conjetura no probada , planteada por Gil Kalai y Karen Meagher, se refiere a otro análogo de la familia de triangulaciones de un polígono convexo con vértices. El número de todas las triangulaciones es un número catalán , y la conjetura establece que una familia de triangulaciones en las que cada par comparte una arista tiene un tamaño máximo . Se puede obtener una familia de tamaños que se interseca exactamente cortando un solo vértice del polígono por un triángulo y eligiendo todas las formas de triangular el polígono de vértice restante . ^[37] ${\displaystyle n}$ ${\displaystyle C_{n-2}}$ ${\displaystyle C_{n-3}}$ ${\displaystyle C_{n-3}}$ ${\displaystyle (n-1)}$

Aplicaciones

El teorema de Erdős-Ko-Rado se puede utilizar para demostrar el siguiente resultado en teoría de probabilidad . Sean variables aleatorias independientes 0–1 con probabilidad de ser uno, y sea cualquier combinación convexa fija de estas variables. Entonces ${\displaystyle x_{i}}$ ${\displaystyle p\geq {\tfrac {1}{2}}}$ ${\displaystyle c({\vec {x}})}$

$${\displaystyle \Pr \left[c({\vec {x}})\geq {\tfrac {1}{2}}\right]\geq p.}$$

vectores indicadoressubconjuntos. ^[38]

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

Ver también

• Teorema de Helly , sobre las condiciones que garantizan que las familias de conjuntos convexos que se cruzan tengan una intersección común
• Teorema de Sperner , un límite superior en familias de conjuntos no anidados por pares
• Sistema Steiner , familias de conjuntos uniformes de tamaño máximo en las que ningún par (en lugar de cada par) tiene una intersección grande
• Girasol (matemáticas) , una familia de conjuntos donde (a diferencia de las familias que se cruzan máximamente aquí) todos los pares tienen intersecciones iguales
• Thrackle , un problema sin resolver sobre el tamaño de familias de curvas que se cruzan

Referencias

Notas

1. Das y Tran (2016).
2. Aigner y Ziegler (2018); Godsil y Meagher (2015), pág. xiii.
3. Furedi (1995).
4. Harvey y madera (2014); Godsil y Meagher (2015), pág. xiv.
5. Godsil y Meagher (2015), pág. 43.
6. Anderson (2013).
7. Erdős, Ko y Rado (1961); Erdős (1987).
8. van Lint y Wilson (1992).
9. Anderson (1987).
10. Aigner y Ziegler (2018).
11. Dinur y Friedgut (2009).
12. Borg (2012).
13. Friedgut (2008).
14. Friedgut (2008); Dinur y Friedgut (2009); Das y Tran (2016).
15. Bollobás, Narayanan y Raigorodskii (2016); Balogh, Krueger y Luo (2022).
16. Polcyn y Ruciński (2017).
17. Füredi (1980).
18. Dow y otros. (1985).
19. Hilton y Milner (1967); Frankl y Furedi (1986); Godsil y Meagher (2015), Sección 1.6: El teorema de Hilton-Milner, págs. 15-17.
20. Erdős, Ko y Rado (1961); Godsil & Meagher (2015), Sección 1.1: La prueba original, págs.
21. Katona (1972); Anderson (1987); van Lint y Wilson (1992); Aigner y Ziegler (2018).
22. Godsil & Meagher (2015), Sección 1.5: El teorema de Kruskal-Katona, págs.
23. Frankl y Graham (1989); Godsil y Meagher (2015), pág. 22.
24. Erdős, Ko y Rado (1961); Godsil y Meagher (2015), Teorema 0.0.2, pág. xiv.
25. Wilson (1984); Godsil y Meagher (2015), pág. 2.
26. Ahlswede y Khachatrian (1997)
27. Godsil y Meagher (2015), pág. xiv.
28. Schrijver (1981); Deza y Frankl (1983).
29. Frankl (1976); Anderson (1987).
30. Frankl y Wilson (1986); Godsil & Meagher (2015), Capítulo 9: El esquema de Grassmann, págs. 161-183.
31. Frankl y Deza (1977); Cameron y Ku (2003); Larose y Malvenuto (2004); Godsil y Meagher (2009); Ellis, Friedgut y Pilpel (2011); Godsil & Meagher (2015), Capítulo 14: Permutaciones, págs.
32. Godsil & Meagher (2015), Sección 7.5: Coincidencias perfectas en gráficos bipartitos completos.
33. Godsil & Meagher (2015), Sección 15.2: Combinaciones perfectas, págs.
34. Godsil & Meagher (2015), Sección 5.6: Geometrías parciales, págs.
35. Bollobás & Líder (1997).
36. Ahlswede y Khachatrian (1998); Godsil & Meagher (2015), Capítulo 10: El esquema Hamming, págs. 184-209.
37. Olarte et al. (2020).
38. Liggett (1977); Anderson (1987).
39. Haviv (2022).
40. Bastón de molienda (2020).

Trabajos citados

• Ahlswede, Rudolf ; Khachatrian, Levon H. (1997). "El teorema de intersección completo para sistemas de conjuntos finitos". Revista europea de combinatoria . 18 : 125-136. doi : 10.1006/eujc.1995.0092 .
• Ahlswede, Rudolf; Khachatrian, Levon H. (1998), "El teorema diametral en espacios de Hamming: anticódigos óptimos", Avances en Matemáticas Aplicadas , 20 (4): 429–449, doi : 10.1006/aama.1998.0588 , MR  1612850
• Aigner, Martín ; Ziegler, Günter M. (2018), "Capítulo 30: Tres teoremas famosos sobre conjuntos finitos", Pruebas del LIBRO (6.a ed.), Springer, págs. 213–217, doi :10.1007/978-3-662-57265 -8_15, ISBN 978-3-662-57265-8, SEÑOR  3823190, Zbl  1392.00001
• Anderson, Ian (1987), "Capítulo 5: Sistemas que se cruzan y el teorema de Erdős-Ko-Rado", Combinatoria de conjuntos finitos , Oxford Science Publications, Oxford University Press, págs. 70–86, ISBN 0-19-853367-5, SEÑOR  0892525
• Anderson, Ian (2013), "Teoría de conjuntos combinatorios", en Wilson, Robin ; Watkins, John J. (eds.), Combinatoria: antigua y moderna , Oxford University Press, págs. 309–328, doi :10.1093/acprof:oso/9780199656592.003.0014, ISBN 978-0-19-965659-2, señor  3204727
• Balogh, József ; Krueger, Robert A.; Luo, Haoran (2022), "Umbral agudo para el teorema de Erdős-Ko-Rado", Algoritmos y estructuras aleatorias , 62 : 3–28, arXiv : 2105.02985 , doi : 10.1002/rsa.21090, S2CID  234093039
• Bollobás, Béla ; Leader, Imre (1997), "Un teorema de Erdős-Ko-Rado para conjuntos con signo", Computadoras y matemáticas con aplicaciones , 34 (11): 9–13, doi : 10.1016/S0898-1221(97)00215-0 , SEÑOR  1486880, Zbl  0901.05088
• Bollobás, Béla ; Narayanan, Bhargav P.; Raigorodskii, Andrei M. (2016), "Sobre la estabilidad del teorema de Erdős-Ko-Rado", Journal of Combinatorial Theory , Serie A, 137 : 64–78, arXiv : 1408.1288 , doi : 10.1016/j.jcta.2015.08 .002 , SEÑOR  3403515
• Borg, Peter (2012), "Subfamilias de familias hereditarias que se cruzan", Journal of Combinatorial Theory , Serie A, 119 (4): 871–881, arXiv : 1103.3858 , doi : 10.1016/j.jcta.2011.12. 002 , señor  2881232
• Cameron, Peter J .; Ku, CY (2003), "Familias de permutaciones que se cruzan", European Journal of Combinatorics , 24 (7): 881–890, doi : 10.1016/S0195-6698(03)00078-7 , MR  2009400, Zbl  1026.05001
• Das, Shagnik; Tran, Tuan (2016), "Eliminación y estabilidad de Erdős – Ko – Rado", Revista SIAM de Matemáticas Discretas , 30 (2): 1102–1114, doi :10.1137/15M105149X, MR  3504983
• Deza, Michel ; Frankl, Péter (1983), "Teorema de Erdős-Ko-Rado - 22 años después", Revista SIAM sobre métodos algebraicos y discretos , 4 (4): 419–431, doi :10.1137/0604042, SEÑOR  0721612
• Dinur, Irit ; Friedgut, Ehud (2009), "Las familias que se cruzan están esencialmente contenidas en juntas", Combinatoria, probabilidad y computación , 18 (1–2): 107–122, doi :10.1017/S0963548308009309, MR  2497376, S2CID  8923303
• Dow, Stephen J.; Drake, David A .; Füredi, Zoltán; Larson, Jean A. (1985), "Un límite inferior para la cardinalidad de una familia máxima de conjuntos de igual tamaño que se cruzan mutuamente", Actas de la decimosexta conferencia internacional del Sureste sobre combinatoria, teoría de grafos e informática (Boca Raton, Florida, 1985), Congressus Numerantium , 48 : 47–48, SEÑOR  0830697
• Ellis, David; Friedgut, Aod; Pilpel, Haran (2011), "Familias de permutaciones que se cruzan", Revista de la Sociedad Matemática Estadounidense , 24 (3): 649–682, arXiv : 1011.3342 , doi : 10.1090/S0894-0347-2011-00690-5, SEÑOR  2784326 , S2CID  9198144
• Erdős, Paul (1987), "Mi trabajo conjunto con Richard Rado" (PDF) , en Whitehead, C. (ed.), Surveys in combinatorics, 1987: Artículos invitados para la Undécima Conferencia Combinatoria Británica , Serie de notas de conferencias de la London Mathematical Society , vol. 123, Cambridge University Press, págs. 53–80, ISBN 978-0-521-34805-8, SEÑOR  0905276, Zbl  0623.01010
• Erdős, P .; Ko, Chao ; Rado, R. (1961), "Teoremas de intersección para sistemas de conjuntos finitos" (PDF) , Quarterly Journal of Mathematics , Second Series, 12 : 313–320, doi : 10.1093/qmath/12.1.313 , MR  0140419, Zbl  0100.01902
• Frankl, Péter (1976), "Sobre las familias Sperner que satisfacen una condición adicional", Journal of Combinatorial Theory , Serie A, 20 (1): 1–11, doi : 10.1016/0097-3165(76)90073-x , MR  0398842
• Frankl, Peter ; Deza, Mikhail (1977), "Sobre el número máximo de permutaciones con una distancia máxima o mínima dada", Journal of Combinatorial Theory , Serie A, 22 (3): 352–360, doi : 10.1016/0097-3165(77)90009 -7 , SEÑOR  0439648, Zbl  0352.05003
• Frankl, Peter ; Füredi, Zoltán (1986), "Familias no triviales que se cruzan", Journal of Combinatorial Theory , Serie A, 41 (1): 150–153, doi : 10.1016/0097-3165(86)90121-4 , MR  0826944
• Frankl, Peter ; Graham, Ronald L. (1989), "Pruebas antiguas y nuevas del teorema de Erdős-Ko-Rado" (PDF) , edición de ciencias naturales de la Universidad de Sichuan , 26 (número especial): 112-122, MR  1059690
• Frankl, Peter ; Wilson, Richard M. (1986), "El teorema de Erdős-Ko-Rado para espacios vectoriales", Journal of Combinatorial Theory , Serie A, 43 (2): 228–236, doi : 10.1016/0097-3165(86)90063 -4 , SEÑOR  0867648, Zbl  0609.05055
• Friedgut, Ehud (2008), "Sobre la medida de las familias que se cruzan, la singularidad y la estabilidad" (PDF) , Combinatorica , 28 (5): 503–528, doi :10.1007/s00493-008-2318-9, MR  2501247, S2CID  7225916, Zbl  1199.05319, archivado desde el original (PDF) el 25 de enero de 2021
• Füredi, Zoltán (1980), "Sobre familias de conjuntos finitos con intersección máxima", Journal of Combinatorial Theory , Serie A, 28 (3): 282–289, doi : 10.1016/0097-3165(80)90071-0 , MR  0570210
• Füredi, Zoltán (1995), "Hipergrafos extremos y geometría combinatoria" (PDF) , Actas del Congreso Internacional de Matemáticos, vol. 1, 2 (Zúrich, 1994) , Basilea: Birkhäuser, págs. 1343–1352, doi :10.1007/978-3-0348-9078-6_65, MR  1404036, Zbl  0839.05077, archivado desde el original el 2017-08-30 , recuperado el 23 de agosto de 2022{{citation}}: CS1 maint: bot: original URL status unknown (link)
• Godsil, Chris ; Meagher, Karen (2009), "Una nueva prueba del teorema de Erdős-Ko-Rado para la intersección de familias de permutaciones", European Journal of Combinatorics , 30 (2): 404–414, arXiv : 0710.2109 , doi : 10.1016/j. ejc.2008.05.006 , señor  2489272, Zbl  1177.05010
• Godsil, Christopher ; Meagher, Karen (2015), Teoremas de Erdős-Ko-Rado: enfoques algebraicos, Estudios de Cambridge en Matemáticas Avanzadas, Cambridge University Press, ISBN 9781107128446
• Grindstaff, Gillian (2020), "El grupo de isometría del espacio del árbol filogenético es S _n ", Actas de la Sociedad Matemática Estadounidense , 148 (10): 4225–4233, arXiv : 1901.02982 , doi : 10.1090/proc/15154, MR  4135291 , S2CID  57761161
• Harvey, Daniel J.; Wood, David R. (2014), "Ancho de árbol del gráfico de Kneser y el teorema de Erdős-Ko-Rado", Electronic Journal of Combinatorics , 21 (1), artículo 1.48, arXiv : 1310.5400 , doi : 10.37236/3971, MR  3177543 , S2CID  15461040, Zbl  1300.05084
• Haviv, Ishay (2022), "Un algoritmo de parámetros fijos para el problema de Kneser", en Bojanczyk, Mikolaj; Merelli, Emanuela; Woodruff, David P. (eds.), 49.º Coloquio internacional sobre autómatas, lenguajes y programación, ICALP 2022, 4 al 8 de julio de 2022, París, Francia , LIPIcs, vol. 229, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, págs. 72:1–72:18, arXiv : 2204.06761 , doi :10.4230/LIPIcs.ICALP.2022.72, ISBN 9783959772358
• Hilton, AJW ; Milner, EC (1967), "Algunos teoremas de intersección para sistemas de conjuntos finitos", Quarterly Journal of Mathematics , Second Series, 18 : 369–384, doi :10.1093/qmath/18.1.369, MR  0219428
• Katona, GOH (1972), "Una prueba simple del teorema de Erdös-Chao Ko-Rado", Journal of Combinatorial Theory , Serie B, 13 (2): 183–184, doi : 10.1016/0095-8956(72)90054 -8 , SEÑOR  0304181, Zbl  0262.05002
• Larose, Benoit; Malvenuto, Claudia (2004), "Conjuntos estables de tamaño máximo en gráficos tipo Kneser", European Journal of Combinatorics , 25 (5): 657–673, doi : 10.1016/j.ejc.2003.10.006 , MR  2061391
• Liggett, Thomas M. (1977), "Extensiones del teorema de Erdős-Ko-Rado y una aplicación estadística", Journal of Combinatorial Theory , Serie A, 23 (1): 15–21, doi : 10.1016/0097-3165( 77)90075-9 , SEÑOR  0441750
• van Lint, JH ; Wilson, Richard M. (1992), Un curso de combinatoria , Cambridge University Press, Cambridge, págs. 45–46, ISBN 0-521-41057-6, señor  1207813
• Olarte, Jorge Alberto; Santos, Francisco ; Spreer, Jonathan; Stump, Christian (2020), "La propiedad EKR para complejos simpliciales puros de bandera sin límite" (PDF) , Journal of Combinatorial Theory , Serie A, 172 : 105205, 29, doi :10.1016/j.jcta.2019.105205, MR  4052307, S2CID  119158469
• Polcyn, Joanna; Ruciński, Andrzej (2017), "Una jerarquía de sistemas triples que se cruzan máximos", Opuscula Mathematica , 37 (4): 597–608, arXiv : 1608.06114 , doi : 10.7494/OpMath.2017.37.4.597, MR  3647803, S2CID  55674958, Zbl  1402.05209
• Schrijver, Alexander (1981), "Esquemas de asociación y capacidad de Shannon: polinomios de Eberlein y el teorema de Erdős-Ko-Rado", en Lovász, László ; Sós, Vera T. (eds.), Métodos algebraicos en teoría de grafos, vol. I, II: Artículos de la conferencia celebrada en Szeged, del 24 al 31 de agosto de 1978 , Colloquia Mathematica Societatis János Bolyai, vol. 25, Holanda Septentrional, págs. 671–688, SEÑOR  0642067
• Wilson, Richard M. (1984), "El límite exacto en el teorema de Erdős-Ko-Rado", Combinatorica , 4 (2–3): 247–257, doi :10.1007/BF02579226, MR  0771733, S2CID  44504849

enlaces externos

• Cameron, Peter (29 de septiembre de 2017), "EKR, sistemas Steiner, esquemas de asociación y todo eso", Blog de Peter Cameron