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.

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

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/

$\endgroup$
  • $\begingroup$ The important part is of course the lower bound, which disproves my conjecture. Thanks for the pointer. $\endgroup$ – Ari Jul 21 '11 at 9:01
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Jul 20 '11 at 13:40

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.