
> 
> We have a set $S$ with $k$ elements, a positive integer $n$, and subsets $S\_1, S\_2, \dots, S\_n,$ each with $n$ elements. For any two elements $a,b$ of $S$, there are at most two sets $S\_i$ containing both $a$ and $b$. Must $k$ be $\Omega(n^2)?$
> 
> 
> 


If we require instead that, for any two $a,b$ there are at most **one** set $S\_i$ containing both $a$ and $b$, then we have $k \ge \frac{(n+1)n}{2},$ because $S\_i$ contains at least $n+1-i$ elements that are not in $S\_1, S\_2, \cdots, S\_{i-1}.$ In this case, a special case of this is that if we have $n$ pairwise disjoint lines in the plane and a set of points such that each line contains at least $n$ points, we have at least $\frac{n(n+1)}{2}$ points.


One motivation for this question is the generalization of Szemerédi-Trotter to a family of curves satisfying 1) two curves intersect in at most m points and 2) for every two points, at most n curves go through both of those points. 


I'm trying to solve a graph theoretical problem assuming only an analogue of condition 2, and this is the easiest case of it. I expect that an extra condition is necessary, but I cannot find any obvious counterexamples.



Family of subsets such that there are at most two sets containing two given elements
I think I may have an answer. Let $p$ be a prime (for simplicity). Let $r=p^3$ and let $T\_1,\dots,T\_r$ be all possible graphs of quadratic functions defined on the integers mod $p$. These graphs live in a set of size $n=p^2$, so $r=n^{3/2}$. Note that no two quadratic functions agree in more than two places, so $|T\_i\cap T\_j|\leq 2$ for every $i\ne j$. 


Now for each $k,l\leq p$ let $S\_{kl}=\{i:(k,l)\in T\_i\}$. If $q\_i$ is the quadratic function corresponding to $T\_i$, then $S\_{kl}=\{i:q\_i(k)=l\}$. Then $|S\_{kl}|=p^2=n$ and there are $n$ of these sets. Each $S\_{kl}$ is a subset of $\{1,2,\dots,r\}$ so lives inside a set of size $n^{3/2}$. And finally, the number of $S\_{kl}$ that contain $i$ and $j$ is the number of pairs $(k,l)$ such that $q\_i(k)=l$ and $q\_j(k)=l$. But two distinct quadratic functions can agree in at most two places (since their difference has at most two roots).


Thus, it seems to me that the $n^{3/2}$ bound is the correct one and not $\Omega(n^2)$.


