Нет проблемы с тремя рядами

Задача геометрии в точках сетки

Набор из 20 точек в сетке 10 × 10, без трех точек в линии.

Проблема отсутствия трех прямых в дискретной геометрии спрашивает, сколько точек можно разместить в сетке так, чтобы никакие три точки не лежали на одной прямой. Проблема касается линий всех уклонов, а не только тех, которые совпадают с сеткой. Он был введен Генри Дьюдени в 1900 году. Брасс, Мозер и Пах называют его «одним из старейших и наиболее широко изученных геометрических вопросов, касающихся точек решетки». ^[1] ${\displaystyle n\times n}$

Можно разместить максимум точек, поскольку точки в сетке будут включать в себя ряд из трех или более точек по принципу ячейки . Хотя проблему можно решить с помощью точек для каждого до , предполагается , что в сетках большого размера можно разместить меньше точек. Известные методы позволяют линейно размещать множество точек в сетках произвольного размера, но лучшие из этих методов размещают немного меньше точек, а не 0,000 . ${\displaystyle 2n}$ ${\displaystyle 2n+1}$ ${\displaystyle 2n}$ ${\displaystyle n}$ ${\displaystyle 46}$ ${\displaystyle 2n}$ ${\displaystyle 3n/2}$ ${\displaystyle 2n}$

Также были изучены несколько связанных проблем поиска точек, в которых нет трех в строке, среди других наборов точек, отличных от сетки. Хотя проблема «нет трех в ряд» возникла в развлекательной математике , она находит применение в рисовании графиков и в задаче о треугольнике Гейльбронна .

Маленькие экземпляры

Решение головоломки Дьюдени о том, как разместить 16 пешек на шахматной доске так, чтобы никакие три пешки не лежали на одной линии, а пешки находились на полях d4 и e5.

Задача была впервые поставлена ​​Генри Дюдени в 1900 году как головоломка из развлекательной математики, сформулированная в виде размещения 16 пешек шахматной доски на доске так, чтобы никакие три не оказались в линии. ^[2] Это в точности проблема «нет трех рядов» для случая . ^[3] ${\displaystyle n=8}$ В более поздней версии головоломки Дьюдени модифицировал задачу, сделав ее решение уникальным, задав решение, в котором две пешки находятся на полях d4 и e5 и атакуют друг друга в центре доски. ^[4]

Многие авторы опубликовали решения этой проблемы для малых значений [ ^5] , ${\displaystyle n}$ и к 1998 году стало известно, что точки можно размещать на сетке без трех в строке для всех значений до 46 и некоторых больших значений. ^[6] Число решений с точками для малых значений , начиная с , равно ${\displaystyle 2n}$ ${\displaystyle n\times n}$ ${\displaystyle n}$ ${\displaystyle 2n}$ ${\displaystyle n}$ ${\displaystyle n=2}$

1, 2, 11, 32, 50, 132, 380, 368, 1135, 1120, 4348, 3622, 10568, ... (последовательность A000755 в OEIS ).

Числа классов эквивалентности решений с точками при отражениях и поворотах равны ${\displaystyle 2n}$

1, 1, 4, 5, 11, 22, 57, 51, 156, 158, 566, 499, 1366, ... (последовательность A000769 в OEIS ). ^[3]

Верхняя и нижняя границы

Точное количество точек, которые можно разместить в зависимости от , неизвестно ${\displaystyle n}$ . Однако как доказанные, так и предполагаемые границы ограничивают это число диапазоном, пропорциональным . ${\displaystyle n}$

Общие способы размещения

Неоптимальное размещение точек в сетке по методу Эрдёша. Наибольшее простое число, меньшее размера сетки, равно ; решение помещает точки в координаты mod для . Например, включено, потому что ( мод ). ${\displaystyle 11}$ ${\displaystyle 12\times 12}$ ${\displaystyle p}$ ${\displaystyle p=11}$ ${\displaystyle (i,i^{2}}$ ${\displaystyle p)}$ ${\displaystyle i=0,1,\dots p-1}$ ${\displaystyle (4,5)}$ ${\displaystyle 4^{2}=16\cong 5}$ ${\displaystyle }$ ${\displaystyle 11}$

