Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 replace the word "two" with the word "one", 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.

share|improve this question
3  
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
add comment

1 Answer

up vote 7 down vote accepted

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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