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 .
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.
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.
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.
{{citation}}
: Mantenimiento de CS1: falta la ubicación del editor ( enlace ).