Teorema de Baranyai

Teorema que trata de las descomposiciones de hipergrafos completos

Partición de un gráfico completo de 8 vértices en 7 colores ( coincidencias perfectas ), caso r  = 2 del teorema de Baranyai

En matemáticas combinatorias , el teorema de Baranyai (demostrado por Zsolt Baranyai y llamado así en honor a él ) trata de las descomposiciones de hipergrafos completos .

Enunciado del teorema

El enunciado del resultado es que si son números enteros y r divide a k , entonces el hipergrafo completo se descompone en 1-factores . es un hipergrafo con k vértices, en el que cada subconjunto de r vértices forma una hiperarista; un 1-factor de este hipergrafo es un conjunto de hiperaristas que toca cada vértice exactamente una vez, o equivalentemente una partición de los vértices en subconjuntos de tamaño  r . Por lo tanto, el teorema establece que los k vértices del hipergrafo pueden ser particionados en subconjuntos de r vértices de diferentes maneras, de tal manera que cada subconjunto de r -elementos aparece en exactamente una de las particiones. ${\displaystyle 2\leq r<k}$ ${\displaystyle K_{r}^{k}}$ ${\displaystyle K_{r}^{k}}$ ${\displaystyle {\binom {k}{r}}{\frac {r}{k}}={\binom {k-1}{r-1}}}$

El casor = 2

En el caso especial , tenemos un gráfico completo en vértices y deseamos colorear las aristas con colores de modo que las aristas de cada color formen una combinación perfecta. El teorema de Baranyai dice que podemos hacer esto siempre que sea par. ${\displaystyle r=2}$ ${\displaystyle K_{n}}$ ${\displaystyle n}$ ${\displaystyle {\binom {n}{2}}{\frac {2}{n}}=n-1}$ ${\displaystyle n}$

Historia

El caso r  = 2 puede reformularse diciendo que cada grafo completo con un número par de vértices tiene una coloración de aristas cuyo número de colores es igual a su grado , o equivalentemente, que sus aristas pueden dividirse en emparejamientos perfectos . Puede usarse para programar torneos de todos contra todos , y su solución ya se conocía en el siglo XIX. El caso de que k  = 2 r también es fácil.

El caso r  = 3 fue establecido por R. Peltesohn en 1936. El caso general fue demostrado por Zsolt Baranyai en 1975.

Referencias

• Baranyai, Zs. (1975), "Sobre la factorización del hipergrafo uniforme completo", en Hajnal, A .; Rado, R .; Sós, VT (eds.), Conjuntos infinitos y finitos, Proc. Col. Keszthely, 1973 , Coloquios de Matemáticas. Soc. János Bolyai, vol. 10, Holanda Septentrional, págs. 91-107.
• van Lint, JH ; Wilson, RM (2001), Un curso de combinatoria (2.ª ed.), Cambridge University Press.
• Peltesohn, R. (1936), Das Turnierproblem für Spiele zu je dreien , Tesis inaugural , Berlín{{citation}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace ).