Упаковка штатива

Нерешенная задача по математике :

Сколько треног можно упаковать своими вершинами в данный куб?

(еще нерешенные проблемы по математике)

Упаковка трипода и соответствующая ей монотонная матрица. Этот пример соответствует 2-сравнимому набору {(1,1,1), (1,3,3), (2,1,2), (2,4,3), (3,1,4), (3,4,5), (4,2,1), (4,5,3), (5,2,2), (5,3,4), (5,5,5)}. ^[1]

В комбинаторике упаковка триподов — это задача нахождения множества непересекающихся триподов в трехмерной сетке, где трипод — это бесконечный поликуб , объединение кубов сетки вдоль трех положительных осей, выровненных по лучам с общей вершиной. ^[1]

Несколько задач по укладке и упаковке триподов и связанных с ними фигур были сформулированы в 1967 году Шерманом К. Стайном . ^[2] Первоначально Стайн называл триподы этой задачи «полукроссами», а Соломон В. Голомб также называл их углами Стайна . [ ^3] Набор непересекающихся триподов можно компактно представить в виде монотонной матрицы , квадратной матрицы, ненулевые элементы которой увеличиваются вдоль каждой строки и столбца, а равные ненулевые элементы размещаются в монотонной последовательности ячеек, ^[4] и задача также может быть сформулирована в терминах нахождения наборов троек, удовлетворяющих условию совместимости, называемому «2-сравнимостью», или нахождения совместимых наборов треугольников в выпуклом многоугольнике. ^[1]

Лучшая нижняя граница, известная для числа треножников, вершины которых могут быть упакованы в сетку , равна , а лучшая верхняя граница равна , обе выражены в большой нотации Омега . ^{[1] [5]} ${\displaystyle n\times n\times n}$ ${\displaystyle \Omega (n^{1.546})}$ ${\displaystyle n^{2}/\exp \Omega (\log ^{*}n)}$

Эквивалентные проблемы

Координаты вершин решения задачи о треноге образуют 2-сравнимые наборы троек , где две тройки определяются как 2-сравнимые, если есть либо по крайней мере две координаты, где одна тройка меньше другой, либо по крайней мере две координаты, где одна тройка больше другой. Это условие гарантирует, что треноги, определенные из этих троек, не имеют пересекающихся лучей. ^[1] ${\displaystyle (x_{i},y_{i},z_{i})}$

Другая эквивалентная двумерная версия вопроса спрашивает, сколько ячеек массива квадратных ячеек (индексированных от до ) можно заполнить числами от до таким образом, чтобы непустые ячейки каждой строки и каждого столбца массива образовывали строго возрастающие последовательности чисел, а позиции, содержащие каждое значение, образовывали монотонную цепочку внутри массива. Массив с такими свойствами называется монотонной матрицей. Набор непересекающихся триподов с вершинами можно преобразовать в монотонную матрицу, поместив число в ячейку массива и наоборот. ^[1] ${\displaystyle n\times n}$ ${\displaystyle 1}$ ${\displaystyle n}$ ${\displaystyle 1}$ ${\displaystyle n}$ ${\displaystyle i}$ ${\displaystyle (x_{i},y_{i},z_{i})}$ ${\displaystyle z_{i}}$ ${\displaystyle (x_{i},y_{i})}$

Задача также эквивалентна нахождению как можно большего числа треугольников среди вершин выпуклого многоугольника, так что никакие два треугольника, которые имеют общую вершину, не имеют вложенных углов в этой вершине. Эта задача подсчета треугольников была поставлена ​​Питером Брассом ^[6] , а ее эквивалентность упаковке триподов была отмечена Ароновым и др. ^[1]

Нижние границы

Легко найти решение задачи упаковки треноги с помощью треноги. ^[1] Например, для тройки являются 2 - сравнимыми. ${\displaystyle \Omega (n^{3/2})}$ ${\displaystyle k=\lfloor {\sqrt {n}}\rfloor }$ ${\displaystyle \Omega (n^{3/2})}$ $${\displaystyle {\bigl \{}(ak+b+1,bk+c+1,ak+c+1){\big |}a,b,c\in [0,k-1]{\bigr \}}}$$

После нескольких предыдущих улучшений этой наивной границы, ^{[7] [8] [9]} Гауэрс и Лонг нашли решения проблемы мощности треножника . ^[5] ${\displaystyle \Omega (n^{1.546})}$

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

Из любого решения задачи упаковки трипода можно вывести сбалансированный трехдольный граф, вершинами которого являются три копии чисел от до (по одной для каждой из трех координат) с треугольником ребер, соединяющим три вершины, соответствующие координатам вершины каждого трипода. В этих графах нет других треугольников (они являются локально линейными графами ), поскольку любой другой треугольник привел бы к нарушению 2-сравнимости. Следовательно, по известным верхним границам задачи Ружи–Семереди (одной из версий которой является нахождение максимальной плотности ребер в сбалансированном трехдольном локально линейном графе), максимальное число непересекающихся триподов, которые можно упаковать в сетку, равно , а точнее . ^{[1] [5] [9] [10]} Хотя Тискин пишет, что «более строгий анализ параметров» может дать границу, которая меньше квадратичной на полилогарифмический множитель, ^[9] он не приводит подробностей, а его доказательство того, что число равно , использует только те же методы, которые известны для задачи Ружи–Семереди, поэтому это более сильное утверждение, по-видимому, является ошибкой. ^[1] ${\displaystyle 0}$ ${\displaystyle n-1}$ ${\displaystyle n\times n\times n}$ ${\displaystyle o(n^{2})}$ ${\displaystyle n^{2}/\exp \Omega (\log ^{*}n)}$ ${\displaystyle o(n^{2})}$

