Teorema de Erdös-Ko-Rado

En matemáticas, el teorema de Erdős-Ko-Rado limita el número de conjuntos de 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. Forma parte del campo de la combinatoria y es uno de los resultados centrales de la teoría de conjuntos extremos.^[1]

El teorema se aplica a familias de conjuntos que tienen todos el mismo tamaño $r$ , y son todos subconjuntos de algún conjunto mayor de tamaño $n$ . 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. El teorema de Erdős-Ko-Rado establece que cuando $n$ es lo suficientemente grande para que el problema no sea trivial $n\geq 2r$ esta construcción produce las mayores familias de intersección posibles. Cuando $n=2r$ hay otras familias igual de grandes, pero para valores mayores de $n$ sólo las familias así construidas pueden ser más grandes.

El teorema de Erdős-Ko-Rado también puede describirse en términos de hipergrafos o conjuntos independientes en grafos 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. 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.

Afirmación

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

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

El requisito de que $n\geq 2r$ es necesario para que el problema no sea trivial: cuando $n<2r$ , cuando todos los conjuntos de elementos $r$ se intersecan, y la mayor familia de intersección está formada por todos los conjuntos de elementos $r$ , con un tamaño de ${\tbinom {n}{r}}$ .^[2]

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 «hiperpuertas») son del mismo tamaño $r$ , se llama hipergrafo $r$ uniforme. Así pues, el teorema proporciona un límite superior para el número de hiperpuertas que se solapan por pares en un hipergrafo $r$ uniforme con $n$ vértices y $n\geq 2r$ .^[3]

El gráfico de Kneser

KG_{5,2}

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

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

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

Se trata de un grafo con un vértice por cada subconjunto de $r$ elementos de un conjunto de $n$ elementos y una arista entre cada par de conjuntos disjuntos. 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.^[4] Dado que los grafos de Kneser tienen simetrías que llevan cualquier vértice a cualquier otro vértice (son grafos de vértice-transitivo), su número cromático fraccionario es igual al cociente entre su número de vértices y su número de independencia, por lo que otra forma de expresar el teorema de Erdős-Ko-Rado es que estos grafos tienen número cromático fraccionario exacto $n/r$ .^[5]

Historia

Paul Erdős, Chao Ko y Richard Rado demostraron este teorema en 1938 tras 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, escapando ambos de la influencia de la Alemania nazi; Ko era 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 por la teoría combinatoria de conjuntos en la década de 1930 y al aumento del interés por el tema en la década de 1960.^[6] El artículo de 1961 presentaba el resultado de una forma aparentemente más general, en la que sólo se exigía que los subconjuntos tuvieran un tamaño máximo de $r$ , y cumplir el requisito adicional de que ningún subconjunto esté contenido en otro.^[7] Una familia de subconjuntos que cumpla estas condiciones puede ampliarse a subconjuntos de tamaño exactamente $r$ bien por una aplicación del teorema de Hall,^[8] bien eligiendo cada subconjunto ampliado de la misma cadena en una descomposición en cadena simétrica de conjuntos.^[9]

Familias máximas y maximales

Familias de tamaño máximo

El gráfico Johnson

J(4,2)

con un vértice para cada subconjunto de dos elementos de {1,2,3,4} y una arista que conecta los pares de subconjuntos que se intersecan, dispuestos geométricamente como un octaedro con conjuntos disjuntos en vértices opuestos. Las familias de intersección más grandes para

r=2

y

n=2r=4

proceden de las caras triangulares de este octaedro. Sustituir 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.

Una forma sencilla de construir una familia de intersección de conjuntos de $r$ elementos cuyo tamaño coincide exactamente con el límite de Erdős-Ko-Rado es elegir cualquier elemento fijo $x$ y dejar ${\mathcal {A}}$ que consista de todos los subconjuntos de $r$ elementos que incluyen $x$ . Por ejemplo, para subconjuntos de 2 elementos del conjunto de 4 elementos $\{1,2,3,4\}$ , con $x=1$ esto da como resultado la familia:

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

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

