Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Points on a plane

  1. Dec 21, 2009 #1
    If you put n points on a plane, not all on a line, is there always a point with at least n/2 lines incident? The lines in question are determined by the points themselves.
  2. jcsd
  3. Dec 22, 2009 #2


    User Avatar
    Science Advisor
    Homework Helper

    Hi Dragonfall! :smile:

    If don't get it :confused: … n-1 lines are always incident at each original point;

    or if you exclude the original n points, then eg it's not even true for a regular pentagon.
  4. Dec 22, 2009 #3
    If 3 points are on a line, then you count it as one line, not 3. If every point "sees" every other point, then yes, each point has n-1 lines incident. However it's possible that some points are "blocked" by others. Take a pencil; there is a point with n-1 lines incident, but all others have only 2.
  5. Dec 22, 2009 #4
  6. Dec 22, 2009 #5
    If you replace it with [tex]\lfloor n/2\rfloor[/tex], it still holds.
  7. Dec 23, 2009 #6


    User Avatar
    Science Advisor
    Homework Helper

    ah, I understand now …

    this is a 1951 conjecture of G.A.Dirac (stepson of the Dirac :wink:) "for any arrangements of n points, not all on a line, the maximum number of incident lines through a point can not be less than [n/2], and he claimed it is true for n ≤ 14."

    He had a similar conjecture (see http://en.wikipedia.org/wiki/Sylvester–Gallai_theorem#The_existence_of_many_ordinary_lines") …
    The first conjecture has 4 similar exceptions for n = 11 (in Tedjn's :smile: link), and the second has a very easy exception for n = 7 (and an exception for n = 13 in the projective plane).

    Neither conjecture (even with those exceptions) has been proved.
    Last edited by a moderator: Apr 24, 2017
  8. Dec 24, 2009 #7
    Ah, this explains why I've failed to prove it. Thanks.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook