A *complete linear hypergraph* is a [hypergraph](https://en.wikipedia.org/wiki/Hypergraph) $H=(V,E)$ such that 


1. $|e|\geq 2$ for all $e\in E$,
2. $|e\_1\cap e\_2|=1$ for all $e\_1, e\_2\in E$ with $e\_1\neq e\_2$, and
3. for all $v\in V$ we have $|\{e\in E:v\in e\}| \geq 2.$


For $n>2$ set $\mathbb{N}\_n =\{1,\ldots,n\}$ and $$\ell(n)=\min\{|E|: E\subseteq{\cal P}(\mathbb{N}\_n) \text{ and }(\mathbb{N}\_n, E) \text{ is complete linear}\},$$ so $\ell(n)$ is the *greatest lower bound* for the number of edges on a complete linear hypergraph on $n$ points.


**Question**: What is the value of $\ell(n)$, depending on $n$?




---


(Note concerning least upper bounds: If $H=(V,E)$ is a complete linear hypergraph with $|V|=n>2$, then $|E| \leq n$ by the [theorem of DeBruijn-Erdos](https://en.wikipedia.org/wiki/De_Bruijn%E2%80%93Erd%C5%91s_theorem_(incidence_geometry)), and we can reach $|E| = n$ with the so-called "near pencil", see the same link.)



Minimal number of edges for complete linear hypergraphs
Let $L$ be the number of edges in the configuration and $n$ the number of points. Then $n \leq {L \choose 2}$ and this bound is tight.


**There are configurations with that many points:** Let the points correspond to the two element subsets of $\{1, 2, \ldots, k\}$. And let the edges correspond to the numbers $\{1, 2, \ldots , k\}$. Then say edge $L\_i$ contains the vertex $v\_{\{a,b\}}$ iff $i \in \{a,b\}$. This is linear, and it has ${k \choose 2}$ points and $k$ edges. It covers each point exactly twice.


**Any configuration has at most that many points:** The previous answer can be pushed to give $L \geq \sqrt{2n}$, but we can get our above bound exactly. Let $\mathcal{L}$ be the set of edges. For each point $i \in \{1, 2, \ldots , n\}$, associate a set $V\_i \subseteq \mathcal{L}$, which is the edges in $\mathcal{L}$ containing the point $i$. Then for all $i \neq j$, we have $|V\_i \cap V\_j| \leq 1$ (else there are two edges containing the same two points). We know that each point is covered at least twice, so $|V\_i| \geq 2$. For each set $V\_i$, let $W\_i$ be any subset of size $2$ (it doesn't matter how we pick $W\_i$). Then the sets $W\_i$ are distinct $2$-element subsets of $\mathcal{L}$, which means there are at most ${L \choose 2}$ of them.




---


**Added afterwards:** To complete the discussion, we have the corresponding lower bound on $n$ that $L \leq n$. This is by [(generalized) Fisher's inequality](https://en.wikipedia.org/wiki/Fisher's_inequality#Generalization), and it uses the fact that the intersection of any two edges has size $1$. And this can be attained by the near pencil mentioned in original post or a projective plane.


So together, we have $L \leq n \leq {L \choose 2}$ and both bounds are best possible.


