Топологический граф

Граф с нечетным числом пересечений 13 и парным числом пересечений 15 ^[1]

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

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

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

Экстремальные задачи для топологических графов

Фундаментальной проблемой в теории экстремальных графов является следующая: каково максимальное число ребер, которое может иметь граф из n вершин, если он не содержит подграфов, принадлежащих заданному классу запрещенных подграфов ? Прототипом таких результатов является теорема Турана , где имеется один запрещенный подграф: полный граф с k вершинами ( k фиксировано). Аналогичные вопросы можно поставить для топологических и геометрических графов, с той разницей, что теперь запрещены определенные геометрические подконфигурации .

Исторически первый пример такой теоремы принадлежит Полу Эрдёшу , который обобщил результат Хайнца Хопфа и Эрики Паннвиц . ^[2] Он доказал, что максимальное количество ребер, которое может иметь геометрический граф с n  > 2 вершинами, не содержащий двух непересекающихся ребер (которые даже не могут иметь общую конечную точку), равно n . Джон Конвей предположил, что это утверждение можно обобщить на простые топологические графы. Топологический граф называется «простым», если любая пара его ребер имеет общую не более чем одну точку, которая является либо конечной точкой, либо общей внутренней точкой, в которой два ребра должным образом пересекаются. Гипотеза Конвея о трэкле теперь может быть переформулирована следующим образом: простой топологический граф с n  > 2 вершинами и без двух непересекающихся ребер имеет не более n ребер.

Первая линейная верхняя граница числа ребер такого графа была установлена ​​Ловасом и др. ^[3] Лучшая известная верхняя граница, 1,3984 n , была доказана Фулеком и Пахом . ^[4] Помимо геометрических графов, гипотеза Конвея о трекле, как известно, верна для x -монотонных топологических графов. ^[5] Топологический граф называется x -монотонным , если каждая вертикальная линия пересекает каждое ребро не более чем в одной точке.

Алон и Эрдёш ^[6] инициировали исследование обобщения вышеуказанного вопроса на случай, когда запрещенная конфигурация состоит из k непересекающихся ребер ( k  > 2). Они доказали, что количество ребер геометрического графа из n вершин, не содержащего 3 непересекающихся ребер, равно O ( n ). Оптимальная граница примерно 2,5n была определена Черны. ^[7] Для больших значений k первая линейная верхняя граница, , была установлена ​​Пахом и Тёрёчиком. ^[8] Она была улучшена Тотом до . ^[9] Для количества ребер в простом топологическом графе без k непересекающихся ребер известна только верхняя граница. ^[10] Это означает, что каждый полный простой топологический граф с n вершинами имеет по крайней мере попарно непересекающиеся ребра, что было улучшено до Руисом-Варгасом. ^{[11] [12]} Возможно, что эту нижнюю границу можно улучшить до cn , где c  > 0 — константа. ${\displaystyle O(k^{4}n)}$ ${\displaystyle O(k^{2}n)}$ ${\displaystyle O(n\log ^{4k-8}n)}$ ${\displaystyle c{\frac {\log n}{\log \log n}}}$ ${\displaystyle cn^{{\frac {1}{2}}-\epsilon }}$

Квазипланарные графы

Общая внутренняя точка двух ребер, в которой первое ребро проходит от одной стороны второго ребра к другой, называется перекрестком . Два ребра топологического графа пересекают друг друга, если они определяют перекресток. Для любого целого числа k  > 1 топологический или геометрический граф называется k-квазипланарным, если он не имеет k попарно пересекающихся ребер. Используя эту терминологию, если топологический граф является 2-квазипланарным, то он является планарным графом . Из полиэдральной формулы Эйлера следует , что любой планарный граф с n  > 2 вершинами имеет не более 3 n  − 6 ребер. Следовательно, любой 2-квазипланарный граф с n  > 2 вершинами имеет не более 3 n  − 6 ребер.

