1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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