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