1
$\begingroup$

One version of the Szemeredi-Trotter theorem states the following:

Given a set of $L$ lines in the plane, the number of points incident to at least $k$ lines is bounded above by a constant times $L/k + L^2/k^3$.

This version of the theorem can be found here in notes written by Adam Hesterberg for Larry Guth's polynomial method class: http://math.mit.edu/~lguth/PolyMethod/lect6.pdf.

Let's suppose instead that I have a collection of $R$ red lines and $B$ blue lines, where $R$ is much smaller than $B$ (like $R$ is about $B^{1/2}$ or so). Assume that none of the red lines are parallel. I would like a bound for the number of points lying on at least one red line that are incident to at least $k$ blue lines. It's possible to use the Szemeredi-Trotter theorem to get a bound of $B/k + B^2/k^3$ by just ignoring the condition that the points need to lie along a red line. Does anyone know if a better bound is possible?

$\endgroup$
1
  • $\begingroup$ When $k >> L^{1/2}$ this version of the Szemeredi-Trotter theorem tells us that the best you can do, up to a constant factor, is partition the lines into $L/k$ sets of size $k$ and have all the lines each part coincide at a point. Seems to me that if we are in this range we could just put all these intersection points on a single red line, so in this range $B/k$ should still be optimal. $\endgroup$
    – Nate
    Aug 12, 2014 at 20:04

1 Answer 1

0
$\begingroup$

I will describe a construction in the dual setting.

Take a $(k+1)\times n/k$ size grid of points. Color the top row red, the rest blue, so we have $n$ red points and $k$ blue points. The number of lines that contain one point of each row is $\Theta(n^2/k^3)$.

So translating it back to your problem, this gives a construction of $B^2/k^3$ if $R=k$, so this shows that your bound is sharp if $R\ge k$.

$\endgroup$
1
  • $\begingroup$ Thanks! Between this and Nate's comment, I think that completely answers my question. $\endgroup$
    – Rob F
    Aug 19, 2014 at 18:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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