Теорема Бека (геометрия)

О теореме Бека в теории категорий (однофамилец) см. статью Теорема Бека о монадизируемости

Теорема Бека — это один из нескольких результатов комбинаторной геометрии, два из которых приведены ниже. Обе теоремы появились вместе с некоторыми другими важными теоремами в хорошо известной статье Джозефа Бека. Два результата, описанные ниже касаются нижних границ числа прямых, определённых множеством точек на плоскости. (Говорят, что любая прямая, соединяющая по меньшей мере две точки множества, определяется точечным множеством.)

Теорема Эрдёша — Бека

Теорема Эрдёша — Бека — это вариант классического результата Л.М. Келли и У.О.Дж. Мозера о конфигурациях n точек, из которых не более n − k коллинеарны для некоторого числа 0 < k < O(√n). Они показали, что если n достаточно велико относительно k, то конфигурация содержит по меньшей мере kn − (1/2)(3k + 2)(k − 1) прямых.

Элекеш и Чаба Тоз заметили, что теорема Эрдёша — Бека не распространяется легко на более высокие размерности. Возьмём, для примера, множество из 2n точек в R³, лежащих на двух скрещивающихся прямых. Предположим, что каждая из этих двух прямых инцидентна n точкам. Такая конфигурация охватывает лишь 2n плоскостей. Таким образом, тривиального расширения гипотезы на множества точек в R^d недостаточно для получения нужного результата.

Результат впервые высказал в качестве гипотезы Эрдёш, доказал теорему Бек.

Утверждение теоремы

Пусть S — множество из n точек на плоскости. Если никакие из более чем n − k точек не лежат на одной прямой для некоторого 0 ≤ k < n − 2, то существует Ω(nk) прямых, задаваемых точками из S.

Теорема Бека

Теорема Бека утверждает, что конечный набор точек на плоскости попадает в один из двух экстремальных случаев. В одном случае большая доля точек лежит на одной прямой, в другом случае требуется большое число прямых, чтобы соединить все точки.

Хотя в статье это не указывается, этот результат вытекает из теоремы Эрдёша — Бека

Утверждение теоремы

Теорема утверждает, что существуют две положительные константы C и K, такие, что для любого числа n точек на плоскости верно одно из следующих утверждений:

1. Существует прямая, содержащая по меньшей мере n/C точек.
2. Существует по меньшей мере [math]\displaystyle{ n^2/K }[/math] прямых, каждая из которых содержит по меньшей мере две точки.

В оригинальной статье Бека величина C равна 100, а величина константы K не указана. Оптимальные значения C и K неизвестны.

Доказательство

Доказать теорему Бека можно следующим образом. Пусть P — множество из n точек на плоскости. Пусть j — положительное целое число. Скажем, что пара точек A и B в множестве P j-связны, если прямая, соединяющая A и B содержит от [math]\displaystyle{ 2^j }[/math] до [math]\displaystyle{ 2^{j+1}-1 }[/math] точек множества P (включая A и B).

Из теоремы Семереди — Троттера следует, что число таких прямых равно [math]\displaystyle{ O( n^2 / 2^{3j} + n / 2^j ) }[/math] по следующей причине. Пусть множество P состоит из n точек и множество L всех таких прямых, соединяющих пары точек множества P, которые содержат по меньшей мере [math]\displaystyle{ 2^j }[/math] точек множества P. Заметим, что [math]\displaystyle{ |L| \cdot {2^j \choose 2} \leq {n \choose 2} }[/math], поскольку никакие две точки не могут лежать на двух различных прямых. Теперь используем теорему Семереди — Троттера, из которой следует, что число инциденций между P и L не превосходит [math]\displaystyle{ O(n^2/2^{2j} + n) }[/math]. Все прямые, соединяющие j-связные точки, также находятся в L, и каждая прямая имеет по меньшей мере [math]\displaystyle{ 2^j }[/math] инциденций. Таким образом, общее число таких прямых равно [math]\displaystyle{ O(n^2/2^{3j} + n/2^j) }[/math].

Поскольку каждая такая прямая соединяет [math]\displaystyle{ \Omega( 2^{2j} ) }[/math] пар точек, мы видим, что не более [math]\displaystyle{ O( n^2 / 2^j + 2^j n ) }[/math] пар точек может быть j-связны.

Теперь, пусть C — достаточно большая константа. Суммируя геометрическую прогрессию, мы получаем, что число j-связных пар точек для некоторого j, удовлетворяющих неравенству [math]\displaystyle{ C \leq 2^j \leq n/C }[/math], не превосходит [math]\displaystyle{ O( n^2 / b\ C) }[/math].

С другой стороны, общее число пар точек равно [math]\displaystyle{ \frac{n(n-1)}{2} }[/math]. Тогда, если мы выберем C достаточно большим, мы можем найти по меньшей мере [math]\displaystyle{ n^2 / 4 }[/math] пар (например), которые не j-связны для любого [math]\displaystyle{ C \leq 2^j \leq n/C }[/math]. Прямые, соединяющие эти точки, проходя через менее чем 2C точек или более чем n/C точек. Если последнее утверждение выполняется для хотя бы для одной пары, выполняется первое утверждение теоремы Бека. Тогда мы можем предположить, что все [math]\displaystyle{ n^2 / 4 }[/math] пар соединены прямыми, которые проходят через менее чем 2C точек. Однако такая прямая может соединять не более [math]\displaystyle{ C(2C-1) }[/math] пар точек. Тогда должно быть по меньшей мере [math]\displaystyle{ n^2 / 4C(2C-1) }[/math] прямых, соединяющих по меньшей мере две точки, так что утверждение теоремы получается, если принять [math]\displaystyle{ K=4C(2C-1) }[/math].