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.

  • 5
    $\begingroup$ 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. $\endgroup$ – gowers Mar 25 '12 at 21:52
  • $\begingroup$ Your 1st paragraph asks a question about $k$ without having previously made any mention of this symbol. Please edit/clarify. $\endgroup$ – Gerry Myerson Mar 25 '12 at 22:35
  • $\begingroup$ 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. $\endgroup$ – David Mar 25 '12 at 23:06
  • $\begingroup$ 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. $\endgroup$ – David Mar 26 '12 at 14:27
  • $\begingroup$ 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. $\endgroup$ – 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)$.

  • $\begingroup$ Potentially confusing typo: In the start of the second paragraph, should be $k, l \leq p$, not $k, l \leq n$, right? $\endgroup$ – David E Speyer Mar 30 '12 at 12:53
  • 1
    $\begingroup$ 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. $\endgroup$ – gowers Mar 30 '12 at 19:37

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.