Аргумент Дина Хикерсона показывает, что, поскольку треножники не могут заполнить пространство с постоянной плотностью, то же самое справедливо и для аналогичных задач в более высоких измерениях. ^[4]

Небольшие экземпляры

Для небольших примеров задачи о треноге точное решение известно. Число треногих, которые можно упаковать в куб, для , равно: ^{[9] [11] [12] [13]} ${\displaystyle n\times n\times n}$ ${\displaystyle n\leq 11}$

1, 2, 5, 8, 11, 14, 19, 23, 28, 32, 38,...

Например, на рисунке показано 11 штативов, которые можно упаковать в куб. ${\displaystyle 5\times 5\times 5}$

Число различных монотонных матриц порядка для равно ^[14] ${\displaystyle n}$ ${\displaystyle n=1,2,3,\dots }$

2, 19, 712, 87685, 31102080, 28757840751, ...

Ссылки

1. Аронов, Борис ; Дуймович, Вида ; Морен, Пат ; Оомс, Орельен; Шульц Ксавье да Силвейра, Луис Фернандо (2019), «Еще больше теорем типа Турана для треугольников в выпуклых точечных множествах», Электронный журнал комбинаторики , 26 (1): стр. 1.8
2. Stein, SK (1967), «Факторизация по подмножествам», Pacific Journal of Mathematics , 22 : 523–541, doi : 10.2140/pjm.1967.22.523 , MR  0219435
3. Голомб, SW (1969), «Общая формулировка метрик ошибок», IEEE Transactions on Information Theory , IT-15: 425–426, doi :10.1109/tit.1969.1054308, MR  0243902
4. Stein, Sherman K. ; Szabó, Sándor (1994), Algebra and Tiling: Homomorphisms in the Service of Geometry , Carus Mathematical Monographs, т. 25, Вашингтон, округ Колумбия: Математическая ассоциация Америки, стр. 97, ISBN 0-88385-028-1, г-н  1311249
5. Gowers, WT ; Long, J. (январь 2021 г.), «Длина -возрастающей последовательности -кортежей », Комбинаторика, вероятность и вычисления : 1–36, arXiv : 1609.08688 , doi :10.1017/s0963548320000371 ${\displaystyle s}$ ${\displaystyle r}$
6. Braß, Peter (2004), «Экстремальные задачи типа Турана для выпуклых геометрических гиперграфов», в Pach, János (ред.), Towards a theory of geometric graphs , Contemporary Mathematics, т. 342, Providence, Rhode Island: American Mathematical Society, стр. 25–33, doi : 10.1090/conm/342/06128, MR  2065250
7. Хамакер, Уильям; Стайн, Шерман (1984), «Комбинаторная упаковка сфер с определенными ошибками», IEEE Transactions on Information Theory , 30 (2, часть 2): 364–368, doi :10.1109/TIT.1984.1056868, MR  0754867 ${\displaystyle \mathbf {R} ^{3}}$
8. Стайн, Шерман К. (март 1995), «Упаковка штативов», Математические развлечения, The Mathematical Intelligencer , 17 (2): 37–39, doi :10.1007/bf03024896. Перепечатано в Gale, David (1998), Tracking the Automatic ANT , Springer-Verlag, стр. 131–136, doi :10.1007/978-1-4612-2192-0, ISBN 0-387-98272-8, г-н  1661863
9. Тискин, Александр (2007), «Упаковка триподов: сужение разрыва плотности», Дискретная математика , 307 (16): 1973–1981, doi : 10.1016/j.disc.2004.12.028 , MR  2326159
10. Ло, По-Шен (2015), Направленные пути: от Рамси до Ружи и Семереди , arXiv : 1505.07312
11. Сабо, Шандор (2013), «Монотонные матрицы и поиск клик в графах», Ann. Univ. Sci. Budapest Sect. Comput. , 41 : 307–322, doi :10.1080/00455091.2001.10717569, MR  3129145
12. Остергорд, Патрик Р.Дж.; Пёлленен, Антти (2019), «Новые результаты по насадкам штатива» (PDF) , Discrete & Computational Geometry , 61 (2): 271–284, doi : 10.1007/s00454-018-0012-2, MR  3903789
13. Слоан, Н. Дж. А. (ред.), «Последовательность A070214», Онлайновая энциклопедия целочисленных последовательностей , Фонд OEIS
14. Слоан, Н. Дж. А. (ред.), «Последовательность A086976», Онлайновая энциклопедия целочисленных последовательностей , Фонд OEIS