^{Пач и др. [13]} предположили , что любой k -квазипланарный топологический граф с n вершинами имеет не более c ( k ) n ребер, где c ( k ) — константа, зависящая только от k . Известно, что эта гипотеза верна для k  = 3 ^{[14] [15]} и k  = 4. ^[16] Известно также, что она верна для выпуклых геометрических графов (то есть для геометрических графов, вершины которых образуют множество вершин выпуклого n -угольника), ^[17] и для k -квазипланарных топологических графов, ребра которых нарисованы как x -монотонные кривые, все из которых пересекают вертикальную линию. ^{[18] [19]} Последний результат подразумевает, что любой k -квазипланарный топологический граф с n вершинами, ребра которых нарисованы как x -монотонные кривые, имеет не более c ( k ) n  log  n ребер для подходящей константы c ( k ). Для геометрических графов это было ранее доказано Валтром. ^[20] Лучшая известная общая верхняя граница для числа ребер k -квазипланарного топологического графа равна . ^[21] Это означает, что каждый полный топологический граф с n вершинами имеет по крайней мере попарно пересекающиеся ребра, что было улучшено до квазилинейной границы в случае геометрического графа. ^[22] ${\displaystyle n\log ^{O(\log k)}n}$ ${\displaystyle n^{\frac {1}{O(\log \log n)}}}$

Пересечение чисел

С тех пор, как Пал Туран сформулировал свою задачу о кирпичной фабрике ^[23] во время Второй мировой войны , определение или оценка чисел пересечений графов стало популярной темой в теории графов и в теории алгоритмов ^[24] , которая изобилует известными давно открытыми проблемами, такими как гипотеза Альбертсона , гипотеза Харари-Хилла ^[25] или до сих пор нерешенная задача о кирпичной фабрике Турана . ^[26] Однако публикации по этой теме (явно или неявно) использовали несколько конкурирующих определений чисел пересечений. На это указали Пах и Тот, ^[27] , которые ввели следующую терминологию.

Число пересечений (графа G ): минимальное число точек пересечения по всем рисункам графа G на плоскости (то есть по всем его представлениям в виде топологического графа) со свойством, что никакие три ребра не проходят через одну и ту же точку. Обозначается cr( G ).

Число парных пересечений : минимальное число пар пересечений ребер по всем рисункам графа G. Обозначается как pair-cr( G ).

Нечетное число пересечений : минимальное число пар ребер, которые пересекаются нечетное число раз, по всем рисункам графа G. Обозначается как odd-cr( G ).

Эти параметры не являются не связанными между собой. Для любого графа G выполняется неравенство odd-cr( G ) ≤ pair-cr( G ) ≤ cr( G ) . Известно, что cr( G ) ≤ 2(odd-cr( G )) ^{2 [27]} и ^[28] , и что существует бесконечно много графов, для которых pair-cr( G ) ≠ odd-cr( G ). ^{[1] [29]} Неизвестны примеры, для которых число пересечений и число парных пересечений не совпадают. Из теоремы Ханани–Тутта ^{[30] [31]} следует , что odd-cr( G ) = 0 влечет cr( G ) = 0. Также известно, что odd-cr( G ) =  k влечет cr(G)=k для k  = 1, 2, 3. ^[32] Другой хорошо изученный параметр графа следующий. ${\displaystyle O(\operatorname {pcr} (G)^{\frac {3}{2}}\log ^{2}\operatorname {pcr} (G))}$

Число прямолинейных пересечений : минимальное число точек пересечения по всем прямолинейным рисункам G на плоскости (то есть, все его представления в виде геометрического графа) со свойством, что никакие три ребра не проходят через одну и ту же точку. Обозначается как lin-cr( G ).

По определению, cr( G ) ≤ lin-cr( G ) для любого графа G . Было показано Биенстоком и Дином, что существуют графы с числом пересечений 4 и с произвольно большим числом прямолинейных пересечений. ^[33]

Вычисление числа пересечений в общем случае является NP-полным ^[34] . Поэтому большое количество исследований сосредоточено на его оценках. Лемма о пересечениях является краеугольным камнем, который обеспечивает широко применимые нижние границы числа пересечений. Известно несколько интересных вариантов и обобщений леммы о пересечениях для жордановых кривых ^{[35] [36]} и вырожденного числа пересечений ^{[37] [38]} , где последнее связывает понятие числа пересечений с родом графа .

Задачи типа Рамсея для геометрических графов

