Теорема Бекса (геометрия) - Becks theorem (geometry)

О теории категорий, разработанной другим автором, см. Теорема Бека монадичности.

В дискретная геометрия, Теорема Бека - это любой из нескольких различных результатов, два из которых приведены ниже. Обе они появились, наряду с несколькими другими важными теоремами, в известной статье Йожеф Бек.^[1] Два описанных ниже результата в первую очередь относятся к нижним оценкам количества строк. определенный набором точек на плоскости. (Любая линия, содержащая не менее двух точек набора точек, называется определенный к этому моменту установлен.)

Теорема Эрдеша – Бека

В Теорема Эрдеша – Бека является вариацией классического результата Л. М. Келли и У. О. Дж. Мозер^[2] включая конфигурации п точки, из которых не более п − k коллинеарны, для некоторого 0 <k < О(√п). Они показали, что если п достаточно велико, относительно k, то конфигурация охватывает не менее кн − (1/2)(3k + 2)(k - 1) линии.^[3]

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

Этот результат был впервые высказан Erds, и доказано Беком. (Видеть Теорема 5.2. в.^[1])

Заявление

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

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

Теорема Бека

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

Хотя это не упоминается в статье Бека, этот результат вытекает из Теорема Эрдеша – Бека.^[5]

Заявление

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

1. Есть строка, содержащая не менее п/C точек.
2. Есть как минимум ${\displaystyle n^{2}/K}$ линии, каждая из которых содержит не менее двух точек.

Согласно первоначальному аргументу Бека, C 100 и K неуказанная константа; неизвестно, какие оптимальные значения C и K находятся.

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

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

От Теорема Семереди – Троттера., количество таких строк равно ${\displaystyle O(n^{2}/2^{3j}+n/2^{j})}$, следующим образом: Рассмотрим множество п из п точек, а набор L всех этих линий, натянутых на пары точек п которые содержат как минимум ${\displaystyle 2^{j}}$ точки п. Поскольку никакие две точки не могут лежать на двух разных прямых ${\displaystyle |L|\cdot {2^{j} \choose 2}\leq {n \choose 2}}$. Теперь используя Теорема Семереди – Троттера., следует, что число случаев между п и L самое большее ${\displaystyle O(n^{2}/2^{2j}+n)}$. Все линии, соединяющие j-связанный точки также лежат в L, и каждый вносит как минимум ${\displaystyle 2^{j}}$ случаи. Следовательно, общее количество таких строк равно ${\displaystyle O(n^{2}/2^{3j}+n/2^{j})}$.

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

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

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

Рекомендации

1. Бек, Йожеф (1983). «О решетчатости плоскости и некоторых проблемах Дирака, Моцкина и Эрдеша в комбинаторной геометрии». Комбинаторика. 3: 281–297. Дои:10.1007 / BF02579184. МИСТЕР  0729781.
2. "Уильям О. Дж. Мозер".
3. Келли, Л.М.; Мозер, У. О. Дж. (1958), "О количестве рядовых строк, определяемых п точки", Может. J. Math., 10: 210–219, Дои:10.4153 / CJM-1958-024-6
4. Элекес, Дьёрдь; Тот, Чаба Д. (2005). «Случаи не слишком вырожденных гиперплоскостей». Материалы двадцать первого ежегодного симпозиума по вычислительной геометрии.. Пиза, Италия: Ежегодный симпозиум по вычислительной геометрии: 16–21. ISBN  1-58113-991-8.
5. Теорема Бека может быть получена, если k = п(1 − 1/C) и применяя теорему Эрдеша – Бека.