0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$ Oct 13 '20 at 3:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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