В традиционной теории графов типичный результат типа Рамсея гласит, что если мы раскрасим ребра достаточно большого полного графа фиксированным числом цветов, то мы обязательно найдем одноцветный подграф определенного типа. ^[39] Можно поднять аналогичные вопросы для геометрических (или топологических) графов, за исключением того, что теперь мы ищем одноцветные (одноцветные) подструктуры, удовлетворяющие определенным геометрическим условиям. ^[40] Один из первых результатов такого рода гласит, что каждый полный геометрический граф, ребра которого раскрашены двумя цветами, содержит непересекающееся одноцветное остовное дерево . ^[41] Также верно, что каждый такой геометрический граф содержит непересекающиеся ребра одного цвета. ^[41] Существование непересекающегося одноцветного пути размера не менее cn , где c  > 0 — константа, является давней открытой проблемой. Известно только, что каждый полный геометрический граф на n вершинах содержит непересекающийся одноцветный путь длины не менее . ^[42] ${\displaystyle \left\lceil {\frac {n+1}{3}}\right\rceil }$ ${\displaystyle n^{\frac {2}{3}}}$

Топологические гиперграфы

Если мы рассматриваем топологический граф как топологическую реализацию 1-мерного симплициального комплекса , естественно задаться вопросом, как вышеуказанные экстремальные и рамсеевские проблемы обобщаются на топологические реализации d -мерных симплициальных комплексов. В этом направлении есть некоторые начальные результаты, но требуются дальнейшие исследования для определения ключевых понятий и проблем. ^{[43] [44] [45]}

Два вершинно непересекающихся симплекса называются пересекающимися , если их относительные внутренности имеют общую точку. Набор из k  > 3 симплексов сильно пересекается , если никакие 2 из них не имеют общей вершины, но их относительные внутренности имеют общую точку.

Известно, что набор d -мерных симплексов, натянутых на n точек в без пары пересекающихся симплексов, может иметь не более симплексов, и эта граница асимптотически точна. ^[46] Этот результат был обобщен на наборы 2-мерных симплексов в без трех сильно пересекающихся симплексов. ^[47] Если мы запрещаем k сильно пересекающихся симплексов, соответствующая лучшая известная верхняя граница равна , ^[46] для некоторых . Этот результат следует из цветной теоремы Тверберга . ^[48] Он далек от предполагаемой границы . ^[46] ${\displaystyle \mathbb {R} ^{d}}$ ${\displaystyle O(n^{d})}$ ${\displaystyle \mathbb {R} ^{2}}$ ${\displaystyle O(n^{d+1-\delta })}$ ${\displaystyle \delta =\delta (k,d)<1}$ ${\displaystyle O(n^{d})}$

Для любого фиксированного k  > 1 мы можем выбрать не более d -мерных симплексов, охватывающих набор из n точек, со свойством, что никакие k из них не имеют общей внутренней точки. ^{[46] [49]} Это асимптотически точно. ${\displaystyle O(n^{\lceil {\frac {d}{2}}\rceil })}$ ${\displaystyle \mathbb {R} ^{d}}$

Два треугольника в называются почти непересекающимися , если они не пересекаются или если они имеют только одну общую вершину. Это старая проблема Гила Калаи и других, чтобы решить, является ли наибольшее число почти непересекающихся треугольников, которое может быть выбрано на некотором множестве вершин из n точек в . Известно, что существуют множества из n точек, для которых это число по крайней мере равно для подходящей константы c  > 0. ^[50] ${\displaystyle \mathbb {R} ^{3}}$ ${\displaystyle \mathbb {R} ^{3}}$ ${\displaystyle o(n^{2})}$ ${\displaystyle cn^{\frac {3}{2}}}$

Ссылки