Cuando $n>2r$ es la única familia de intersección de este tamaño. Sin embargo, cuando $n=2r$ , existe una construcción más general. Cada conjunto de $r$ elementos puede emparejarse con su complemento, el único conjunto de $r$ elementos de las que es disjunta. A continuación, elija un conjunto de cada uno de estos pares complementarios. Por ejemplo, para los mismos parámetros anteriores, esta construcción más general puede utilizarse para formar la familia:

$\{3,4\}$ , $\{2,4\}$ , y $\{2,3\}$ ,

donde cada dos conjuntos se intersecan a pesar de que ningún elemento pertenezca 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 sólo algunos de los conjuntos.^[2]

Cuando familiar $n>2r,$ del primero tipo (conocidas como estrellas,^[1] dictaduras,^[10] juntas^[10], familias centradas^[11] o familias principales^[12]) son las familias máximas únicas. En este caso, una familia de tamaño casi máximo tiene un elemento que es común a casi todos sus conjuntos.^[10] Esta propiedad se ha denominado estabilidad,^[12] aunque el mismo término también se ha utilizado para una propiedad diferente, el hecho de que (para un amplio rango de parámetros) eliminar aristas elegidas al azar del grafo de Kneser no aumenta el tamaño de sus conjuntos independientes.^[13]

Familias de intersección máxima

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

Una familia en intersección de conjuntos de $r$ elementos puede ser máximo, en el sentido de que no se puede añadir ningún conjunto más (ni siquiera ampliando el conjunto base) sin destruir la propiedad de intersección, pero no de tamaño máximo. Un ejemplo con $n=7$ y $r=3$ es el conjunto de siete líneas del plano de Fano, mucho menos que el límite de Erdős-Ko-Rado de 15.^[14] En términos más generales, las rectas de cualquier plano proyectivo finito de orden $q$ forman una familia de intersección máxima que incluye sólo a conjuntos $n$ , para el parámetro $r=q+1$ y $=q^{2}+q+1$ . El plano de Fano es el caso $q=2$ de esta construcción.^[15]

El menor tamaño posible de una familia de intersección máxima de conjuntos de $r$ elementos, en términos de $r$ , se desconoce, pero al menos $3r$ para $r\geq 4$ .^[16] Los planos proyectivos producen familias de intersección máxima cuyo número de conjuntos es $r^{2}-r+1$ , pero para infinitas opciones de $r$ existen familias de intersección maximal más pequeñas de tamaño ${\tfrac {3}{4}}r^{2}$ .^[15]

Las mayores familias intersecantes de conjuntos de $r$ elementos que son maximales pero no máximos tienen tamaño:

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

Están formados a partir de un elemento $x$ y un conjunto de $r$ elementos, $Y$ que no contiene $x$ , al agregar $Y$ a la familia de conjunto de $r$ elementos que incluye ambos $x$ y por lo menos un elemento de $Y$ . Este resultado se denomina teorema de Hilton-Milner, en honor a su demostración por Anthony Hilton y Eric Charles Milner en 1967.^[17]

Evidencias

La demostración original del teorema de Erdős-Ko-Rado utilizaba la inducción en $n$ . El caso base para $n=2r$ se deduce fácilmente del hecho de que una familia de intersección no puede incluir tanto un conjunto como su complemento, y que en este caso el límite del teorema de Erdős-Ko-Rado es exactamente la mitad del número de todos los conjuntos de $r$ elementos. El paso de inducción para un $n$ más grande utiliza un método llamado desplazamiento, de sustitución de elementos en familias que se intersecan para hacer la familia más pequeña en orden lexicográfico y reducirla a una forma canónica más fácil de analizar. ^[7]

En 1972, Gyula O. H. Katona dio la siguiente prueba breve utilizando la doble contabilidad.^[18]

