Let $G = (V,E)$ be an $L$-uniform hypergraph, s.t.:
- $n := |V|$
- $L$ divides $(n - 1)$
- every subset of $V$ of size $(n - 1)$ has a perfect matching (which would be a near-perfect matching in $G$)
Can we give any non-trivial lower bound on the number of hyper-edges in the graph, i.e. $|E|$ ?
Note that a lower bound of $|E| \ge \frac{n - 1}{L}$ is trivial...
If we note that the degree of each vertex is at least 2, then a double-counting argument gives a slightly better lower bound of $|E| \ge \frac{2n}{L}$.
Can we show a lower bound of the form $|E| = \Omega(n)$ (for any suitable $L$) ?
Thanks a lot :)
Yes, there must be at least $n$ edges.
In fact, more is true: if $H$ is any (not necessarily uniform) hypergraph on $n \ge 2$ vertices such that for every $v \in V(H)$, $V(H) - \{v\}$ can be partitioned into edges of $H$, then $|E(H)| \ge n$.
To see this, let $V(H) = \{v_1, v_2, \dots, v_n\}$, and define for all edges $e \in E(H)$ the vector $\mathbf x^e \in \mathbb R^n$ with $$x^e_i = \begin{cases}1 & v_i \in e, \\ 0 & v_i \notin e.\end{cases}$$ Then for any $v_i$, the sum of $\mathbf x^e$ over the edges $e$ partitioning $V(H) - \{v_i\}$ gives us the vector $(1,\dots,1,0,1,\dots,1)$ with a $0$ in the $i^{\text{th}}$ position, and $1$'s everywhere else.
These vectors are linearly independent, since $$\det\begin{bmatrix}0 & 1 & 1 & \cdots & 1 \\ 1 & 0 & 1 & \cdots & 1 \\ 1 & 1 & 0 & \cdots & 1\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & 1 & 1 & \cdots & 0\end{bmatrix} = (-1)^{n-1}(n-1) \ne 0,$$ so the vectors $\{\mathbf x^e : e \in E(H)\}$ span $\mathbb R^n$, and therefore there must be at least $n$ of them.
The bound $n$ is best possible. For example, for any $n$ and any $L$ such that $L \mid n-1$, we can take the tight cycle with edges $\{v_i, v_{i+1}, \dots, v_{i+L-1}\}$ for $1 \le i \le n$ (wrapping around modulo $n$ from $v_n$ to $v_1$) and get a hypergraph with this property.