Connected Baranyai's theorem (Q397066)

From MaRDI portal





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

      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
      0 references