Dejemos que $A$ sea cualquier familia intersecante de subconjuntos de $r$ elementos de un conjunto de $n$ elementos. Ordenar todos los $n$ elementos en cualquier orden cíclico, y considerar los conjuntos de $A$ que forman intervalos de longitud $r$ dentro de este orden cíclico elegido. Por ejemplo, si $n=8$ y $r=3$ , un posible orden cíclico para los números $\{1,2,...,8\}$ es el orden $(3,1,5,4,2,7,6,8)$ , que tiene ocho intervalos de 3 elementos (incluidos los que envuelven): $(3,1,5)$ , $(1,5,4)$ , $(5,4,2)$ , $(4,2,7)$ , $(2,7,6)$ , $(7,6,8)$ , $(6,8,3)$ , y $(8,3,1)$ .
Sin embargo, sólo algunos de estos intervalos pueden pertenecer a ${\mathcal {A}}$ , porque no todas se cruzan. La observación clave de Katona es que a lo sumo intervalos $r$ de un mismo orden cíclico pueden pertenecer a ${\mathcal {A}}$ . Esto es porque, si $(a_{1},a_{2},\dots ,a_{r})$ es uno de estos intervalos, entonces cualquier otro intervalo del mismo orden cíclico que pertenezca a ${\mathcal {A}}$ separa $a_{i}$ from $a_{i+1}$ , para algunos $i$ , por contener precisamente uno de estos dos elementos. Los dos intervalos que separan estos elementos son disjuntos, por lo que a lo sumo uno de ellos puede pertenecer a ${\mathcal {A}}$ . Así, el número de intervalos en ${\mathcal {A}}$ es como máximo uno más el número $r-1$ de pares que pueden separarse.^[18]
Basándose en esta idea, es posible contar los pares $(S,C)$ , donde $S$ es un conjunto en ${\mathcal {A}}$ y $C$ es un orden cíclico para el que $S$ es un intervalo, en dos vías. En primer lugar, para cada conjunto $S$ puede generar $C$ al elegir uno de $r!$ permutaciones de $S$ y $(n-r)!$ permutaciones de los elementos restantes, demostrando que el número de pares es is $|{\mathcal {A}}|r!(n-r)!$ . Y segundo, hay $(n-1)!$ órdenes cíclicos, cada uno de los cuales tiene como máximo $r$ intervalos de ${\mathcal {A}}$ , por lo que el número de pares es de a lo mucho $r(n-1)!$ . Comparando estos dos recuentos se obtiene la desigualdad
$|{\mathcal {A}}|r!(n-r)!\leq r(n-1)!$ y dividiendo ambos lados por $r!(n-r)!$ da el resultado:^[18] $|{\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.^[5] Se conocen muchas otras pruebas.^[19]

Resultados relacionados

Generalizaciones

Una generalización del teorema se aplica a subconjuntos que deben tener intersecciones grandes. Esta versión del teorema tiene tres parámetros: $n$ , el número de elementos de los que se extraen los subconjuntos $r$ , del tamaño de los subconjuntos, como antes, y $t$ , el tamaño mínimo de la intersección de dos subconjuntos cualesquiera. Para la forma original del teorema de Erdős-Ko-Rado, $t=1$ . En general, para $n$ 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 $t$ es como máximo^[7] ${\binom {n-t}{r-t}}.$

Más concretamente, este límite se cumple cuando $n\geq (t+1)(r-t+1)$ , y no se mantiene para valores más pequeños de $n$ . Cuando $n>(t+1)(r-t+1)$ , las únicas familias 𝑡-intersecantes de este tamaño se obtienen designando 𝑡 elementos como la intersección común de todos los subconjuntos, y construyendo la familia de todos los subconjuntos de 𝑡 elementos que incluyen estos 𝑡 elementos designados.^[20] El tamaño máximo de una familia de intersección $t$ cuando $n<(t+1)(r-t+1)$ fue determinada por Ahlswede y Khachatrian^[21], en su teorema Ahlswede-Khachatrian.

La correspondiente formulación grafo-teórica de esta generalización implica grafos de Johnson en lugar de grafos de Kneser.^[5] Para valores suficientemente grandes de $n$ y en particular para $n>{\tfrac {1}{2}}r^{2}$ , tanto el teorema de Erdős-Ko-Rado como su generalización pueden reforzarse desde el número de independencia a la capacidad de Shannon de un grafo: el grafo de Johnson correspondiente a los subconjuntos 𝑡-intersecantes de elementos 𝑟 tiene capacidad de Shannon ${\tbinom {n-t}{r-t}}$ .^[22]

El teorema también se puede generalizar a familias en las que cada $h$ subconjuntos tienen una intersección común. Como esto refuerza la condición de que cada par se intersecte (para lo cual $h=2$ ), estas familias tienen el mismo límite en su tamaño máximo, ${\tbinom {n-1}{r-1}}$ cuando $n$ es suficientemente grande. Sin embargo, en este caso el significado de «suficientemente grande» puede relajarse de $n\geq 2r$ to $n\geq {\tfrac {h}{h-1}}r$ .^[23]

Análogos

Se conocen muchos resultados análogos al teorema de Erdős-Ko-Rado, pero para otras clases de objetos distintas de los conjuntos finitos. Generalmente implican la afirmación de que las mayores familias 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. Algunos ejemplos son los siguientes:

Existe un análogo q del teorema de Erdős-Ko-Rado para familias intersecantes de subespacios lineales sobre campos finitos. Si ${\mathcal {S}}$ es una familia de intersección de subespacios 𝑟-dimensionales de un espacio vectorial 𝑛-dimensional sobre un campo finito de orden $q$ y $n\geq 2r$ entonces:

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

donde el subíndice q marca la notación para el coeficiente binomial gaussiano, el número de subespacios de una dimensión dada dentro de un espacio vectorial de una dimensión mayor sobre un campo finito de orden q. En este caso, se puede obtener una familia de subespacios de intersección mayor eligiendo cualquier vector distinto de cero y construyendo la familia de subespacios de la dimensión dada que contienen todos el vector elegido.^[24]

Dos permutaciones sobre el mismo conjunto de elementos se definen como intersecantes si existe algún elemento que tiene la misma imagen bajo ambas permutaciones. En un conjunto de 𝑛 elementos, existe una familia obvia de $(n-1)!$ permutaciones intersecantes, las permutaciones que fijan uno de los elementos (el subgrupo estabilizador de este elemento). El teorema análogo es que ninguna familia intersecante de permutaciones puede ser mayor, y que las únicas familias intersecantes de tamaño $(n-1)!$ son los cosets de estabilizadores de un elemento.^[25] Pueden describirse más directamente como las familias de permutaciones que asignan un elemento fijo a otro elemento fijo. En términos más generales, 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 de $(n-t)!$ , y las únicas familias de este tamaño son cosets de estabilizadores puntuales. Alternativamente, en términos de teoría de grafos, las permutaciones de $n$ elementos corresponden a los emparejamientos perfectos de un grafo bipartito completo $K_{n,n}$ 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.^[5] Otro análogo del teorema, para particiones de un conjunto, incluye como caso especial los emparejamientos perfectos de un grafo completo $K_{n}$ (con $n$ par). Hay $(n-1)!!$ emparejamientos, donde $!!$ denota el doble factorial. La mayor familia de emparejamientos que se cruzan por pares (es decir, que tienen una arista en común) tiene el tamaño $(n-3)!!$ y se obtiene fijando una arista y eligiendo todas las formas de emparejar los $n-2$ vértices restantes.^[5]

Una geometría parcial es un sistema de un número finito de puntos y rectas abstractos que satisface ciertos axiomas, incluido el requisito de que todas las rectas contengan el mismo número de puntos y todos los puntos pertenezcan al mismo número de rectas. 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.^[5]

Un conjunto con signo consiste en un conjunto junto con una función de signo que asigna cada elemento a $\{1,-1\}$ . Se puede decir que los conjuntos con signo se intersecan cuando tienen un elemento común que tiene el mismo signo en cada uno de ellos. Entonces, una familia de intersección de conjuntos con signo de 𝑟-elementos, extraída de un universo de 𝑛-elementos, consta de como máximo $2^{r-1}{\binom {n-1}{r-1}}$ conjuntos con signo. Este número de conjuntos con signo puede obtenerse fijando un elemento y su signo y dejando que los restantes elementos $r-1$ y los signos varían.^[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. 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 están formadas por ${\textstyle q^{n-1}}$ 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 $t+2i$ y símbolos para esas posiciones, para un número $i$ que depende en $n$ , $q$ , y $t$ , y construyendo la familia de cadenas que tienen cada una al menos $t+i$ de los símbolos escogidos. 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. El número de todas las triangulaciones es un número Catalán $C_{n-2}$ , y la conjetura afirma que una familia de triangulaciones cada par de las cuales comparte una arista tiene tamaño máximo $C_{n-3}$ . Una familia de intersección de tamaño exacto $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 resto del polígono de vértices restantes $(n-1)$ .^[28]

Aplicaciones

El teorema de Erdős-Ko-Rado puede utilizarse para demostrar el siguiente resultado en teoría de la probabilidad. Dejemos que $x_{i}$ sea independiente variables aleatorias 0-1 con probabilidad $p\geq {\tfrac {1}{2}}$ de ser una, y dejemos $c({\vec {x}})$ sea cualquier combinación convexa fija de estas variables. Entonces $\Pr \left[c({\vec {x}})\geq {\tfrac {1}{2}}\right]\geq p.$

La prueba consiste en observar que los subconjuntos de variables cuyos vectores indicadores tienen grandes combinaciones convexas deben ser no disjuntos y utilizar el teorema de Erdős-Ko-Rado para acotar el número de estos subconjuntos.^[29]

Las propiedades de estabilidad del teorema de Erdős-Ko-Rado desempeñan un papel clave en un algoritmo eficiente para encontrar aristas monocromáticas en coloraciones impropias de grafos de Kneser.^[30] El teorema de Erdős-Ko-Rado también se ha utilizado para caracterizar las simetrías del espacio de árboles filogenéticos.^[31]

Referencias

↑ ^a ^b Das, Shagnik; Tran, Tuan (2016). «"Removal and stability for Erdős–Ko–Rado». SIAM Journal on Discrete Mathematics. doi:10.1137/15M105149X.
↑ ^a ^b ^c Aigner, Martin; Ziegler, Günter M. (2018). «"Chapter 30: Three famous theorems on finite sets",». Proofs from THE BOOK (6th ed.), Springer. ISBN 978-3-662-57265-8. doi:10.1007/978-3-662-57265-8_15.
↑ Füredi, Zoltán (1995). «"Extremal hypergraphs and combinatorial geometry"». Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Zürich, 1994), Basel: Birkhäuser,. doi:10.1007/978-3-0348-9078-6_65.
↑ Harvey, Daniel J.; Wood, David R. (2014). «"Treewidth of the Kneser graph and the Erdős–Ko–Rado theorem"». Electronic Journal of Combinatorics. doi:10.37236/3971.
↑ ^a ^b ^c ^d ^e ^f Godsil, Christopher; Meagher, Karen (2015). «Erdős–Ko–Rado Theorems: Algebraic Approaches». Cambridge Studies in Advanced Mathematics, Cambridge University Press. ISBN 9781107128446.
↑ ^a ^b Anderson, Ian (2013). «Combinatorial set theory». Combinatorics: Ancient and Modern, Oxford University Press: 309-328. ISBN 978-0-19-965659-2. doi:10.1093/acprof:oso/9780199656592.003.0014.
↑ ^a ^b ^c ^d Erdős, P.; Ko, Chao; Rado, R. (1961). «"Intersection theorems for systems of finite sets"». Quarterly Journal of Mathematics, Second Series. doi:10.1093/qmath/12.1.313.
↑ van Lint, J. H.; Wilson, Richard M. (1992). «A Course in Combinatorics». Cambridge University Press, Cambridge. ISBN 0-521-41057-6.
↑ Anderson, Ian (1987). «"Chapter 5: Intersecting systems and the Erdős–Ko–Rado theorem", Combinatorics of Finite Sets». Oxford Science Publications, Oxford University Press. ISBN 0-19-853367-5.
↑ ^a ^b ^c Dinur, Irit; Friedgut, Ehud (2009). «"Intersecting families are essentially contained in juntas"». Combinatorics, Probability and Computing. doi:10.1017/S0963548308009309.
↑ Borg, Peter (2012). «"Cross-intersecting sub-families of hereditary families"». Journal of Combinatorial Theory. doi:10.1016/j.jcta.2011.12.002.
↑ ^a ^b Friedgut, Ehud (2008). «On the measure of intersecting families, uniqueness and stability». Combinatorica. doi:10.1007/s00493-008-2318-9.
↑ Bollobás, Béla; Narayanan, Bhargav P.; Raigorodskii, Andrei M. (2016). «"On the stability of the Erdős-Ko-Rado theorem"». Journal of Combinatorial Theory, Series A,. doi:10.1016/j.jcta.2015.08.002.
↑ Polcyn, Joanna; Ruciński, Andrzej (2017). «A hierarchy of maximal intersecting triple systems». Opuscula Mathematica. doi:10.7494/OpMath.2017.37.4.597.
↑ ^a ^b Füredi, Zoltán (1980). «On maximal intersecting families of finite sets». Journal of Combinatorial Theory, Series A. doi:10.1016/0097-3165(80)90071-0.
↑ Dow, Stephen J.; Drake, David A.; Füredi, Zoltán; Larson, Jean A. (1985). «"A lower bound for the cardinality of a maximal family of mutually intersecting sets of equal size",». Proceedings of the sixteenth Southeastern international conference on combinatorics, graph theory and computing (Boca Raton, Fla., 1985), Congressus Numerantium,.
↑ Hilton, A. J. W.; Milner, E. C. (1967). «"Some intersection theorems for systems of finite sets",». Quarterly Journal of Mathematics, Second Series. doi:10.1093/qmath/18.1.369.
↑ ^a ^b ^c Katona, G. O. H. (1972). «"A simple proof of the Erdös–Chao Ko–Rado theorem"». Journal of Combinatorial Theory, Series B. doi:10.1016/0095-8956(72)90054-8.
↑ Frankl, Péter; Graham, Ronald L. (1989). «"Old and new proofs of the Erdős–Ko–Rado theorem"». Journal of Sichuan University Natural Science Edition, 26 (Special Issue).
↑ Wilson, Richard M. (1984). «"The exact bound in the Erdős–Ko–Rado theorem"». Combinatorica. doi:10.1007/BF02579226.
↑ Ahlswede, Rudolf; Khachatrian, Levon H. (1997). «"The complete intersection theorem for systems of finite sets"». European Journal of Combinatorics. doi:10.1006/eujc.1995.0092.
↑ Schrijver, Alexander (1981). «"Association schemes and the Shannon capacity: Eberlein polynomials and the Erdős–Ko–Rado theorem"». Algebraic Methods in Graph Theory, Vol. I, II: Papers from the Conference held in Szeged, August 24–31, 1978, Colloquia Mathematica Societatis János Bolyai, vol. 25, North-Holland.
↑ Frankl, Péter (1976). «On Sperner families satisfying an additional condition"». Journal of Combinatorial Theory, Series A. doi:10.1016/0097-3165(76)90073-x.
↑ Frankl, Péter; Wilson, Richard M. (1986). «The Erdős–Ko–Rado theorem for vector spaces». Journal of Combinatorial Theory, Series A. doi:10.1016/0097-3165(86)90063-.
↑ Frankl, Péter; Deza, Mikhail (1977). «"On the maximum number of permutations with given maximal or minimal distance"». Journal of Combinatorial Theory, Series A,. doi:10.1016/0097-3165(77)90009-7.
↑ Bollobás, Béla; Leader, Imre (1997). «"An Erdős–Ko–Rado theorem for signed sets"». Computers and Mathematics with Applications. doi:10.1016/S0898-1221(97)00215-0.
↑ Ahlswede, Rudolf; Khachatrian, Levon H. (1998). «"The diametric theorem in Hamming spaces—optimal anticodes"». Advances in Applied Mathematics,. doi:10.1006/aama.1998.0588.
↑ Olarte, Jorge Alberto; Santos, Francisco; Spreer, Jonathan; Stump, Christian (2020). «"The EKR property for flag pure simplicial complexes without boundary"». Journal of Combinatorial Theory, Series A. doi:10.1016/j.jcta.2019.105205.
↑ Liggett, Thomas M. (1977). «"Extensions of the Erdős–Ko–Rado theorem and a statistical application"». Journal of Combinatorial Theory, Series A. doi:10.1016/0097-3165(77)90075-9.
↑ Haviv, Ishay (2022). «"A fixed-parameter algorithm for the Kneser problem"». 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4–8, 2022, Paris, France, LIPIcs, vol. 229, Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ISBN 9783959772358. doi:10.4230/LIPIcs.ICALP.2022.72.
↑ Grindstaff, Gillian (2020). «The isometry group of phylogenetic tree space is Sn». Proceedings of the American Mathematical Society. doi:10.1090/proc/15154.

Enlaces externos

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

Datos: Q718875

[:0-1] Das, Shagnik; Tran, Tuan (2016). «"Removal and stability for Erdős–Ko–Rado». SIAM Journal on Discrete Mathematics. doi:10.1137/15M105149X.

[:1-2] Aigner, Martin; Ziegler, Günter M. (2018). «"Chapter 30: Three famous theorems on finite sets",». Proofs from THE BOOK (6th ed.), Springer. ISBN 978-3-662-57265-8. doi:10.1007/978-3-662-57265-8_15.

[3] Füredi, Zoltán (1995). «"Extremal hypergraphs and combinatorial geometry"». Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Zürich, 1994), Basel: Birkhäuser,. doi:10.1007/978-3-0348-9078-6_65.

