Stativförpackning

Olöst problem i matematik :

Hur många stativ kan ha sina spetsar packade i en given kub?

(fler olösta problem i matematik)

En stativförpackning och dess motsvarande monotona matris. Detta exempel motsvarar den 2-jämförbara uppsättningen {(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)}.

Inom kombinatorik är stativpackning ett problem med att hitta många disjunkta stativ i ett tredimensionellt rutnät, där ett stativ är en oändlig polykub , föreningen av rutnätskuberna längs tre positiva axelinriktade strålar med en delad spets.

Flera problem med plattsättning och packning av stativ och relaterade former formulerades 1967 av Sherman K. Stein . Stein kallade ursprungligen detta problems tripods för "semicrosses", och de kallades också Stein-hörn av Solomon W. Golomb . En samling disjunkta stativ kan representeras kompakt som en monoton matris , en kvadratisk matris vars poster som inte är noll ökar längs varje rad och kolumn och vars lika stora poster som inte är noll placeras i en monoton sekvens av celler, och problemet kan också formuleras i termer av hitta uppsättningar av trianglar som uppfyller ett kompatibilitetsvillkor som kallas "2-jämförbarhet", eller att hitta kompatibla uppsättningar av trianglar i en konvex polygon.

Den bästa nedre gränsen som är känd för antalet stativ som kan ha sina spetsar packade i ett $n\times n\times n$$) {\displaystyle \Omega (n^{ 1,546})}$ är , och den bästa övre gränsen är ${\displaystyle n^{2}/\exp \Omega (\log ^{*}n)} ,$ båda uttryckta i stor Omega notation .

Motsvarande problem

Koordinaterna $(x_{i},y_{i},z_{i})$ för spetsarna för en lösning på stativproblemet bildar två jämförbara uppsättningar av trippel , där två trippel definieras som 2-jämförbara om det antingen finns minst två koordinater där en trippel är mindre än den andra, eller minst två koordinater där en trippel är större än den andra. Detta tillstånd säkerställer att stativ som definieras från dessa trippel inte har korsande strålar.

En annan likvärdig tvådimensionell version av frågan frågar hur många celler i en $n\times n$ array av kvadratiska celler (indexerad från $1$ till ${\displaystyle n} )$ som kan fyllas in med siffrorna från $1$ till $n$ på ett sådant sätt att de icke-tomma cellerna i varje rad och varje kolumn i arrayen bildar strikt ökande talsekvenser och positionerna som innehåller varje värde $i$ bildar en monoton kedja inom arrayen. En matris med dessa egenskaper kallas en monoton matris. En samling disjunkta stativ med spetsar $(x_{i},y_{i},z_{i})$ kan omvandlas till en monoton matris genom att placera talet $z_{i}$ i arraycell $(x_{i},y_{i})$ och vice versa.

Problemet är också likvärdigt med att hitta så många trianglar som möjligt bland hörnen i en konvex polygon, så att inga två trianglar som delar en vertex har kapslade vinklar vid den vertexen. Detta triangelräkningsproblem ställdes av Peter Braß och dess likvärdighet med stativpackning observerades av Aronov et al.

Nedre gränser

Det är enkelt att hitta en lösning på packningsproblemet med stativ med $\Omega (n^{3/2})$ stativ. Till exempel, för $displaystyle k=\lfloor {\sqrt {n}}\rfloor } ,$$\Omega (n^{3/2})$ Ω tredubblar

$${\bigl \{}(ak+b+1,bk+c+1,ak+c+1){\big |}a,b, c\in [0,k-1]{\bigr \}}$$

är 2-jämförbara.

Efter flera tidigare förbättringar av denna naiva gräns, hittade Gowers och Long lösningar på stativproblemet med kardinalitet $\Omega (n^{1.546})$ .

Övre gränser

Från vilken lösning som helst på stativpackningsproblemet kan man härleda en balanserad tredelad graf vars hörn är tre kopior av talen från $0$ till $n-1$ (en för var och en av de tre koordinaterna) med en triangel av kanter som förbinder de tre hörnen som motsvarar koordinaterna för spetsen på varje stativ. Det finns inga andra trianglar i dessa grafer (de är lokalt linjära grafer ) eftersom vilken annan triangel som helst skulle leda till ett brott mot 2-jämförbarhet. Därför, genom de kända övre gränserna för Ruzsa–Szemerédi-problemet (varav en version är att hitta den maximala tätheten av kanter i en balanserad tredelad lokalt linjär graf), det maximala antalet disjunkta stativ som kan packas i ett $n\times n\times n$ rutnät är $o(n^{2})$ , och mer exakt ${\ displaystyle n^{2}/\exp \Omega (\log ^{*}n)}$ . Även om Tiskin skriver att "snävare analys av parametrarna" kan producera en gräns som är mindre än kvadratisk av en polylogaritmisk faktor, tillhandahåller han inga detaljer och hans bevis för att talet är o ( n 2 ) {\ ${ 2})}$ använder bara samma tekniker som är kända för Ruzsa–Szemerédi-problemet, så detta starkare påstående verkar vara ett misstag.

Ett argument från Dean Hickerson visar att, eftersom stativ inte kan packa utrymme med konstant densitet, gäller samma sak för analoga problem i högre dimensioner.

Små instanser

För små fall av stativproblemet är den exakta lösningen känd. Antalet stativ som kan packas i en $n\times n\times n$ kub, för $n\leq 11$ , är:

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

Till exempel visar figuren de 11 stativ som kan packas i en $5\times 5\times 5$ kub.

Antalet distinkta monotona matriser av ordningen $n$ , för $n=1,2,3,\dots$ är

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