Решение Пола Эрдеша , опубликованное Ротом (1951), основано на наблюдении, что, когда является простым числом , набор точек сетки mod для , не содержит трех коллинеарных точек. Когда не является простым, можно выполнить это построение для сетки, содержащейся в сетке, где — наибольшее простое число, не превышающее . Поскольку разрыв между последовательными простыми числами намного меньше, чем сами простые числа, он всегда будет близок к , поэтому этот метод можно использовать для размещения точек в сетке без трех точек, лежащих на одной прямой. ^[7] ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle (i,i^{2}}$ ${\displaystyle n)}$ ${\displaystyle 0\leq i<n}$ ${\displaystyle n}$ ${\displaystyle p\times p}$ ${\displaystyle n\times n}$ ${\displaystyle p}$ ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle n}$ ${\displaystyle n-o(n)}$ ${\displaystyle n\times n}$

Впоследствии граница Эрдеша была улучшена: Hall et al. (1975) показывают, что, когда простое число, можно получить решение с точками, помещая точки в несколько копий гиперболы ( mod ), где можно выбирать произвольно, если оно не равно нулю . Опять же, для произвольного можно выполнить эту конструкцию для простого числа рядом , чтобы получить решение с точками. ^[8] ${\displaystyle n/2}$ ${\displaystyle 3(n-2)/2}$ ${\displaystyle xy=k}$ ${\displaystyle n/2}$ ${\displaystyle k}$ ${\displaystyle n/2}$ ${\displaystyle n}$ ${\displaystyle n/2}$ ${\displaystyle {\tfrac {3}{2}}n-o(n)}$

Верхняя граница

Большинство точек могут быть размещены в сетке любого размера . Ведь если разместить больше точек, то по принципу «ячейки» около трех из них будут лежать на одной горизонтальной линии сетки. Для эта тривиальная оценка, как известно, является точной. ^[3] ${\displaystyle 2n}$ ${\displaystyle n}$ ${\displaystyle n\leq 46}$

Предполагаемые границы

Хотя на маленьких сетках можно разместить ровно столько точек, Гай и Келли (1968) предположили, что для больших сеток существует значительно меньшая верхняя граница количества точек, которые можно разместить. Точнее, они предположили, что количество точек, которые можно разместить, не превышает сублинейной величины , при этом ^[9] ${\displaystyle 2n}$ ${\displaystyle cn}$

$${\displaystyle c={\sqrt[{3}]{\frac {2\pi ^{2}}{3}}}\approx 1.874.}$$

^[10] ${\displaystyle cn}$

$${\displaystyle c={\frac {\pi }{\sqrt {3}}}\approx 1.814.}$$

Приложения

Решения проблемы отсутствия трех строк можно использовать, чтобы избежать определенных видов вырождений при построении графов . Проблема, к которой они применяются, включает в себя размещение вершин данного графа в целочисленных координатах на плоскости и рисование ребер графа в виде отрезков прямых линий . Для некоторых графов, таких как граф полезности , пересечения между парами ребер неизбежны, но все равно следует избегать размещений, которые заставляют вершину лежать на ребре, проходящем через две другие вершины. Когда вершины расположены без трех в строке, такое проблемное размещение не может возникнуть, поскольку вся линия, проходящая через любые две вершины, а не только отрезок прямой, свободна от других вершин. ^[11] Тот факт, что задача «нет трех в ряд» имеет решение с линейным числом точек, можно перевести в термины рисования графов, означая, что каждый граф, даже полный граф , может быть нарисован без нежелательных инцидентов вершин и ребер, используя сетка, площадь которой квадратична по количеству вершин, и что для полных графов такое рисование с площадью меньше квадратичной невозможно. Полные графы также требуют линейного количества цветов при любой раскраске графа , но другие графы, которые можно раскрасить меньшим количеством цветов, также можно нарисовать на сетках меньшего размера: если граф имеет вершины и раскраска графа цветами , его можно нарисовать в сетка с площадью, пропорциональной . Рисование полного графа без трех строк является частным случаем этого результата с . ^[12] ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle nk}$ ${\displaystyle k=n}$