[4] Harvey, Daniel J.; Wood, David R. (2014). «"Treewidth of the Kneser graph and the Erdős–Ko–Rado theorem"». Electronic Journal of Combinatorics. doi:10.37236/3971.

[:7-5] ↑ ^a ^b ^c ^d ^e ^f Godsil, Christopher; Meagher, Karen (2015). «Erdős–Ko–Rado Theorems: Algebraic Approaches». Cambridge Studies in Advanced Mathematics, Cambridge University Press. ISBN 9781107128446.

[:2-6] Anderson, Ian (2013). «Combinatorial set theory». Combinatorics: Ancient and Modern, Oxford University Press: 309-328. ISBN 978-0-19-965659-2. doi:10.1093/acprof:oso/9780199656592.003.0014.

[:3-7] Erdős, P.; Ko, Chao; Rado, R. (1961). «"Intersection theorems for systems of finite sets"». Quarterly Journal of Mathematics, Second Series. doi:10.1093/qmath/12.1.313.

[8] van Lint, J. H.; Wilson, Richard M. (1992). «A Course in Combinatorics». Cambridge University Press, Cambridge. ISBN 0-521-41057-6.

[9] Anderson, Ian (1987). «"Chapter 5: Intersecting systems and the Erdős–Ko–Rado theorem", Combinatorics of Finite Sets». Oxford Science Publications, Oxford University Press. ISBN 0-19-853367-5.

[:4-10] Dinur, Irit; Friedgut, Ehud (2009). «"Intersecting families are essentially contained in juntas"». Combinatorics, Probability and Computing. doi:10.1017/S0963548308009309.

[11] Borg, Peter (2012). «"Cross-intersecting sub-families of hereditary families"». Journal of Combinatorial Theory. doi:10.1016/j.jcta.2011.12.002.

[:5-12] Friedgut, Ehud (2008). «On the measure of intersecting families, uniqueness and stability». Combinatorica. doi:10.1007/s00493-008-2318-9.

[13] Bollobás, Béla; Narayanan, Bhargav P.; Raigorodskii, Andrei M. (2016). «"On the stability of the Erdős-Ko-Rado theorem"». Journal of Combinatorial Theory, Series A,. doi:10.1016/j.jcta.2015.08.002.

[14] Polcyn, Joanna; Ruciński, Andrzej (2017). «A hierarchy of maximal intersecting triple systems». Opuscula Mathematica. doi:10.7494/OpMath.2017.37.4.597.

[:6-15] Füredi, Zoltán (1980). «On maximal intersecting families of finite sets». Journal of Combinatorial Theory, Series A. doi:10.1016/0097-3165(80)90071-0.

[16] Dow, Stephen J.; Drake, David A.; Füredi, Zoltán; Larson, Jean A. (1985). «"A lower bound for the cardinality of a maximal family of mutually intersecting sets of equal size",». Proceedings of the sixteenth Southeastern international conference on combinatorics, graph theory and computing (Boca Raton, Fla., 1985), Congressus Numerantium,.

