On Non-Uniform Baranyai Factorizations

Source abstract

For a fixed nonempty finite set $L$ of positive integers and $k=\max L\ge2$, let $\binom{[n]}{L}=\bigcup_{\ell\in L}\binom{[n]}{\ell}$ denote the non-uniform hypergraph whose edge set consists of all $\ell$-subsets of $[n]$ for $\ell\in L$. A $1$-factor of a hypergraph $H$ is a collection of pairwise disjoint edges whose union is $V(H)$. We say $H$ is $1$-factorable if $E(H)$ can be partitioned into $1$-factors. In this paper, we study the 1-factorability of $\binom{[n]}{L}$. Earlier work of He, Huang, and Ma shows that, for all sufficiently large $n$, $1$-factorability can occur only in the residue classes $0$ and $-1$ modulo $k$: it always occurs in class $0$, whereas it occurs in class $-1$ only if $k-1\in L$. We determine exactly when $1$-factorability occurs in this exceptional class. More precisely, we define a finite gcd-peeling algorithm on $L\setminus\{k-1,k\}$ and prove that $\binom{[qk-1]}{L}$ is $1$-factorable if and only if the algorithm accepts. As a consequence, our result provides a criterion for the $1$-factorability of $\binom{[n]}{L}$ and confirms the conjecture posed by He, Huang, and Ma.