Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Have you checked Richard Guy's book titled "Unsolved problems in combinatorial geometry" or something like that? –  Jyrki Lahtonen Jul 20 '11 at 13:41
    
It seems that we all interpret your question differently, could you modify it so as to remove the ambiguities raised in the comments below? –  Anthony Labarre Jul 20 '11 at 14:03

2 Answers 2

up vote 5 down vote accepted

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/

share|improve this answer
    
The important part is of course the lower bound, which disproves my conjecture. Thanks for the pointer. –  Ari Jul 21 '11 at 9:01

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

share|improve this answer
    
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. –  Jyrki Lahtonen Jul 20 '11 at 13:40

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.