[17] Hilton, A. J. W.; Milner, E. C. (1967). «"Some intersection theorems for systems of finite sets",». Quarterly Journal of Mathematics, Second Series. doi:10.1093/qmath/18.1.369.

[:8-18] Katona, G. O. H. (1972). «"A simple proof of the Erdös–Chao Ko–Rado theorem"». Journal of Combinatorial Theory, Series B. doi:10.1016/0095-8956(72)90054-8.

[19] Frankl, Péter; Graham, Ronald L. (1989). «"Old and new proofs of the Erdős–Ko–Rado theorem"». Journal of Sichuan University Natural Science Edition, 26 (Special Issue).

[20] Wilson, Richard M. (1984). «"The exact bound in the Erdős–Ko–Rado theorem"». Combinatorica. doi:10.1007/BF02579226.

[21] Ahlswede, Rudolf; Khachatrian, Levon H. (1997). «"The complete intersection theorem for systems of finite sets"». European Journal of Combinatorics. doi:10.1006/eujc.1995.0092.

[22] Schrijver, Alexander (1981). «"Association schemes and the Shannon capacity: Eberlein polynomials and the Erdős–Ko–Rado theorem"». Algebraic Methods in Graph Theory, Vol. I, II: Papers from the Conference held in Szeged, August 24–31, 1978, Colloquia Mathematica Societatis János Bolyai, vol. 25, North-Holland.

