5
$\begingroup$

Let $H(n,r)$ be the set of $r$-uniform hypergraph with $n$ vertices that have only disjoint perfect matchings (i.e. every hyperedge only appears in at most one of the perfect matchings). Let $m(h(n,r))$ be the number of perfect matchings of a hypergraph $h \in H(n,r)$.

What is $$M(n,r)=\max_{h(n,r) \in H(n,r)} m(h(n,r))$$ for each value of $r$ and $n=k\cdot r$ with $k \in \mathbb{N_{\geq 2}}$?

Special Cases:

The case $r=2$, i.e. for conventional graphs, was solved by Ilya Bogdanov:

  • $M(4,2)=3$ (satisfied by the complete graph $K_4$)
  • $M(2m,2)=2$ for all $m \in \mathbb{N_{\geq 3}}$ (satisfied by the cyclic graph $C_{2m}$).

The case $M(n=2r,r=2...7)=3, 10, 35, 126, 462, 1716, 6435$. This sequence corresponds to the first seven entries of OEIS A001700.

$\endgroup$

0

You must log in to answer this question.