En combinatoria , el teorema de Erdős-Ko-Rado de Paul Erdős , Chao Ko y Richard Rado es un teorema sobre la intersección de familias de conjuntos .
El teorema es el siguiente. Suponga que A es una familia de subconjuntos distintos detal que cada subconjunto es de tamaño r y cada par de subconjuntos tiene una intersección no vacía , y supongamos que n ≥ 2 r . Entonces el número de conjuntos en A es menor o igual que el coeficiente binomial
El resultado es parte de la teoría de los hipergráficos . Una familia de conjuntos también puede denominarse hipergrafia, y cuando todos los conjuntos (que se denominan "hipergrafos" en este contexto) tienen el mismo tamaño r , se denomina hipergrafia r -uniforme. Por lo tanto, el teorema da un límite superior para el número de hipergrabados no disjuntos por pares en un hipergrama r -uniforme con n vértices yn ≥ 2 r .
El teorema también se puede formular en términos de teoría de grafos : el número de independencia del grafo de Kneser KG n , r para n ≥ 2 r es
Según Erdős (1987), el teorema se demostró en 1938, pero no se publicó hasta 1961 en una forma aparentemente más general. Los subconjuntos en cuestión solo debían tener el tamaño r como máximo , y con el requisito adicional de que ningún subconjunto estuviera contenido en ningún otro.
Una versión del teorema también es válida para conjuntos firmados ( Bollobás & Leader 1997 )
Prueba
La prueba original de 1961 usó inducción en n . En 1972, Gyula OH Katona dio la siguiente prueba corta usando doble conteo .
Supongamos que tenemos un poco de tales familia de subconjuntos A . Organice los elementos de {1, 2, ..., n } en cualquier orden cíclico y considere los conjuntos de A que forman intervalos de longitud r dentro de este orden cíclico. Por ejemplo, si n = 8 y r = 3, podríamos ordenar los números {1, 2, ..., 8} en el orden cíclico (3,1,5,4,2,7,6,8), que tiene ocho intervalos:
- (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, no es posible que todos los intervalos del orden cíclico pertenezcan a A , porque algunos pares de ellos son disjuntos. Observación clave de Katona es que como máximo r de los intervalos para una sola orden cíclico puede pertenecer a A . Para ver esto, tenga en cuenta que si ( a 1 , a 2 , ..., a r ) es uno de estos intervalos en A , entonces cualquier otro intervalo del mismo orden cíclico que pertenece a A separa a i y a i +1 para algunos i (es decir, contiene 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 una . Por tanto, el número de intervalos en A es uno más el número de pares separados, que es como máximo ( r - 1).
Con base en esta idea, podemos contar el número de pares ( S , C ), donde S es un conjunto en A y C es un orden cíclico para el cual S es un intervalo, de dos maneras. Primero, para cada conjunto S, se puede generar C eligiendo uno de r ! permutaciones de S y ( n - r )! permutaciones de los elementos restantes, mostrando que el número de pares es | A | r ! ( n - r ) !. Y segundo, ¡hay ( n - 1)! órdenes cíclicos, cada uno de los cuales tiene como máximo r intervalos de A , por lo que el número de pares es como máximo r ( n - 1). La combinación de estos dos recuentos da la desigualdad
y dividiendo ambos lados por r ! ( n - r )! da el resultado
Familias de tamaño máximo
Hay dos construcciones diferentes y sencillas para una familia de intersección de conjuntos de elementos r que logran el límite de cardinalidad de Erdős-Ko-Rado. Primero, elija cualquier elemento fijo x , y deje que A consista en todos los subconjuntos r deque incluyen x . Por ejemplo, si n = 4, r = 2 y x = 1, esto produce la familia de tres conjuntos de 2
- {1,2}, {1,3}, {1,4}.
Dos conjuntos cualesquiera de esta familia se cruzan, porque ambos incluyen x . En segundo lugar, cuando n = 2 r y con x como arriba, sea A consistente en todos los subconjuntos r deque no incluyen x . Para los mismos parámetros que arriba, esto produce la familia
- {2,3}, {2,4}, {3,4}.
Dos conjuntos cualesquiera de esta familia tienen un total de 2 r = n elementos entre ellos, elegidos entre los n - 1 elementos que son desiguales ax , por lo que según el principio de casillero deben tener un elemento en común.
Cuando n > 2 r , las familias del primer tipo (conocidas como girasoles, estrellas, dictaduras, familias centradas, familias principales) son las familias máximas únicas. Friedgut (2008) demostró que en este caso, una familia casi de tamaño máximo tiene un elemento común a casi todos sus conjuntos. Esta propiedad se conoce como estabilidad .
Familias máximas que se cruzan
Una familia de intersección de conjuntos de elementos r puede ser máxima, ya que no se pueden agregar más conjuntos 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 7 líneas del plano de Fano , mucho menos que el límite de Erdős – Ko – Rado de 15.
Intersección de familias de subespacios
Existe un análogo q del teorema de Erdős-Ko-Rado para la intersección de familias de subespacios sobre campos finitos . Frankl y Wilson (1986)
Si es una familia de intersección de -subespacios dimensionales de un -espacio vectorial dimensional sobre un campo finito de orden, y , luego
Relación con gráficos en esquemas de asociación
El teorema de Erdős-Ko-Rado da un límite al tamaño máximo de un conjunto independiente en los gráficos de Kneser contenidos en los esquemas de Johnson . [ cita requerida ]
De manera similar, el análogo del teorema de Erdős-Ko-Rado para la intersección de familias de subespacios sobre campos finitos da un límite en el tamaño máximo de un conjunto independiente en los gráficos q-Kneser contenidos en los esquemas de Grassmann . [ cita requerida ]
Referencias
- Bollobás, B .; Líder, I. (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
- Erdős, P. (1987), "Mi trabajo conjunto con Richard Rado", en Whitehead, C. (ed.), Surveys in combinatorics, 1987: Artículos invitados para la undécima conferencia combinatoria británica (PDF) , London Mathematical Society Lecture Note Serie, 123 , Cambridge University Press, págs. 53–80, ISBN 978-0-521-34805-8.
- Erdős, P .; Ko, C .; 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.
- Frankl, P .; Wilson, RM (1986), "El teorema de Erdős-Ko-Rado para espacios vectoriales", Journal of Combinatorial Theory, Serie A , 43 : 228-236, doi : 10.1016 / 0097-3165 (86) 90063-4.
- 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
- Katona, GOH (1972), "Una demostración 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.
- Godsil, Christopher ; Karen, Meagher (2015), Teoremas de Erdős – Ko – Rado: enfoques algebraicos , Cambridge Studies in Advanced Mathematics, Cambridge University Press, ISBN 9781107128446.