[23] Frankl, Péter (1976). «On Sperner families satisfying an additional condition"». Journal of Combinatorial Theory, Series A. doi:10.1016/0097-3165(76)90073-x.

[24] Frankl, Péter; Wilson, Richard M. (1986). «The Erdős–Ko–Rado theorem for vector spaces». Journal of Combinatorial Theory, Series A. doi:10.1016/0097-3165(86)90063-.

[25] Frankl, Péter; Deza, Mikhail (1977). «"On the maximum number of permutations with given maximal or minimal distance"». Journal of Combinatorial Theory, Series A,. doi:10.1016/0097-3165(77)90009-7.

[26] Bollobás, Béla; Leader, Imre (1997). «"An Erdős–Ko–Rado theorem for signed sets"». Computers and Mathematics with Applications. doi:10.1016/S0898-1221(97)00215-0.

[27] Ahlswede, Rudolf; Khachatrian, Levon H. (1998). «"The diametric theorem in Hamming spaces—optimal anticodes"». Advances in Applied Mathematics,. doi:10.1006/aama.1998.0588.

[28] Olarte, Jorge Alberto; Santos, Francisco; Spreer, Jonathan; Stump, Christian (2020). «"The EKR property for flag pure simplicial complexes without boundary"». Journal of Combinatorial Theory, Series A. doi:10.1016/j.jcta.2019.105205.

[29] Liggett, Thomas M. (1977). «"Extensions of the Erdős–Ko–Rado theorem and a statistical application"». Journal of Combinatorial Theory, Series A. doi:10.1016/0097-3165(77)90075-9.

[30] Haviv, Ishay (2022). «"A fixed-parameter algorithm for the Kneser problem"». 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4–8, 2022, Paris, France, LIPIcs, vol. 229, Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ISBN 9783959772358. doi:10.4230/LIPIcs.ICALP.2022.72.

[31] Grindstaff, Gillian (2020). «The isometry group of phylogenetic tree space is Sn». Proceedings of the American Mathematical Society. doi:10.1090/proc/15154.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]