Проблема отсутствия трех рядов также имеет приложения к другой задаче дискретной геометрии — проблеме треугольника Гейльбронна . В этой задаче необходимо размещать точки в любом месте единичного квадрата, не ограничиваясь сеткой. Целью размещения является избежание треугольников малой площади, а точнее, максимизация площади наименьшего треугольника, образованного тремя вершинами. Например, размещение с тремя точками на линии было бы очень плохим по этому критерию, потому что эти три точки образовывали бы вырожденный треугольник с нулевой площадью. С другой стороны , если точки можно разместить на сетке с длиной стороны в пределах единичного квадрата, без трех в линии, то по теореме Пика каждый треугольник будет иметь площадь не менее половины квадрата сетки. Таким образом, решение задачи «нет трех в ряд» и последующее уменьшение целочисленной сетки до размера единичного квадрата приводит к решению проблемы треугольника Гейльбронна, где наименьший треугольник имеет площадь . Это приложение послужило для Пола Эрдеша мотивацией найти решение проблемы отсутствия трех рядов. ^[13] Она оставалась лучшей нижней границей площади, известной для задачи треугольника Гейльбронна с 1951 по 1982 год, когда она была улучшена с помощью логарифмического коэффициента с использованием конструкции, которая не была основана на задаче отсутствия трех рядов. ^[14] ${\displaystyle n}$ ${\displaystyle \varepsilon }$ ${\displaystyle \varepsilon ^{2}/2}$ ${\displaystyle \Omega (1/n^{2})}$

Обобщения и вариации

Подмножества общего положения

В вычислительной геометрии конечные множества точек, в которых нет трех на прямой, называются находящимися в общем положении . В этой терминологии задача «нет трех рядов» ищет наибольшее подмножество сетки, находящееся в общем положении, но исследователи также рассматривали проблему поиска наибольшего подмножества общего положения других наборов точек, не являющихся сеткой. Найти это подмножество для определенных входных наборов NP-трудно , и трудно аппроксимировать его размер с точностью до постоянного коэффициента; Этот результат сложности аппроксимации суммируется, говоря, что проблема APX-трудна . Если наибольшее подмножество имеет размер , ${\displaystyle k}$ решение с непостоянным коэффициентом аппроксимации может быть получено с помощью жадного алгоритма , который просто выбирает точки по одной до тех пор, пока все оставшиеся точки не лягут на линии, проходящие через пары выбранных точек. ^[15] ${\displaystyle O({\sqrt {k}})}$

Можно получить более детальное представление о времени работы алгоритмов поиска точного оптимального решения, используя параметризованную сложность , при которой алгоритмы анализируются не только с точки зрения размера входных данных, но и с точки зрения других входных параметров. В этом случае для входных данных, наибольшее подмножество общего положения которых имеет размер , ${\displaystyle k}$ его можно найти за промежуток времени, который является экспоненциальной функцией от умножения на многочлен входного размера , при этом показатель степени полинома не зависит от . Задачи с таким ограничением по времени называются управляемыми с фиксированными параметрами . ^[16] ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle k}$

Для наборов точек , имеющих не более точек на линию, при , существуют подмножества общего положения размером, почти пропорциональным . Пример сетки показывает, что эту оценку невозможно существенно улучшить. ^[17] Доказательство существования этих больших подмножеств общего положения может быть преобразовано в полиномиальный алгоритм для поиска подмножества общего положения , размер которого соответствует границе существования, с использованием алгоритмического метода, известного как сжатие энтропии . ^[15] ${\displaystyle S}$ ${\textstyle \ell }$ ${\textstyle \ell =O({\sqrt {|S|}})}$ ${\textstyle \ell =O({\sqrt {|S|}})}$ ${\displaystyle S}$

