# Family of subsets such that there are at most two sets containing two given elements

We have a set $S$ with $k$ elements, a positive integer $n$, and subsets $S_1, S_2, \cdots, 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.

-
Have you tried taking the characteristic functions of the $S_i$, adding them up, and looking at the $\ell_2$ norm? The condition on the $S_i$ should put a strong condition on the average inner product, and then the Cauchy-Schwarz inequality should give a bound the other way. I feel this ought to work, but can't quite be certain without writing it down. – gowers Mar 25 '12 at 21:52
Your 1st paragraph asks a question about $k$ without having previously made any mention of this symbol. Please edit/clarify. – Gerry Myerson Mar 25 '12 at 22:35
Sorry, I forgot to define $k = |S|.$ @gowers: After reading your comment, I used that to get $k = \Omega(n^\frac{5}{3})$, which is stronger than the bound one gets by simply counting edges. I used the condition in a rather weak way, so this can probably be extended. – David Mar 25 '12 at 23:06
Actually, the derivation of my $n^\frac{5}{3}$ bound is false. My attempt actually gives $n^\frac{3}{2},$ no better than the edge-counting way. – David Mar 26 '12 at 14:27
This is a "packing problem", wherein one asks for how many sets of size something from a universal set of size something can be chosen so that each $t$-subset is covered at most $\lambda$ times. It can also be expressed in terms of error correcting codes. The version with "exactly lambda times" is a block design problem. There is quite a lot of literature on these but I don't know it well enough to say if your question has been answered. – Brendan McKay Mar 28 '12 at 13:46

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

-
Potentially confusing typo: In the start of the second paragraph, should be $k, l \leq p$, not $k, l \leq n$, right? – David Speyer Mar 30 '12 at 12:53
Thanks a lot -- I've edited it now. – gowers Mar 30 '12 at 13:53
It is perhaps worth adding that the above construction is generated by two standard tricks. The first is to dualize the problem by defining $T_i$ to be the set of $k$ such that $i\in S_k$ and reformulating the conditions in terms of the $T_i$. (The main one says that the maximum intersection of any two $T_i$ is 2.) The other trick is to use graphs of polynomials to get plenty of sets with small intersections. – gowers Mar 30 '12 at 19:37