Гипотеза большой линии-большой клики

Синие точки имеют большие линии длиной до десяти точек, но не имеют большой клики (самые большие взаимовидимые подмножества любого подмножества выпуклой сетки имеют только четыре точки). Желтые точки образуют большую клику из десяти точек, но не имеют большой линии (самое большое коллинеарное подмножество точек в выпуклом положении имеет только две точки). Согласно гипотезе большой линии-большой клики, ни одно множество точек не может избежать как больших линий, так и больших клик.

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

Заявление и история

Точнее, гипотеза большой клики о большой линии утверждает, что для любых положительных целых чисел $k$ и $\ell$ должен существовать другой номер $n_{k,\ell }$, такой, что каждый набор $n_{k,\ell }$ точек содержит $\ell$ коллинеарные точки («большая линия»), $k$ взаимовидимые точки («большая клика») или и то, и другое.

Гипотеза о большой линии-большой клике была выдвинута Яном Кара, Аттилой Пором и Дэвидом Р. Вудом в публикации 2005 года. Это привело к большому количеству дополнительных исследований по двухточечной видимости в наборах точек.

Частичные результаты

Конечные множества точек в общем положении (не три коллинеарных) всегда содержат большую клику, поэтому гипотеза верна для $\ell \leq 3$. Кроме того, конечные множества точек, не имеющие пяти взаимно видимых точек (например, пересечения целочисленной решетки с выпуклыми множествами), всегда содержат много коллинеарных точек, поэтому гипотеза верна для $k\leq 5$.

Обобщая пример целочисленной решетки, проецируя $d$-мерная система точек решетки размером $(\ell -1)\times (\ell -1)\times \cdots =(\ell -1)^{d}$на плоскость с использованием общей линейной проекции создает набор точек без $\ell$ точки коллинеарны и нет $2^{d}+1$ взаимовидимые точки. Поэтому, когда $n_{k,\ell }$ существует, оно должно быть больше, чем $(\ell -1)^{\log _{2}(k-1)}$.

Связанные проблемы

Видимость любой системы точек можно проанализировать с помощью графа видимости точек, графа, вершинами которого являются точки и который соединяет две точки ребром всякий раз, когда соединяющий их отрезок не пересекается с другими точками. «Большие клики» гипотезы «большая линия-большая клика» — это клики в графе видимости. Однако, хотя система точек, которая полностью коллинеарна, может быть охарактеризована наличием двудольного графа видимости, эта характеристика не распространяется на подмножества точек: подмножество может иметь двудольный индуцированный подграф графа видимости, не будучи коллинеарным.

Согласно решению проблемы счастливого конца , каждое подмножество точек, в которых нет трех в строке, включает в себя большое подмножество, образующее вершины выпуклого многоугольника . В более общем смысле, используя те же методы, можно доказать, что каждый набор из достаточного числа точек либо включает в себя $\ell$ коллинеарные точки или $k$ точки в выпуклом положении . Однако некоторые из этих пар выпуклых точек могут быть заблокированы от видимости точками внутри выпуклого многоугольника, который они образуют.

Другой связанный с этим вопрос заключается в том, содержат ли точки в общем положении (или без линий, число которых превышает определенное заданное количество точек) вершины пустого выпуклого многоугольника или отверстия . Это многоугольник, вершины которого принадлежат множеству точек, но не имеет других точек пересечения множества точек со своей выпуклой оболочкой. Если дыра заданного размера существует, все ее вершины обязательно видят друг друга. Все достаточно большие множества точек общего положения содержат пять вершин, образующих пустой пятиугольник. или шестиугольник , но существуют сколь угодно большие множества общего положения, в которых нет пустых семиугольников .

Усиление гипотезы о большой клике большой линии требует, чтобы большая клика была «видимым островом», набором взаимно видимых точек, которые формируются из данного большего набора точек путем пересечения его с выпуклым множеством. Однако эта усиленная версия неверна: если набор точек в общем положении не имеет пустого семиугольника, то замена каждой из его точек близко расположенной тройкой коллинеарных точек дает набор точек без четырех на линии и без видимых островов. 13 и более баллов.

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