On the number of lines of given points

Question

Hi all, I have a question Concerning Beck's theorem. I have read it from http://en.wikipedia.org/wiki/Beck%27s_theorem and I have two questions :

I suppose Beck's theorem doesn't hold when instead of saying "at least two points" we take "exactly two points",since there may be lines which do not connect exactly two points at all, right?
In the proof mentioned above, I think the statement that "The lines that connect these pairs either pass through fewer than 2C points, or pass through more than n/C points." is incorrect, it should be "fewer than C points" or more than "2n/C points". Am I right or do I miss some logic here?

thanks

@rose: I repaired the broken link (the apostrophe needs a special character). — Joseph O'Rourke, Commented Apr 11, 2012 at 19:50

domotorp · Accepted Answer · 2012-04-15 16:32:33Z

1

1, Yes, it only holds with at least two, otherwise you get the ordinary lines problem, for which the answer is linear in n, for more see http://mathworld.wolfram.com/OrdinaryLine.html

2, No, you miss something, I think it is correct on wikipedia (or I miss some logic...)

answered Apr 15, 2012 at 16:32

domotorp

18.7k3 gold badges57 silver badges125 bronze badges

$\begingroup$ Thanks, but where do I miss something for point 2? Since C<=2^j<=N/C, if line is not j-connected, either it contains more than 2^{j+1} points or less than 2^{j} points, right? Hence it should contain fewer than C or more than 2N/C points. Where is my fault? $\endgroup$
– rose
Commented Apr 17, 2012 at 16:27
$\begingroup$ If a line contains less than 2^j points, then it does not mean that it contains less then C points, because C might not be a power of two. E.g. suppose C=5, j=3. Then if a line contains 7 points, it is 2-connected (and not 3-connected). We cannot conclude that 7<C, only that 7<2C. $\endgroup$
– domotorp
Commented Apr 17, 2012 at 18:42
$\begingroup$ but we are considering the case when line is not j-connected for all j such that C<=2^{j} <=N/C, that's why we can conclude that line should contain less than C points $\endgroup$
– rose
Commented Apr 18, 2012 at 1:32
$\begingroup$ In my previous example, a line with 7 points is not j-connected for any such j (since only 2-connected) and it contains more than C points. $\endgroup$
– domotorp
Commented Apr 20, 2012 at 5:43

Add a comment |

1 Answer 1