Жадное размещение

Повторяя предложение Адены, Холтона и Келли (1974), Мартин Гарднер попросил указать наименьшее подмножество сетки , которое нельзя расширить: в нем нет трех точек на линии, но в каждом правильном надмножестве есть три точки на линии. Аналогично, это наименьший набор, который может быть создан жадным алгоритмом , который пытается решить проблему отсутствия трех рядов, размещая точки по одной, пока не застрянет. ^[3] Если рассматривать только осепараллельные и диагональные линии, то в каждом таком множестве есть как минимум точки. ^[18] Однако о версии задачи, в которой учитываются все линии, известно меньше: каждое жадное размещение включает в себя как минимум точки, прежде чем застревать, но ничего лучше, чем тривиальная верхняя граница, неизвестно. ^[19] ${\displaystyle n\times n}$ ${\displaystyle n-1}$ ${\displaystyle \Omega (n^{2/3})}$ ${\displaystyle 2n}$

Высшие измерения

Неколлинеарные наборы точек в трехмерной сетке были рассмотрены Пором и Вудом (2007). Они доказали, что максимальное количество точек в сетке, в которых нет трех точек, лежащих на одной прямой, равно . Подобно двумерной конструкции Эрдёша, это можно сделать, используя точки mod , где — простое число, конгруэнтное 3 mod 4 . ^[20] Точно так же, как исходную задачу «нет трех в ряд» можно использовать для рисования двумерных графиков, можно использовать это трехмерное решение для рисования графиков в трехмерной сетке. Здесь условие неколлинеарности означает, что вершина не должна лежать на несмежном ребре, но нормально работать с более строгим требованием, чтобы никакие два ребра не пересекались. ^[21] ${\displaystyle n\times n\times n}$ ${\displaystyle \Theta (n^{2})}$ ${\displaystyle (x,y,x^{2}+y^{2}}$ ${\displaystyle p)}$ ${\displaystyle p}$

В гораздо более высоких измерениях наборы точек сетки без трех в строке, полученные путем выбора точек рядом с гиперсферой , использовались для поиска больших наборов Салема – Спенсера , наборов целых чисел без трех, образующих арифметическую прогрессию. ^[22] Однако использовать ту же идею выбора точек рядом с кругом в двух измерениях не очень хорошо: этот метод находит точки, образующие выпуклые многоугольники, которые удовлетворяют требованию отсутствия трех в линии, но слишком малы. Самые большие выпуклые многоугольники с вершинами в сетке имеют только вершины. ^[23] Проблема с ограниченным набором связана с проблемой, аналогичной проблеме отсутствия трех строк в пространствах, которые являются многомерными и основаны на векторных пространствах над конечными полями , а не над целыми числами. ^[24] ${\displaystyle n\times n}$ ${\displaystyle O(n^{2/3})}$

Другое обобщение на более высокие измерения — найти как можно больше точек в трехмерной сетке, чтобы никакие четыре из них не находились в одной плоскости. Эта последовательность начинается с 5, 8, 10, 13, 16,... OEIS : A280537 для N = 2, 3, 4 и т. д. ${\displaystyle N\times N\times N}$

Тор

Другой вариант проблемы включает преобразование сетки в дискретный тор с использованием периодических граничных условий , в которых левая сторона тора соединяется с правой стороной, а верхняя сторона соединяется с нижней стороной. Это приводит к тому, что наклонные линии, проходящие через сетку, соединяются в более длинные линии через большее количество точек и, следовательно, затрудняют выбор точек, имеющих не более двух из каждой линии. Эти расширенные линии также можно интерпретировать как нормальные линии, проходящие через бесконечную сетку в евклидовой плоскости, взятую по модулю размеров тора. Для тора, основанного на сетке, максимальное количество точек, которые можно выбрать без трех в строке, не превышает . ^[25] Когда обе размерности равны и просты, невозможно разместить ровно одну точку в каждой строке и столбце, не образуя линейного числа коллинеарных троек. ^[26] Также изучались торические версии задачи более высокой размерности. ^[27] ${\displaystyle m\times n}$ ${\displaystyle 2\gcd(m,n)}$

