Connected Baranyai's theorem (Q397066)

From MaRDI portal
scientific article
Language Label Description Also known as
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
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    complete uniform hypergraph
    0 references
    factorization
    0 references
    partition
    0 references
    connected components
    0 references
    0 references
    0 references