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, \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.

• 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 E Speyer Mar 30 '12 at 12: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