Русская Википедия:Теорема Бека (геометрия)
О теореме Бека в теории категорий (однофамилец) см. статью Шаблон:Не переведено 5
Теорема Бека — это один из нескольких результатов комбинаторной геометрии, два из которых приведены ниже. Обе теоремы появились вместе с некоторыми другими важными теоремами в хорошо известной статье Джозефа БекаШаблон:Sfn. Два результата, описанные ниже касаются нижних границ числа прямых, определённых множеством точек на плоскости. (Говорят, что любая прямая, соединяющая по меньшей мере две точки множества, определяется точечным множеством.)
Теорема Эрдёша — Бека
Теорема Эрдёша — Бека — это вариант классического результата Л.М. Келли и У.О.Дж. Мозера[1] о конфигурациях n точек, из которых не более n − k коллинеарны для некоторого числа 0 < k < O(√n). Они показали, что если n достаточно велико относительно k, то конфигурация содержит по меньшей мере kn − (1/2)(3k + 2)(k − 1) прямыхШаблон:Sfn.
Элекеш и Чаба Тоз заметили, что теорема Эрдёша — Бека не распространяется легко на более высокие размерностиШаблон:Sfn. Возьмём, для примера, множество из 2n точек в R3, лежащих на двух скрещивающихся прямых. Предположим, что каждая из этих двух прямых инцидентна n точкам. Такая конфигурация охватывает лишь 2n плоскостей. Таким образом, тривиального расширения гипотезы на множества точек в Rd недостаточно для получения нужного результата.
Результат впервые высказал в качестве гипотезы Эрдёш, доказал теорему БекШаблон:Sfn.
Утверждение теоремы
Пусть S — множество из n точек на плоскости. Если никакие из более чем n − k точек не лежат на одной прямой для некоторого 0 ≤ k < n − 2, то существует Ω(nk) прямых, задаваемых точками из S.
Доказательство
Теорема Бека
Теорема Бека утверждает, что конечный набор точек на плоскости попадает в один из двух экстремальных случаев. В одном случае большая доля точек лежит на одной прямой, в другом случае требуется большое число прямых, чтобы соединить все точки.
Хотя в статье это не указывается, этот результат вытекает из теоремы Эрдёша — Бека[2]
Утверждение теоремы
Теорема утверждает, что существуют две положительные константы C и K, такие, что для любого числа n точек на плоскости верно одно из следующих утверждений:
- Существует прямая, содержащая по меньшей мере n/C точек.
- Существует по меньшей мере <math>n^2/K</math> прямых, каждая из которых содержит по меньшей мере две точки.
В оригинальной статье Бека величина C равна 100, а величина константы K не указана. Оптимальные значения C и K неизвестны.
Доказательство
Доказать теорему Бека можно следующим образом. Пусть P — множество из n точек на плоскости. Пусть j — положительное целое число. Скажем, что пара точек A и B в множестве P j-связны, если прямая, соединяющая A и B содержит от <math>2^j</math> до <math>2^{j+1}-1</math> точек множества P (включая A и B).
Из теоремы Семереди — Троттера следует, что число таких прямых равно <math>O( n^2 / 2^{3j} + n / 2^j )</math> по следующей причине. Пусть множество P состоит из n точек и множество L всех таких прямых, соединяющих пары точек множества P, которые содержат по меньшей мере <math> 2^j </math> точек множества P. Заметим, что <math> |L| \cdot {2^j \choose 2} \leq {n \choose 2}</math>, поскольку никакие две точки не могут лежать на двух различных прямых. Теперь используем теорему Семереди — Троттера, из которой следует, что число инциденций между P и L не превосходит <math>O(n^2/2^{2j} + n)</math>. Все прямые, соединяющие j-связные точки, также находятся в L, и каждая прямая имеет по меньшей мере <math>2^j</math> инциденций. Таким образом, общее число таких прямых равно <math>O(n^2/2^{3j} + n/2^j)</math>.
Поскольку каждая такая прямая соединяет <math>\Omega( 2^{2j} )</math> пар точек, мы видим, что не более <math>O( n^2 / 2^j + 2^j n )</math> пар точек может быть j-связны.
Теперь, пусть C — достаточно большая константа. Суммируя геометрическую прогрессию, мы получаем, что число j-связных пар точек для некоторого j, удовлетворяющих неравенству <math>C \leq 2^j \leq n/C</math>, не превосходит <math>O( n^2 / b\ C)</math>.
С другой стороны, общее число пар точек равно <math>\frac{n(n-1)}{2}</math>. Тогда, если мы выберем C достаточно большим, мы можем найти по меньшей мере <math>n^2 / 4 </math> пар (например), которые не j-связны для любого <math>C \leq 2^j \leq n/C</math>. Прямые, соединяющие эти точки, проходя через менее чем 2C точек или более чем n/C точек. Если последнее утверждение выполняется для хотя бы для одной пары, выполняется первое утверждение теоремы Бека. Тогда мы можем предположить, что все <math>n^2 / 4</math> пар соединены прямыми, которые проходят через менее чем 2C точек. Однако такая прямая может соединять не более <math>C(2C-1)</math> пар точек. Тогда должно быть по меньшей мере <math>n^2 / 4C(2C-1)</math> прямых, соединяющих по меньшей мере две точки, так что утверждение теоремы получается, если принять <math>K=4C(2C-1)</math>.
Примечания
Литература
- ↑ Шаблон:Cite web
- ↑ Теорема Бека получается, если положить k = n(1 − 1/C) и применить теорему Эрдёша — Бека.
