Teorema de Baranyai
En matemática combinatoria , el teorema de Baranyai (probado y nombrado en honor a Zsolt Baranyai ) trata de las descomposiciones de hipergráficos completos .
El enunciado del resultado es que si son números naturales y r divide k , entonces el hipergráfico completo se descompone en 1 factores . es un hipergrafo con k vértices, en el que cada subconjunto de r vértices forma un hipergrabado; un factor 1 de este hipergráfico es un conjunto de hipergrafias 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 hipergráfico pueden dividirse en subconjuntos de r vértices de diferentes maneras, de tal manera que cada El subconjunto r -element aparece exactamente en una de las particiones.
En el caso especial , tenemos un gráfico completo de vértices y deseamos colorear los bordes con colores para que los bordes 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 todo gráfico completo con un número par de vértices tiene un color de borde cuyo número de colores es igual a su grado , o de manera equivalente, que sus bordes pueden dividirse en coincidencias perfectas . 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 probado por Zsolt Baranyai en 1975.
