# Lower bound on universe size for set system with pairwise intersections of 1?

Given a finite universe $$U$$, consider a collection of subsets $$S_1, ..., S_n \subset U$$, where each subset has exactly $$k$$ elements. Suppose that each pair of sets has exactly one element in common: that is, give any distinct pair $$i, j \in [n]$$, we have $$\left\vert S_i \cap S_j \right\vert = 1$$.

My question: Given a fixed pair of integers $$(n, k)$$, what is the minimum size of a universe $$U$$ for which such a set system can exist? I am interested in all ranges of parameters but especially when $$n >> k$$.

(Actually, I am also interested in an upper bound, but I believe this will be given by requiring that the sets $$C_1, ..., C_n$$ form a sunflower, so $$\left\vert U \right\vert = n(k-1) + 1$$. Please correct me if this upper bound is wrong).

I think I have made partial progress on this question: in the case where $$n = k + 1$$, I claim that we need $$\left\vert U \right\vert \geq {k + 1 \choose 2} = (1 + 2 + ... + k)$$. This comes from an arrangement where each pair of sets shares a unique element of $$U$$, which intuitively should be the most "efficient" arrangement but I cannot prove this.

Each set $$S_i$$ contains $$\binom{k}2$$ pairs of elements of $$U$$. Furthermore, for any two sets $$S_i$$ and $$S_j$$, the set of pairs of $$S_i$$ is disjoint from the set of pairs of $$S_j$$, because $$|S_i\cap S_j|=1$$. Therefore, the number of pairs of elements appearing in any of the $$S_i$$ is at least $$n\cdot \binom{k}2$$. The number of pairs of elements in $$U$$ must be at least this, which implies $$\binom{|U|}2\ge n\binom{k}2$$ Using the approximation $$\binom{m}2\approx m^2/2$$, this means that roughly $$|U|\ge k\sqrt{n}$$.
Furthermore, this bound is attained whenever $$k=q+1$$ and $$n=q^2+q+1$$, for any prime power $$q$$, by the set of lines in the finite projective plane of order $$q$$.
• Thanks! Do you know if projective space also attains the generalized lower bound? That is, if instead of interections of size $1$ we require that $\forall i, j \left\vert S_i \cap S_j \right\vert = \ell$ then ${\left\vert U \right\vert \choose \ell + 1} \geq n {k \choose \ell + 1}$ by the same reasoning. Do the $\ell$-dimensional subspaces of some projective space over a finite field attain this bound? Oct 13 '20 at 3:05