3
$\begingroup$

Let $H=(V,E)$ be a hypergraph such that $V\neq \varnothing$ and $\varnothing \notin E$. A matching is a subset $M\subseteq E$ such that $m_1\neq m_2 \in M$ implies $m_1\cap m_2 = \varnothing$, and $M$ is said to be perfect if $\bigcup M = V$. We say that $H$ is $1$-factorizable if $E$ is the disjoint union of perfect matchings.

If $H$ is $1$-factorizable, it is easy to see that it implies that for any vertices $v_1,v_2\in V$ we have $\text{deg}(v_1) = \text{deg}(v_2)$ where for $v\in V$ we set $\text{deg}(v) = |\{e\in E: v\in e\}|$.

We regard every positive integer $n$ as an ordinal, that is $n = \{0, \ldots, n-1\}$. If $X$ is a set and $\kappa$ is a cardinal, we let $[X]^\kappa$ be the collection of subsets of $X$ having cardinality $\kappa$.

Question. If $k, n> 2$ are integers, is the hypergraph $(k\cdot n, [k\cdot n]^k)$ $1$-factorizable?

(The answer is yes for $k\leq 2$.)

$\endgroup$

1 Answer 1

6
$\begingroup$

This is Baranyai's theorem. Other than in Baranyai's original paper you can also find a cool proof in the article "Uniform hypergraphs" by Brouwer and Schrijver which uses max-flow min-cut.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .