Pakowanie statywu

Nierozwiązany problem z matematyki :

Ile trójnogów może mieć wierzchołki upakowane w danym sześcianie?

(więcej nierozwiązanych problemów z matematyki)

Opakowanie statywu i odpowiadająca mu macierz monotoniczna. Ten przykład odpowiada zestawowi porównywalnemu z 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)}.

W kombinatoryce upakowanie statywu jest problemem polegającym na znalezieniu wielu rozłącznych statywów w trójwymiarowej siatce, gdzie statyw jest nieskończonym polisześcianem , połączeniem kostek siatki wzdłuż trzech dodatnich osi wyrównanych promieni ze wspólnym wierzchołkiem.

Sherman K. Stein sformułował kilka problemów związanych z układaniem i pakowaniem statywów oraz związanych z nimi kształtów . Stein pierwotnie nazwał statywy tego problemu „półkrzyżami”, a Solomon W. Golomb nazwał je również narożnikami Steina . Zbiór rozłącznych trójnogów można zwięźle przedstawić jako macierz monotoniczną , kwadratowa macierz, której niezerowe wpisy rosną wzdłuż każdego wiersza i kolumny i której równe niezerowe wpisy są umieszczone w monotonicznej sekwencji komórek, a problem można również sformułować w kategoriach znalezienia zbiorów trójek spełniających warunek zgodności zwany „2-porównywalność „lub znajdowania zgodnych zestawów trójkątów w wypukłym wielokącie.

Najlepsza dolna granica znana dla liczby statywów, których wierzchołki mogą być upakowane w siatkę, to n $\ displaystyle n \ razy n \ razy n}$${\ Displaystyle \ Omega (n ^ { 1,546})}$ , a najlepszą górną granicą jest ${\ Displaystyle n ^ {2}/\ exp \ Omega (\ log ^ {*} n)}$ , oba wyrażone w duża notacja Omega .

Równoważne problemy

$_$ wierzchołków _ _ , gdzie dwie trójki są zdefiniowane jako 2-porównywalne, jeśli istnieją co najmniej dwie współrzędne, w których jedna trójka jest mniejsza od drugiej, lub co najmniej dwie współrzędne, w których jedna trójka jest większa od drugiej. Warunek ten zapewnia, że ​​statywy zdefiniowane z tych trójek nie mają przecinających się promieni.

$displaystyle n \ razy n}$ równoważna dwuwymiarowa wersja pytania zadaje pytanie, ile komórek tablicy ${\$ komórek (indeksowanych od do $)$ można wypełnić przez liczby od do $\ displaystyle$$n}$ w taki sposób, że niepuste komórki każdego wiersza i każdej kolumny tablicy tworzą ściśle rosnące sekwencje liczb, a pozycje zawierające każdą wartość ${\ Displaystyle i}$ tworzą monotoniczny łańcuch w tablicy. Tablica o takich właściwościach nazywana jest macierzą monotoniczną. Zbiór $rozłącznych$ z ${\ Displaystyle z_ {i}}$ w komórce tablicy ${\ Displaystyle (x_ {i}, y_ {i})}$ i odwrotnie.

Problem jest również równoważny znalezieniu jak największej liczby trójkątów wśród wierzchołków wielokąta wypukłego, tak aby żadne dwa trójkąty, które mają wspólny wierzchołek, nie miały zagnieżdżonych kątów w tym wierzchołku. Ten problem liczenia trójkątów został postawiony przez Petera Braßa, a jego równoważność z pakowaniem na statywie zaobserwowali Aronov i in.

Dolne granice

$statywów$ rozwiązania problemu pomocą Na przykład ${\ Displaystyle k = \ lfloor {\ sqrt {n}} \ rfloor}$$\ Displaystyle \ Omega (n ^ {3/2})}$ ( trójki

$${\ Displaystyle {\ bigl \ {} (ak + b + 1, bk + c + 1, ak + c + 1) {\ duży |} a, b, c\w [0,k-1]{\bigr \}}}$$

są 2-porównywalne.

Po kilku wcześniejszych ulepszeniach tego naiwnego ograniczenia, Gowers i Long znaleźli rozwiązania problemu liczności statywu . ${\ Displaystyle \ Omega (n ^ {1,546})}$ .

Górne granice

$zrównoważony$ trójdzielny wykres, którego wierzchołki są trzema kopiami liczb od (po jednej dla każdej z trzech współrzędnych ) ${\ displaystyle n-1}$ z trójkątem krawędzi łączących trzy wierzchołki odpowiadające współrzędnym wierzchołka każdego statywu. Na tych wykresach nie ma innych trójkątów (są to wykresy lokalnie liniowe ), ponieważ każdy inny trójkąt prowadziłby do naruszenia zasady 2-porównywalności. Dlatego według znanych górnych granic problemu Ruzsy – Szemerédiego (jedną z wersji jest znalezienie maksymalnej gęstości krawędzi w zrównoważonym trójdzielnym lokalnie liniowym wykresie), maksymalna liczba rozłącznych trójnogów, które można upakować w n × n × n {\ $\ razy n}$ siatka jest ${\ Displaystyle o (n ^ {2})}$ , a dokładniej ${\ Displaystyle n ^ {2} / \ exp \ Omega (\ dziennik ^{*}n)}$ . Chociaż Tiskin pisze, że „ściślejsza analiza parametrów” może dać granicę, która jest mniejsza niż kwadratowa przez współczynnik polilogarytmiczny, nie podaje szczegółów ani dowodu, że liczba ta jest o ( n 2 ) {\ ${ 2})}$ używa tylko tych samych technik, które są znane z problemu Ruzsy-Szemerédiego, więc to silniejsze twierdzenie wydaje się być błędem.

Argument Deana Hickersona pokazuje, że ponieważ statywy nie mogą upakować miejsca ze stałą gęstością, to samo dotyczy analogicznych problemów w wyższych wymiarach.

Małe przypadki

W przypadku małych przypadków problemu ze statywem znane jest dokładne rozwiązanie. Liczby statywów, które można upakować w sześcian dla ${\ displaystyle n \ razy n \ razy n}$ to: ${\ displaystyle n \ leq 11}$

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

$w$ statywów, które można zapakować kostkę

Liczba różnych monotonicznych macierzy rzędu dla ${\ displaystyle n}$$Displaystyle n = 1,2,3, \ kropek}$ wynosi n

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