0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ @rose: I repaired the broken link (the apostrophe needs a special character). $\endgroup$ Apr 11, 2012 at 19:50

1 Answer 1

1
$\begingroup$

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

$\endgroup$
4
  • $\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
    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
    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
    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
    Apr 20, 2012 at 5:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.