A hypergraph $H$ is a pair $H = (X,E)$ where $X$ is a set of elements called nodes or vertices, and $E$ is a set of non-empty subsets of $X$ called hyperedges or edges.
We say a hypergraph is $k$-uniform if all its hyperedges have size (cardinality) $k$.
We say a hypergraph is linear if every two hyperedges have at most one vertex in common.
I am looking for an upper bound for the number of hyperedges of a $k$-uniform linear hypergraph with $n$ nodes.
A naive bound that doesn't take in count the "linearity" would be $\binom nk $
This bound is tight in the case $k=2$ since such hypergraphs would simply be graphs, but in the general case I am not sure.
Can anyone help me with this?
Thanks
Best Answer
Look at all edges containing vertex $v$. They can have no other vertices in common, so the other $k-1$ vertices in each edge are disjoint. This means there are at most $\frac{n-1}{k-1}$ edges containing $v$.
Counting each vertex separately, this means there are at most $\frac{n(n-1)}{k-1}$ pairs $(v,e)$ where $v\in e$. Since there are $k$ such pairs for each edge $e$, there are at most $\frac{n(n-1)}{k(k-1)}$ edges in total.