0
$\begingroup$

For any set $X$ and any cardinal $\kappa$, let $[X]^\kappa$ denote the subsets of $X$ having cardinality $\kappa$.

A linear hypergraph is a hypergraph such that for all $e\neq e_1 \in E$ we have $|e\cap e_1|\leq 1$. For any positive integer $n$ let $[n] = \{1,\ldots,n\}$. We say that $([n^2], E)$ is a square hypergraph if it is linear and every element of $E$ has $n$ elements.

For any integer $n>1$ let $m(n)$ denote the maximum cardinality of $E$ where $([n^2], E)$ is a square hypergraph. For instance we have $m(2) = 6$. What is the value of $$\lim (\sup)_{n\geq 2}\frac{m(n)}{n^2}\;?$$ (Note: I added $(\sup)$ in case the limit doesn't exist.)

$\endgroup$

1 Answer 1

4
$\begingroup$

In a linear hypergraph, any pair of vertices is contained in at most one hyperedge. Since any hyperedge contains $n$ vertices, it contains ${n \choose 2}$ pairs. Double counting gives $$m(n) \leq \frac{n^2 \choose 2}{n \choose 2} = n (n+1).$$

This bound is sharp when $n$ is a prime power (take an affine plane of order $n$), so $$ \limsup \frac {m(n)}{n^2} = 1. $$

$\endgroup$

You must log in to answer this question.

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