1. Pelsmajer, Michael J.; Schaefer, Marcus; Štefankovič, Daniel (2008), «Нечетное число пересечений и число пересечений не одно и то же», Discrete and Computational Geometry , 39 (1–3): 442–454, doi : 10.1007/s00454-008-9058-xПредварительная версия этих результатов была рассмотрена в Proc. of 13th International Symposium on Graph Drawing , 2005, стр. 386–396, doi : 10.1007/11618058_35
2. Хопф, Хайнц ; Паннвиц, Эрика (1934), «Aufgabe № 167», Jahresbericht der Deutschen Mathematiker-Vereinigung , 43 : 114
3. Ловас, Ласло ; Пах, Янош ; Сегеди, Марио (1997), «О гипотезе Конвея о трекле», Дискретная и вычислительная геометрия , 18 (4), Springer: 369–376, doi : 10.1007/PL00009322
4. Фулек, Радослав ; Пах, Янош (2019), «Thrackles: улучшенная верхняя граница», Discrete Applied Mathematics , 259 : 226–231, arXiv : 1708.08037 , doi : 10.1016/j.dam.2018.12.025.
5. Пах, Янош ; Стерлинг, Итан (2011), «Гипотеза Конвея для монотонных треклов», American Mathematical Monthly , 118 (6): 544–548, doi :10.4169/amer.math.monthly.118.06.544, MR  2812285, S2CID  17558559
6. Алон, Нога ; Эрдёш, Пол (1989), «Непересекающиеся ребра в геометрических графах», Дискретная и вычислительная геометрия , 4 (4): 287–290, doi : 10.1007/bf02187731
7. Черны, Якуб (2005), «Геометрические графы без трех непересекающихся ребер», Дискретная и вычислительная геометрия , 34 (4): 679–695, doi : 10.1007/s00454-005-1191-1
8. Пах, Янош ; Тёрёчик, Йенё (1994), «Некоторые геометрические приложения теоремы Дилворта», Дискретная и вычислительная геометрия , 12 : 1–7, doi : 10.1007/BF02574361
9. Tóth, Géza (2000), «Заметка о геометрических графах», Журнал комбинаторной теории , Серия A, 89 (1): 126–132, doi : 10.1006/jcta.1999.3001
10. Pach, János ; Tóth, Géza (2003), "Disjoint sides in topological graphs", Комбинаторная геометрия и теория графов: совместная конференция Индонезии и Японии, IJCCGGT 2003, Бандунг, Индонезия, 13-16 сентября 2003 г., Пересмотренные избранные статьи (PDF) , Lecture Notes in Computer Science, т. 3330, Springer-Verlag, стр. 133–140, doi :10.1007/978-3-540-30540-8_15
11. Ruiz-Vargas, Andres J. (2015), "Множество непересекающихся рёбер в топологических графах", в Campêlo, Manoel; Corrêa, Ricardo; Linhares-Sales, Cláudia; Sampaio, Rudini (ред.), LAGOS'15 – VIII Latin-American Algorithms, Graphs and Optimization Symposium , Electronic Notes in Discrete Mathematics, т. 50, Elsevier, стр. 29–34, arXiv : 1412.3833 , doi : 10.1016/j.endm.2015.07.006, S2CID  14865350
12. Руис-Варгас, Андрес Дж. (2017), «Множество непересекающихся ребер в топологических графах», Comput. Geom. , 62 : 1–13, arXiv : 1412.3833 , doi : 10.1016/j.comgeo.2016.11.003
13. Пах, Янош ; Шахрохи, Фархад; Сегеди, Марио (1996), «Применение числа пересечений», Algorithmica , 16 (1), Springer: 111–117, doi : 10.1007/BF02086610, S2CID  20375896
14. Агарвал К., Панкадж ; Аронов Борис ; Пах, Янош ; Поллак, Ричард ; Шарир, Миха (1997), «Квазиплоские графы имеют линейное число ребер», Combinatorica , 17 : 1–9, doi : 10.1007/bf01196127, S2CID  8092013
15. Акерман, Эяль; Тардос, Габор (2007), «О максимальном числе ребер в квазипланарных графах», Журнал комбинаторной теории , Серия A, 114 (3): 563–571, ​​doi :10.1016/j.jcta.2006.08.002
16. Акерман, Эял (2009), «О максимальном количестве ребер в топологических графах без четырех попарно пересекающихся ребер», Дискретная и вычислительная геометрия , 41 (3): 365–375, doi : 10.1007/s00454-009-9143-9
17. Капойлеас, Василис; Пах, Янош (1992), «Теорема типа Турана о хордах выпуклого многоугольника», Журнал комбинаторной теории , Серия B, 56 (1): 9–15, doi :10.1016/0095-8956(92)90003-G
18. Сук, Эндрю (2011), " k -квазипланарные графы", Graph Drawing: 19th International Symposium, GD 2011, Эйндховен, Нидерланды, 21-23 сентября 2011 г., Revised Selected Papers , Lecture Notes in Computer Science, т. 7034, Springer-Verlag, стр. 266–277, arXiv : 1106.0958 , doi : 10.1007/978-3-642-25878-7_26, S2CID  18681576
19. Фокс, Якоб ; Пах, Янош ; Сук, Эндрю (2013), «Число ребер в k -квазипланарных графах», SIAM Journal on Discrete Mathematics , 27 (1): 550–561, arXiv : 1112.2361 , doi : 10.1137/110858586, S2CID  52317.
20. Вальтр, Павел (1997), «Рисунок графа без k попарно пересекающихся ребер», Рисование графа: 5-й международный симпозиум, GD '97 Рим, Италия, 18–20 сентября 1997 г., Труды , Lecture Notes in Computer Science, т. 1353, Springer-Verlag, стр. 205–218
21. Фокс, Якоб; Пах, Янош (2012), «Раскраска графов пересечений без K k {\displaystyle K_{\mbox{k}}} геометрических объектов на плоскости» (PDF) , Европейский журнал комбинаторики , 33 (5): 853–866, doi : 10.1016/j.ejc.2011.09.021Предварительная версия этих результатов была опубликована в Proc. of Symposium on Computational Geometry (PDF) , 2008, стр. 346–354, doi :10.1145/1377676.1377735, S2CID  15138458
22. Пах, Янош ; Рубин, Натан; Тардос, Габор (2021), «Планарные множества точек определяют множество попарно пересекающихся сегментов», Успехи в математике , 386 : 107779, arXiv : 1904.08845 , doi : 10.1016/j.aim.2021.107779.
23. Туран, Пол (1977), «Приветственное сообщение», Журнал теории графов , 1 : 7–9, doi :10.1002/jgt.3190010105
24. Гэри, М. Р .; Джонсон, Д. С. (1983), «Пересечение чисел является NP-полным», Журнал SIAM по алгебраическим и дискретным методам , 4 (3): 312–316, doi :10.1137/0604033, MR  0711340{{citation}}: CS1 maint: несколько имен: список авторов ( ссылка )
25. Балог, Йожеф; Лидицкий, Бернард; Салазар, Геласио (2019), «Приближение к гипотезе Хилла», SIAM Journal on Discrete Mathematics , 33 (3): 1261–1276, arXiv : 1711.08958 , doi : 10.1137/17M1158859, S2CID  119672893
26. Шефер, Маркус (2012), «Число пересечений графов и его варианты: обзор», Электронный журнал комбинаторики , 1000 : DS21–May, doi : 10.37236/2713
27. Pach, János; Tóth, Géza (2000), «Какое же это число пересечения?», Журнал комбинаторной теории , Серия B, 80 (2): 225–246, doi : 10.1006/jctb.2000.1978
28. Матоушек, Йиржи (2014), «Почти оптимальные разделители в строковых графах», Combin. Probab. Comput. , т. 23, стр. 135–139, arXiv : 1302.6482 , doi : 10.1017/S0963548313000400, S2CID  2351522
29. Tóth, Géza (2008), «Заметка о числе парных пересечений и числе нечетных пересечений», Discrete and Computational Geometry , 39 (4): 791–799, doi : 10.1007/s00454-007-9024-z.
30. Хойнацкий (Ханани), Хаим (Хаим) (1934), «Uber wesentlich unplattbar Kurven im drei Dimensionale Raume», Fundamenta Mathematicae , 23 : 135–142, doi : 10.4064/fm-23-1-135-142
31. Тутт, Уильям Т. (1970), «К теории скрещивающихся чисел», Журнал комбинаторной теории , 8 : 45–53, doi :10.1016/s0021-9800(70)80007-2
32. Pelsmajer, Michael J.; Schaefer, Marcus; Štefankovič, Daniel (2007), «Удаление четных пересечений», Журнал комбинаторной теории , Серия B, 97 (4): 489–500, doi :10.1016/j.jctb.2006.08.001
33. Бьенсток, Дэниел; Дин, Натаниэль (1993), «Границы для прямолинейных чисел пересечения», Журнал теории графов , 17 (3): 333–348, doi :10.1002/jgt.3190170308
34. Garey, MR ; Johnson, DS (1983). «Crossing number is NP-complete». SIAM Journal on Algebraic and Discrete Methods . 4 (3): 312–316. doi :10.1137/0604033. MR  0711340.
35. Пач, Янош ; Рубин, Натан; Тардос, Габор (2018), «Лемма о пересечении жордановых кривых», Advances in Mathematics , 331 : 908–940, arXiv : 1708.02077 , doi : 10.1016/j.aim.2018.03.015, S2CID  22278629
36. Пач, Янош ; Тот, Геза (2019), «Множество прикосновений приводит к множеству пересечений», Журнал комбинаторной теории , серия B, 137 : 104–111, arXiv : 1706.06829 , doi : 10.1016/j.jctb.2018.12.002
37. Акерман, Эяль; Пинхаси, Ром (2013), «О числе вырожденных перекрестков», Дискретная и вычислительная геометрия , 49 (3): 695–702, doi :10.1007/s00454-013-9493-1, S2CID  254030772
38. Шефер, Маркус; Штефанкович, Дэниел (2015), «Число вырожденных скрещиваний и вложения более высокого рода», Рисование графа: 23-й международный симпозиум, GD 2015, Лос-Анджелес, Калифорния, США, 24-26 сентября 2015 г., Пересмотренные избранные статьи , стр. 63–74, doi : 10.1007/978-3-319-27261-0_6
39. Грэм, Рональд Л.; Ротшильд, Брюс Л.; Спенсер, Джоэл Х. (1990), Теория Рамсея , Wiley
40. Каройи, Дьюла (2013), «Проблемы типа Рамсея для геометрических графов», в Pach, J. (ред.), Тридцать эссе по геометрической теории графов , Springer
41. Кароли, Дьюла Дж.; Пах, Янош; Тот, Геза (1997), «Результаты типа Рамсея для геометрических графов, I», Дискретная и вычислительная геометрия , 18 (3): 247–255, doi : 10.1007/PL00009317
42. Кароли, Дьюла Дж.; Пах, Янош; Тот, Геза; Валтр, Павел (1998), «Результаты типа Рамсея для геометрических графов, II», Дискретная и вычислительная геометрия , 20 (3): 375–388, doi : 10.1007/PL00009391
43. Пах, Янош (2004), «Геометрическая теория графов», в Goodman, Jacob E. ; O'Rourke, Joseph (ред.), Handbook of Discrete and Computational Geometry , Discrete Mathematics and Its Applications (2-е изд.), Chapman and Hall/CRC
44. Матоушек, Йиржи ; Танцер, Мартин; Вагнер, Ули (2009), «Трудность вложения симплициальных комплексов в », Труды двадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , стр. 855–864 ${\displaystyle \mathbb {R} ^{d}}$
45. Брасс, Питер (2004), «Проблемы типа Турана для выпуклых геометрических гиперграфов», в Pach, J. (ред.), К теории геометрических графов , Contemporary Mathematics, Американское математическое общество, стр. 25–33
46. Дей, Тамал К.; Пах, Янош (1998), «Экстремальные задачи для геометрических гиперграфов», Дискретная и вычислительная геометрия , 19 (4): 473–484, doi : 10.1007/PL00009365
47. Сук, Эндрю (2013), «Заметка о геометрических 3-гиперграфах», в Pach, J. (ред.), Тридцать эссе о геометрической теории графов , SpringerarXiv:1010.5716v3
48. Живальевич, Раде Т.; Вречица, Синиша Т. (1992), «Цветная проблема Тверберга и комплексы инъективных функций», Журнал комбинаторной теории , Серия A, 61 (2): 309–318, doi : 10.1016/0097-3165(92)90028-S
49. Барань, Имре; Фюреди, Золтан (1987), «Пустые симплексы в евклидовом пространстве», Canadian Mathematical Bulletin , 30 (4): 436–445, doi : 10.4153/cmb-1987-064-1, hdl : 1813/8573 , S2CID  122255929
50. Кароли, Дьюла; Солимоси, Йожеф (2002), «Почти непересекающиеся треугольники в трехмерном пространстве», Дискретная и вычислительная геометрия , 28 (4): 577–583, doi : 10.1007/s00454-002-2888-z