Let $3 \leq k < n \in \mathbb{N}$. By $[n]^k$ we denote the collection of the subsets of $n = \{0,\ldots,n-1\}$ that have size $k$. We say that a hypergraph $H=(n,E)$ is $k$-uniform if $E\subseteq [n]^k$. Moreover, $H=(n, E)$ is linear if $|e_1\cap e_2| \leq 1$ for $e_1\neq e_2\in E$, and it is maximal linear if $E\subseteq E'\subseteq [n]^k$ and $E\neq E'$ imply that $(n, E')$ is no longer linear.

Question. Are there integers $k < n$ with $k\geq 3$ and maximal linear hypergraphs $H_i = (n, E_i)$ for $i = 1,2$ such that $|E_1| \neq |E_2|$? (If yes, it would also be interesting to know how big the difference of the edge sets can become in terms of $n$, but this information is not needed for acceptance of answer.)


2 Answers 2


For the case $k=3$ we have partial Steiner triple systems as a design theory name for $3$-uniform linear hypergraphs. The spectrum $S^{(3)}(v)$ consists of the sizes of maximal partial Steiner triple systems taking triples from a $v$-element set. The paper below gives the final steps in determining $S^{(3)}(v)$ for each $v$. I can access the paper through my university, but I did not find a freely available version.

The spectrum of maximal partial steiner triple systems

However, the main result (and other references) can be found in

Maximal designs and configurations - a survey

looking in Section 9 about partial Steiner triple systems. In particular, you do have multiple sizes in the spectrum. If $v = 12k + r$, then the smallest is around $12k^2$ while the largest is around $24k^2$ (of course with linear and constant terms depending on cases $\pmod{12}$ as well as other caveats).


If all maximal $k$-regular linear hypergraphs of order $n$ had the same size, then finding the maximum possible size would be a trivial problem, just use the greedy algorithm.

For a concrete counterexample, let $k=3$ and $n=7$. The Steiner triple system on $7$ points (the Fano plane) has $7$ triples. Here is a maximal linear $3$-hypergraph with $5$ triples: $ABC$, $ADE$, $BFG$, $CDF$, $CEG$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.