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

115 Views Asked by At

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.

1

There are 1 best solutions below

1
On BEST ANSWER

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