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

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

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

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

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

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

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

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

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

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

Теорема Бека

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

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

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

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

Существует прямая, содержащая по меньшей мере n / C точек.
Существует по меньшей мере $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 {2^{j} \choose 2}\leq {n \choose 2}$ , поскольку никакие две точки не могут лежать на двух различных прямых. Теперь используем теорему Семереди — Троттера , из которой следует, что число инциденций между P и L не превосходит $O(n^{2}/2^{2j}+n)$ . Все прямые, соединяющие j-связные точки, также находятся в L , и каждая прямая имеет по меньшей мере $2^{j}$ инциденций. Таким образом, общее число таких прямых равно $O(n^{2}/2^{3j}+n/2^{j})$ .

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

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

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

Примечания

, с. 281–297.
. Дата обращения: 10 сентября 2017. 5 октября 2016 года.
, с. 210–219.
, с. 16–21.
, с. 281–297 Theorem 5.2.
Теорема Бека получается, если положить k = n (1 − 1/ C ) и применить теорему Эрдёша — Бека.

Литература

Beck J. On the lattice property of the plane and some problems of Dirac, Motzkin, and Erdős in combinatorial geometry // Combinatorica. — 1983. — Т. 3 . — С. 281–297 . — doi : .

Kelly L. M., Moser W. O. J. // Canad. J. Math.. — 1958. — Т. 10 . — doi : .
Elekes G., Tóth C. D. Incidences of not-too-degenerate hyperplanes // Proceedings of the twenty-first annual symposium on Computational geometry. — Pisa, Italy: Annual Symposium on Computational Geometry, 2005. — ISBN 1-58113-991-8 .