# Number of edges in $k$-uniform linear hypergraph

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.)

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$$.