Введение
О нижних оценках числа прямых, определяемых набором точек на плоскости
теория категорий, разработанная другим автором
В дискретной геометрии теорема Бека – это любое из нескольких различных результатов, два из которых приведены ниже. Обе теоремы появились вместе с несколькими другими важными теоремами в известной работе Йожефа Бека, рассматривая конфигурации из n точек, среди которых не более n–k коллинеарны, для некоторого 0 < k < n. Они показали, что если n достаточно велико относительно k, то конфигурация определяет не менее kn – (1/2)(3k + 2)(k – 1) прямых. Элекеш и Чаба Тот заметили, что теорема Эрдеша-Бека нелегко обобщается на более высокие размерности. Например, рассмотрим множество из 2n точек в R3, все лежащие на двух скрещивающихся прямых. Предположим, что каждая из этих прямых содержит по n точек. Такая конфигурация точек определяет только 2n плоскостей. Следовательно, тривиального расширения гипотезы для множеств точек в Rd недостаточно для получения желаемого результата. Этот результат был впервые предположен Эрдешем и доказан Беком. (См. теорему 5.2.)
the category theory developed by a different author
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ózsef Beck. involving configurations of n points of which at most n − k are collinear, for some 0 < k < O They showed that if n is sufficiently large, relative to k, then the configuration spans at least kn − (1/2)(3k + 2)(k − 1) lines. Elekes and Csaba Toth noted that the Erdős–Beck theorem does not easily extend to higher dimensions. Take for example a set of 2n points in R3 all lying on two skew lines. Assume that these two lines are each incident to n points. Such a configuration of points spans only 2n planes. Thus, a trivial extension to the hypothesis for point sets in Rd is not sufficient to obtain the desired result. This result was first conjectured by Erdős, and proven by Beck. (See Theorem 5.2 in.)
Заявление
Пусть S — множество из n точек на плоскости. Если на любой прямой лежит не более n − k точек для некоторого 0 ≤ k < n − 2, то существует Ω(nk) прямых, определяемых точками из S.
Теорема Бека
Теорема Бека утверждает, что конечные наборы точек на плоскости попадают в одну из двух крайних ситуаций: либо большая доля точек лежит на одной прямой, либо для соединения всех точек требуется большое количество прямых. Хотя в работе Бека это явно не указано, этот результат вытекает из теоремы Эрдеша — Бека.
Доказательство
Доказательство теоремы Бека может быть дано следующим образом. Рассмотрим множество P из n точек на плоскости. Пусть j – положительное целое число. Будем говорить, что пара точек A, B в множестве P является j-связанной, если прямая, соединяющая A и B, содержит от до точек из P (включая A и B). Из теоремы Семереди–Троттера следует, что число таких прямых равно , а именно: рассмотрим множество P из n точек и множество L, состоящее из всех прямых, определяемых парами точек из P, которые содержат по крайней мере точек из P. Поскольку никакие две точки не могут лежать на двух различных прямых. Теперь, используя теорему Семереди–Троттера, получаем, что число инциденций между P и L не превышает . Все прямые, соединяющие j-связанные точки, также принадлежат L, и каждая из них вносит не менее инциденций. Следовательно, общее число таких прямых равно . Поскольку каждая такая прямая соединяет пар точек, мы видим, что не более пар точек могут быть j-связанными. Теперь пусть C – большая константа. Суммируя геометрическую прогрессию, получаем, что число пар точек, которые j-связаны для некоторого j, удовлетворяющего , не превышает . С другой стороны, общее число пар равно . Таким образом, если выбрать C достаточно большим, то можно найти по крайней мере пар (например), которые не являются j-связанными ни при каком . Прямые, соединяющие эти пары, либо проходят через менее чем 2C точек, либо проходят через более чем n/C точек. Если последний случай выполняется хотя бы для одной из этих пар, то мы приходим к первому заключению теоремы Бека. Следовательно, мы можем предположить, что все пары соединены прямыми, проходящими через менее чем 2C точек. Но каждая такая прямая может соединять не более пар точек. Таким образом, должно быть по крайней мере прямых, соединяющих по крайней мере две точки, и утверждение следует из выбора .
Since each such line connects together pairs of points, we thus see that at most 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 is at most
On the other hand, the total number of pairs is Thus if we choose C to be large enough, we can find at least pairs (for instance) which are not j connected for any 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 pairs are connected by lines which pass through fewer than 2C points. But each such line can connect at most pairs of points. Thus there must be at least lines connecting at least two points, and the claim follows by taking .