Skip to main content
4 of 4
replaced http://mathoverflow.net/ with https://mathoverflow.net/

You have equality, yes.

The same proof I gave here applies equally well to this situation.

Here's a generalization of both (also implied by that proof).

Suppose $\mathcal{H}$ is a hypergraph on $[n]$ where any $r$ edges share at most $1$ point and each point is contained in at least $r$ edges. Then if $m$ is the number of edges in $\mathcal{H}$, we need $n \leq {m \choose r}$ and this is tight.

(The modification of the proof is to consider $r$-element subsets of $V_i$.)

Pat Devlin
  • 2.7k
  • 16
  • 21