Points on a Plane: Does n/2 Lines Exist?

[Dragonfall]

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.

 

[tiny-tim]

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.

Hi Dragonfall!

If don't get it … 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.

 

[Dragonfall]

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.

 

[Tedjn]

Poking around, my friend managed to find the following, which seems to say that the statement is false: http://www.jaist.ac.jp/~uehara/JCCGG09/submissions/jccgg2009_submission_57.pdf

 

[Dragonfall]

If you replace it with \lfloor n/2\rfloor, it still holds.

 

[tiny-tim]

ah, I understand now …

this is a 1951 conjecture of G.A.Dirac (stepson of the Dirac ) "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") …

for any collection of n points, not all collinear, there exist at least n⁄2 lines containing exactly two points.

The first conjecture has 4 similar exceptions for n = 11 (in Tedjn's 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.

 

[Dragonfall]

Ah, this explains why I've failed to prove it. Thanks.