3
$\begingroup$

Here's a conjecture I have. Can anyone prove or disprove it?

Given $n$ distinct straight lines in the plane, the total degree of any $n$ (or less) intersection points is O$(n)$ (where the degree of a point is the number of lines containing it).

Update: I meant the question as Justin Smith understood it. Pick any $n$ or less intersection points (actually they don't even have to be intersection points---just points in the plane). Then for each of these points, count how many lines contain it. Add up these numbers. The conjecture was that the sum will always be O$(n)$. Note that $n$ is both the number of lines and an upper bound on the number of points you are allowed to select.

  • 0
    It seems that we all interpret your question differently, could you modify it so as to remove the ambiguities raised in the comments below?2011-07-20

2 Answers 2

4

The sum of "degrees" of a set of points is the total number of "incidences" for those points. There're numerous related bounds, the most famous of which (and applicable to this question) is Szemeredi-Trotter. http://en.wikipedia.org/wiki/Szemer%C3%A9di%E2%80%93Trotter_theorem

This bound applies even when you only select a subset of the lines' intersection points.

And that bound is tight, i.e., there are known arrangements of lines that attain the asymptotic bound.

Tao has a demonstration of points and lines that achieves Omega(n^(4/3)) incidences here: http://terrytao.wordpress.com/2009/06/12/the-szemeredi-trotter-theorem-and-the-cell-decomposition/

  • 0
    The important part is of course the lower bound, which disproves my conjecture. Thanks for the pointer.2011-07-21
1

Unless I'm missing something, I don't think this holds: write numbers $1$ to $n$ on line $A$ in the natural order, then the same numbers but in the reverse order on a parallel line $B$, and connect $i$ on $A$ to $i$ on $B$ by a straight line, spacing numbers as required so that all intersections have degree $2$. Then you have ${n \choose 2}$ intersections of degree $2$.

  • 0
    I think the question is about a bound on the total degree of the $n$ highest degree points of intersection. The bound should hold no matter how you draw the lines.2011-07-20