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

О теореме Бека в теории категорий (однофамилец) см. статью Шаблон:Не переведено 5

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

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

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

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

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

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

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

Теорема Бека

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

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

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

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

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

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

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

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

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

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

Теперь, пусть C — достаточно большая константа. Суммируя геометрическую прогрессию, мы получаем, что число j-связных пар точек для некоторого j, удовлетворяющих неравенству $C\le 2^j\le n/C$, не превосходит $O(n^2/bC)$.

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

Литература

• Шаблон:Статья
• Шаблон:Книга