Смотрите также

• Головоломка «Восемь ферзей» о размещении точек на сетке, в которых не должно быть двух в одной строке, столбце или диагонали.

Примечания

1. Брасс, Мозер и Пах 2005.
2. The Weekly Dispatch , 29 апреля и 13 мая 1900 г., цитируется Кнутом 2008.
3. Гарднер 1976.
4. Дудени 1917.
5. Крэггс и Хьюз-Джонс, 1976; Клёве 1978, 1979; Андерсон 1979; Харборт, Эртель и Преллберг, 1989; Фламменкамп 1992, 1998.
6. Фламменкамп 1992, 1998.
7. Эрдеш не опубликовал это наблюдение; оно появляется у Рота 1951 года.
8. Холл и др. 1975.
9. Гай и Келли 1968.
10. Как сообщает Пегг 2005. Открытие этой ошибки было приписано Пеггом Габору Эллманну.
11. Брасс и др. 2007.
12. Вуд 2005.
13. Рот 1951.
14. Комлос, Пинц и Семереди 1982.
15. Эппштейн 2018.
16. Фрёзе и др. 2017 год; Эппштейн 2018
17. Пейн и Вуд 2013.
18. Купер и др. 2014.
19. Айххольцер, Эппштейн и Хайнцль (2023).
20. Пор и Вуд 2007.
21. Пач, Тиле и Тот 1998; Дуймович, Морин и Вуд, 2005 г.; Ди Джакомо, Лиотта и Мейер, 2005 г.
22. Элкин 2011.
23. Ярник 1926.
24. Кларрайх 2016.
25. Мисиак и др. 2016.
26. Купер и Солимоси 2005.
27. Ку и Вонг 2018.

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

