Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 :

  1. 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?

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

share|improve this question
    
@rose: I repaired the broken link (the apostrophe needs a special character). –  Joseph O'Rourke Apr 11 '12 at 19:50

1 Answer 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...)

share|improve this answer
    
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? –  rose Apr 17 '12 at 16:27
    
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. –  domotorp Apr 17 '12 at 18:42
    
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 –  rose Apr 18 '12 at 1:32
    
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. –  domotorp Apr 20 '12 at 5:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.