Connected Baranyai's theorem (Q397066)

From MaRDI portal





scientific article; zbMATH DE number 6330534
Language Label Description Also known as
default for all languages
No label defined
    English
    Connected Baranyai's theorem
    scientific article; zbMATH DE number 6330534

      Statements

      Connected Baranyai's theorem (English)
      0 references
      0 references
      14 August 2014
      0 references
      Let \(\lambda K_{n}^{h}\) be the complete \(h\)-uniform hypergraph with \(n\) vertices and every edge of multiplicity \(\lambda\) and \(r_1+r_2+\dots +r_k=\lambda {{n-1}\choose{h-1}}\). Then, an \((r_1,r_2,\dots,r_k)\)-factorization of \(\lambda K_{n}^{h}\) is a partition of the edge set of \(\lambda K_{n}^{h}\) into factors \(F_1,F_2,\dots,F_k\), where \(F_i\) is \(r_i\)-regular. When \(r_1=r_2=\dots=r_k=r\), then the factorization is called an \(r\)-factorization. The well known Baranyai's theorem states that \(K_{n}^{h}\) can be decomposed into edge-disjoint \(r\)-regular factors if and only if \(h\) divides \(rn\) and \(r\) divides \({n-1}\choose{h-1}\). The author generalizes Baranyai's result by proving that \(\lambda K_{n}^{h}\) has an \((r_1,r_2,\dots ,r_k)\)-factorization if and only if \(h\) divides \(r_i n\) for all \(r_i\), \(1\leq i\leq k,\) and \(\sum_{i=1}^{k}r_i=\lambda{{n-1}\choose{h-1}}\). Moreover, the result is strengthening Baranyai's theorem because it further asserts that whenever \(r_i\geq 2\), the \(r_i\)-regular factor \(F_i\) can be guaranteed to be connected.
      0 references
      complete uniform hypergraph
      0 references
      factorization
      0 references
      partition
      0 references
      connected components
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references