Teorema de Erdös-Ko-Rado

Dos famílies intersecantes de subconjunts de dos elements d'un conjunt de quatre elements. Tots els subconjunts de la família esquerra contenen l'element inferior esquerre, mentres que els subconjunts de la família dreta eviten este element

En matemàtiques, la teorema de Erdős-Ko-Rado llimita el número de subconjunts que formen part d'una família de subconjunts d'un conjunt dau, quan cada dos d'estos subconjunts tenen a lo manco un element en comú. Paul Erdős, Chao Ko i Richard Rado varen demostrar la teorema en 1938, pero no ho varen publicar fins a 1961. Forma part del camp de la combinatòria i és un dels resultats centrals de la teoria de conjunts extrems.

La teorema s'aplica a famílies de subconjunts que tenen tots el mateix tamany $r$, i són tots subconjunts d'algun conjunt major de tamany $n$. Una forma de construir una família de conjunts en estos paràmetros, de manera que cada dos d'ells compartixquen un element, és elegir un únic element que pertanyga a tots els subconjunts i, a continuació, formar tots els subconjunts que continguen l'element elegit. La teorema de Erdős-Ko-Rado establix que quan $n$ és lo suficientment gran per a que el problema no siga trivial (és dir, per a $n\ge 2r$) esta construcció produïx les majors famílies d'intersecció possibles. Quan $n=2r$ hi ha atres famílies igual de grans, pero per a valors majors de $n$ només les famílies aixina construïdes poden ser més grans.

La teorema de Erdős-Ko-Rado també pot descriure's en térmens d'hipergrafos o conjunts independents en grafos de Kneser. Vàries teoremes anàlogues s'apliquen a atres tipos d'objectes matemàtics distints dels conjunts, inclosos els subespacios llineals, les permutació i les cadenes. També descriuen les famílies d'intersecció més grans possibles com les que es formen elegint un element i formant la família de tots els objectes que contenen l'element elegit.

Enunciat

Suponga's que $𝒜$ és una família de subconjunts en $r$ elements distints, que pertanyen a un conjunt de $n$ elements en $n\ge 2r$, i que cada dos subconjunts compartixen a lo manco un element. Llavors, la teorema establix que el número de subconjunts en $𝒜$ és com a màxim el coeficient binomial

$$(\genfrac{}{}{0ex}{}{n-1}{r-1})$$

El requisit de que $n\ge 2r$ siga necessari per a que el problema no siga trivial, es deu a que quan $n<2r$, tots els subconjunts de $r$-elements es intersecan, i la família d'interseccions més gran consistix en tots els conjunts de $r$-elements, en tamany $(\genfrac{}{}{0ex}{}{n}{r})$.

El mateix resultat pot formular-se com a part de la teoria d'hipergrafos. Una família de conjunts també pot denominar-se hipergrafo, i quan tots els conjunts (que en este context es denominen "hiperaristas") tenen el mateix tamany $r$, es denomina hipergrafo $r$-uniforme. Per lo tant, la teorema proporciona un llímit superior per al número de hiperaristas superpostes per parells en un hipergrafo $r$-uniforme en $n$ vèrtiços i $n\ge 2r$.Plantilla:Sfnp

El grafo de Kneser $K{G}_{5,2}$, en un vèrtiç per cada subconjunt de dos elements del conjunt de cinc elements {1,2,3,4,5} i una aresta per cada parell de subconjunts disjuntos. Segons la teorema de Erdős–Ko–Rado, els conjunts independents d'este grafo tenen com a màxim quatre vèrtiços

La teorema també pot formular-se en térmens de teoria de grafos: el conjunt independent del grafo de Kneser $K{G}_{n,r}$ per a $n\ge 2r$ és

$$\alpha (K{G}_{n,r})=(\genfrac{}{}{0ex}{}{n-1}{r-1}).$$

Est és un grafo en un vèrtiç per a cada subconjunt de $r$-elements d'un conjunt de $n$-elements i una aresta entre cada parell de conjunts disjuntos. Un conjunt independent és una colecció de vèrtiços que no té arestes entre els seus parells, i el número d'independència és el tamany de el conjunt independeinte. més gran. Ya que els grafos de Kneser tenen simetria que duen qualsevol vèrtiç a qualsevol atre vèrtiç (són grafos de vèrtiços transitivos), el seu número cromàtic fraccionario és igual al cocient del seu número de vèrtiços i del seu número d'independència. Per lo tant, una atra forma d'expressar la teorema de Erdos-Ko-Rado és que estos grafos tenen un número cromàtic fraccionario que val exactament $n/r$.Plantilla:Sfnp

Història

Paul Erdős, Chao Ko i Richard Rado varen demostrar esta teorema en 1938 despuix de treballar junts en Anglaterra. Rado s'havia mudat de Berlín a l'Universitat de Cambridge i Erdos d'Hongria a l'Universitat de Mánchester, abdós escapant de l'influència de l'Alemània nazi. Ko va ser alumne de Louis Mordell en Mánchester.Plantilla:Sfnp No obstant, no varen publicar el resultat fins a 1961, degut, en part, a la falta d'interés en la teoria de conjunts combinatoris en la década de 1930 i al creixent interés en el tema en la década de 1960.Plantilla:Sfnp L'artícul de 1961 va plantejar el resultat d'una forma aparentment més general, en la que solament es requeria que els subconjunts tingueren un tamany a lo manco de $r$, i satisferen el requisit adicional de que cap subconjunt estiguera contingut en cap atre. Una família de subconjunts que complixca estes condicions pot ampliar-se a subconjunts de tamany exactament $r$ per mig de l'aplicació de el teorema de Hall,Plantilla:Sfnp o seleccionant cada subconjunt ampliat de la mateixa cadena en una descomposició en una cadena de conjunts simètrica.Plantilla:Sfnp

Vore també

• Teorema de Helly, sobre les condicions que garantisen que les famílies de conjunts convexos que es intersecan tinguen una intersecció comuna.
• Teorema de Sperner, una cota superior per a famílies de conjunts no anidados per parells.
• Sistema de Steiner, famílies de conjunts uniformes de tamany màxim en les que cap parell (en lloc de tots) té una intersecció gran.
• Girasol (matemàtiques), una família de conjunts a on (a diferència de les famílies de màxima intersecció ací mostrades) tots els parells tenen interseccions iguals.
• Thrackle, un problema sense resoldre sobre el tamany de les famílies de curves que es intersecan.

Referències

Obres citades

• «The complete intersection theorem for systems of finite sets».European Journal of Combinatorics.18(2)

125–136.doi:10.1006/eujc.1995.0092.