• Адена, Майкл А.; Холтон, Дерек А.; Келли, Патрик А. (1974). «Некоторые мысли о проблеме отсутствия трех рядов». В Холтоне, Дерек А. (ред.). Комбинаторная математика: материалы второй австралийской конференции (Мельбурнский университет, 1973) . Конспект лекций по математике. Том. 403. стр. 6–17. дои : 10.1007/BFb0057371. МР  0349396.
• Айххольцер, Освин; Эппштейн, Дэвид ; Хайнцль, Ева-Мария (январь 2023 г.). «Геометрические доминирующие множества - минимальная версия проблемы трех рядов». Вычислительная геометрия . Эльзевир. 108 : 101913. arXiv : 2203.13170 . дои : 10.1016/j.comgeo.2022.101913 . S2CID  249687906.
• Андерсон, Дэвид Брент (1979). «Обновленная информация о проблеме отсутствия трех рядов». Журнал комбинаторной теории . Серия А. 27 (3): 365–366. дои : 10.1016/0097-3165(79)90025-6 . МР  0555806.
• Брасс, Питер; Сенек, Эовин; Дункан, Кристиан А.; Эфрат, Алон; Эртен, Чесим; Исмаилеску, Дэн П.; Кобуров, Стивен Г.; Любив, Анна ; Митчелл, Джозеф С.Б. (2007). «Об одновременных вложениях планарных графов». Вычислительная геометрия . 36 (2): 117–130. дои : 10.1016/j.comgeo.2006.05.006 . МР  2278011.
• Брасс, Питер; Мозер, Уильям; Пах, Янош (2005). «Раздел 10.1: Упаковка точек решетки в подпространствах». Проблемы исследования дискретной геометрии . Спрингер, Нью-Йорк. стр. 417–421. ISBN 978-0-387-29929-7. МР  2163782.
• Купер, Алек С.; Пихурко Олег; Шмитт, Джон Р.; Уоррингтон, Грегори С. (2014). «Задача Мартина Гарднера о минимуме № 3 в ряд». Американский математический ежемесячник . 121 (3): 213–221. arXiv : 1206.5350 . doi : 10.4169/amer.math.monthly.121.03.213. JSTOR  10.4169/amer.math.monthly.121.03.213. S2CID  887220.
• Купер, Джошуа Н.; Солимоси, Йожеф (2005). «Коллинеарные точки в перестановках» (PDF) . Анналы комбинаторики . 9 (2): 169–175. arXiv : math/0408396 . дои : 10.1007/s00026-005-0248-4. MR  2153735. S2CID  11035679.
• Крэггс, Д.; Хьюз-Джонс, Р. (1976). «О проблеме отсутствия трех рядов». Журнал комбинаторной теории . Серия А. 20 (3): 363–364. дои : 10.1016/0097-3165(76)90030-3 . МР  0406804.
• Дудени, Генри (1917). «317. Загадка с пешками». Забавы по математике . Эдинбург: Нельсон. п. 94.Решение, с. 222. Первоначально опубликовано в «Лондон Трибьюн» 7 ноября 1906 года.
• Ди Джакомо, Эмилио; Лиотта, Джузеппе; Мейер, Хенк (2005). «Расчет прямолинейных трехмерных сеточных рисунков графиков в линейном объеме». Вычислительная геометрия: теория и приложения . 32 (1): 26–58. дои : 10.1016/j.comgeo.2004.11.003.
• Дуймович, Вида ; Морен, Пэт ; Вуд, Дэвид Р. (2005). «Компоновка графов с ограниченной шириной дерева». SIAM Journal по вычислительной технике . 34 (3): 553–579. arXiv : cs/0406024 . дои : 10.1137/S0097539702416141. S2CID  3264071.
• Элкин, Майкл (2011). «Улучшенная конструкция наборов без прогрессирования». Израильский математический журнал . 184 : 93–128. arXiv : 0801.4310 . дои : 10.1007/s11856-011-0061-1 . МР  2823971.
• Эппштейн, Дэвид (2018). «Глава 9: Общее положение». Запрещенные конфигурации в дискретной геометрии . Издательство Кембриджского университета. стр. 72–86.
• Фламменкамп, Ахим (1992). «Прогресс в решении проблемы отсутствия трех рядов». Журнал комбинаторной теории . Серия А. 60 (2): 305–311. дои : 10.1016/0097-3165(92)90012-J .
• Фламменкамп, Ахим (1998). «Прогресс в решении проблемы отсутствия трех рядов, II». Журнал комбинаторной теории . Серия А. 81 (1): 108–113. дои : 10.1006/jcta.1997.2829 .
• Фрёзе, Винсент; Кандж, Ияд; Нихтерляйн, Андре; Нидермайер, Рольф (2017). «Нахождение точек в общем положении». Международный журнал вычислительной геометрии и приложений . 27 (4): 277–296. arXiv : 1508.01097 . дои : 10.1142/S021819591750008X. МР  3766097. S2CID  47260245.
• Гарднер, Мартин (октябрь 1976 г.). «Комбинаторные задачи, некоторые старые, некоторые новые и все новые, атакованные компьютером». Математические игры. Научный американец . Том. 235, нет. 4. С. 131–137. JSTOR  24950467.
• Гай, РК ; Келли, Пенсильвания (1968). «Проблема отсутствия трех рядов». Канадский математический бюллетень . 11 (4): 527–531. дои : 10.4153/CMB-1968-062-3 . МР  0238765.
• Холл, РР; Джексон, Техас; Садбери, А.; Уайлд, К. (1975). «Некоторые успехи в решении проблемы отсутствия трех рядов». Журнал комбинаторной теории . Серия А. 18 (3): 336–341. дои : 10.1016/0097-3165(75)90043-6 .
• Харборт, Хейко ; Эртель, Филипп; Прелльберг, Томас (1989). «Нет-три в ряд для семнадцати и девятнадцати». Материалы совещания «Комбинаторик» в Обервольфахе (1986). Дискретная математика . 73 (1–2): 89–90. дои : 10.1016/0012-365X(88)90135-5 . МР  0974815.
• Ярник, Войтех (1926). «Über die Gitterpunkte auf konvexen Kurven» [О точках сетки на выпуклых кривых]. Mathematische Zeitschrift (на немецком языке). 24 (1): 500–518. дои : 10.1007/BF01216795. MR  1544776. S2CID  117747514.
• Кларрайх, Эрика (31 мая 2016 г.). «Простое доказательство игры ошеломляет математиков». Кванта .
• Клёве, Торлейв (1978). «О проблеме отсутствия трех рядов. II». Журнал комбинаторной теории . Серия А. 24 (1): 126–127. дои : 10.1016/0097-3165(78)90053-5 . МР  0462998.
• Клёве, Торлейв (1979). «О проблеме отсутствия трех рядов. III». Журнал комбинаторной теории . Серия А. 26 (1): 82–83. дои : 10.1016/0097-3165(79)90055-4. МР  0525088.
• Комлос, Дж .; Пинц, Дж .; Семереди, Э. (1982). «Нижняя оценка проблемы Хейльбронна». Журнал Лондонского математического общества . 25 (1): 13–24. дои : 10.1112/jlms/s2-25.1.13. МР  0645860.
• Кнут, Дональд Э. (2008). «Ответ к упражнению 242». Искусство компьютерного программирования, глава 1b: Черновой вариант раздела 7.1.4: Двоичные диаграммы решений . п. 130.
• Ку, Ченг Йи; Вонг, Кок Бин (2018). «О задаче отсутствия трех прямых на m -мерном торе». Графы и комбинаторика . 34 (2): 355–364. дои : 10.1007/s00373-018-1878-8. МР  3774457. S2CID  3935268.
• Мисяк, Александр; Стемпень, Зофья; Шимашкевич, Алисия; Шимашкевич, Лючан; Звержовский, Мацей (2016). «Заметка о проблеме отсутствия трех прямых на торе». Дискретная математика . 339 (1): 217–221. arXiv : 1406.6713 . doi :10.1016/j.disc.2015.08.006. МР  3404483. S2CID  40210322.
• Пах, Янош ; Тиле, Торстен; Тот, Геза (1998). «Трёхмерные сеточные рисунки графиков». Рисование графика, 5-й Межд. Симп., ГД '97 . Конспекты лекций по информатике. Том. 1353. Шпрингер-Верлаг. стр. 47–51. дои : 10.1007/3-540-63938-1_49 .
• Пейн, Майкл С.; Вуд, Дэвид Р. (2013). «О задаче выбора подмножества общего положения». SIAM Journal по дискретной математике . 27 (4): 1727–1733. arXiv : 1208.5289 . дои : 10.1137/120897493. MR  3111653. S2CID  7164626.
• Пегг, Эд младший (11 апреля 2005 г.). «Задачи на шахматной доске». Математические игры . Математическая ассоциация Америки . Проверено 25 июня 2012 г.
• Пор, Аттила; Вуд, Дэвид Р. (2007). «Нет-три в ряд-в-3D». Алгоритмика . 47 (4): 481. doi :10.1007/s00453-006-0158-9. S2CID  209841346.
• Рот, К.Ф. (1951). «О проблеме Гейльбронна». Журнал Лондонского математического общества . 26 (3): 198–204. doi : 10.1112/jlms/s1-26.3.198.
• Вуд, Дэвид Р. (2005). «Сетчатые рисунки k-раскрашиваемых графов». Вычислительная геометрия: теория и приложения . 30 (1): 25–28. дои : 10.1016/j.comgeo.2004.06.001 .

Внешние ссылки

• Фламменкамп, Ахим. «Проблема трех рядов».
• Вайсштейн, Эрик В. «Задача «нет трех в ряд». Математический мир .