[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/jp\/wiki21\/archives\/106244#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/jp\/wiki21\/archives\/106244","headline":"Beck’s theorem (geometry) – Wikipedia","name":"Beck’s theorem (geometry) – Wikipedia","description":"On lower bounds on the number of lines determined by a set of points in the plane In discrete geometry,","datePublished":"2022-03-09","dateModified":"2022-03-09","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/jp\/wiki21\/archives\/author\/lordneo#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/jp\/wiki21\/archives\/author\/lordneo","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/1\/1c\/Wiki_letter_w_cropped.svg\/20px-Wiki_letter_w_cropped.svg.png","url":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/1\/1c\/Wiki_letter_w_cropped.svg\/20px-Wiki_letter_w_cropped.svg.png","height":"14","width":"20"},"url":"https:\/\/wiki.edu.vn\/jp\/wiki21\/archives\/106244","about":["Wiki"],"wordCount":4492,"articleBody":"On lower bounds on the number of lines determined by a set of points in the plane  In discrete geometry, Beck’s theorem is any of several different results, two of which are given below. Both appeared, alongside several other important theorems, in a well-known paper by J\u00f3zsef Beck.[1] The two results described below primarily concern lower bounds on the number of lines determined by a set of points in the plane. (Any line containing at least two points of point set is said to be determined by that point set.)Table of ContentsErd\u0151s\u2013Beck theorem[edit]Statement[edit]Proof[edit]Beck’s theorem[edit]Statement[edit]Proof[edit]References[edit]Erd\u0151s\u2013Beck theorem[edit]The Erd\u0151s\u2013Beck theorem is a variation of a classical result by L. M. Kelly and W. O. J. Moser[2] involving configurations of n points of which at most n\u00a0\u2212\u00a0k are collinear, for some 0\u00a0(2j2)\u2264(n2){displaystyle |L|cdot {2^{j} choose 2}leq {n choose 2}}. Now using Szemer\u00e9di\u2013Trotter theorem, it follows that the number of incidences between P and L is at most O(n2\/22j+n){displaystyle O(n^{2}\/2^{2j}+n)}. All the lines connecting j-connected points also lie in L, and each contributes at least 2j{displaystyle 2^{j}} incidences. Therefore, the total number of such lines is O(n2\/23j+n\/2j){displaystyle O(n^{2}\/2^{3j}+n\/2^{j})}.Since each such line connects together \u03a9(22j){displaystyle Omega (2^{2j})} pairs of points, we thus see that at most O(n2\/2j+2jn){displaystyle O(n^{2}\/2^{j}+2^{j}n)} pairs of points can be j-connected.Now, let C be a large constant. By summing the geometric series, we see that the number of pairs of points which are j-connected for some j satisfying C\u22642j\u2264n\/C{displaystyle Cleq 2^{j}leq n\/C} is at most O(n2\/C){displaystyle O(n^{2}\/C)}.On the other hand, the total number of pairs is n(n\u22121)2{displaystyle {frac {n(n-1)}{2}}}.  Thus if we choose C to be large enough, we can find at least n2\/4{displaystyle n^{2}\/4} pairs (for instance) which are not j-connected for any C\u22642j\u2264n\/C{displaystyle Cleq 2^{j}leq n\/C}.  The lines that connect these pairs either pass through fewer than 2C points, or pass through more than n\/C points.  If the latter case holds for even one of these pairs, then we have the first conclusion of Beck’s theorem. Thus we may assume that all of the n2\/4{displaystyle n^{2}\/4} pairs are connected by lines which pass through fewer than 2C points.  But each such line can connect at most C(2C\u22121){displaystyle C(2C-1)} pairs of points.  Thus there must be at least n2\/4C(2C\u22121){displaystyle n^{2}\/4C(2C-1)} lines connecting at least two points, and the claim follows by taking K=4C(2C\u22121){displaystyle K=4C(2C-1)}.References[edit]^ a b Beck, J\u00f3zsef (1983). “On the lattice property of the plane and some problems of Dirac, Motzkin, and Erd\u0151s in combinatorial geometry”. Combinatorica. 3: 281\u2013297. doi:10.1007\/BF02579184. MR\u00a00729781.^ “William O. J. Moser”.^ Kelly, L. M.; Moser, W. O. J. (1958), “On the number of ordinary lines determined by n points”, Can. J. Math., 10: 210\u2013219, doi:10.4153\/CJM-1958-024-6^ Elekes, Gy\u00f6rgy; T\u00f3th, Csaba D. (2005). “Incidences of not-too-degenerate hyperplanes”. Proceedings of the twenty-first annual symposium on Computational geometry. Pisa, Italy: Annual Symposium on Computational Geometry: 16\u201321. ISBN\u00a01-58113-991-8.^ Beck’s Theorem can be derived by letting k\u00a0=\u00a0n(1\u00a0\u2212\u00a01\/C) and applying the Erd\u0151s\u2013Beck theorem."},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/jp\/wiki21\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/jp\/wiki21\/archives\/106244#breadcrumbitem","name":"Beck’s theorem (geometry) – Wikipedia"}}]}]