A Danzer-Grunbaum probléma

A Danzer-Grunbaum probléma egy kombinatorikus geometriai probléma , amely felveti azt a kérdést, hogy legfeljebb hány pont helyezhető el egy többdimenziós térben úgy, hogy ne képezzenek egymás között derékszöget vagy tompaszöget. Ismeretes, hogy egy síkon legfeljebb három ilyen, háromdimenziós térben öt ilyen pont helyezhető el. 2017-ben bebizonyosodott, hogy Θ ilyen pontok elhelyezhetők a dimenziók terében. $d$ $(2^{d})$

A probléma leírása

Adott esetén jelölje a különböző pontok maximális számát a dimenziós térben úgy, hogy bármely három pont hegyesszögű háromszöget képezzen , azaz bármely három esetén a skaláris szorzat . $d$ $f(d)$ $d$ $x,y,z$ $\langle {yx,zx}\rangle >0$

Hogyan nő relatíve ? $f(d)$ $d$

Más szóval, a probléma az, hogy találjunk egy egyszerű képletet, amely a lehető legjobb pontossággal fejezi ki az eredményt (és egy algoritmus megtalálása egy ponthalmaz felépítéséhez ). $f(d)$ $d$ $f(d)$

Azokat a halmazokat, amelyek pontjai csak hegyesszöget alkotnak, hegyesszögű halmazoknak nevezzük . Figyeljük meg, hogy a definícióból az következik, hogy egy hegyesszögű halmazban nem lehet három pont ugyanazon az egyenesen.

2018 márciusától ismert, hogy . ${\displaystyle 2^{d-1}+1\leq f(d)\leq 2^{d))$

Kapcsolódó feladatok

Tompaszögek nélküli halmazok

A következő problémát Erdős a Danzer-Grunbaum probléma klasszikus megfogalmazásánál is korábban vetette fel [1] :

Adott esetén jelölje a -dimenziós tér különböző pontjainak maximális számát, amelyek közül három nem alkot szigorúan tompaszöget, azaz bármelyik három $d$ $g(d)$ $d$ $x,y,z$ $\langle {yx,zx}\rangle \geq 0$

Hogyan nő relatíve ? $g(d)$ $d$

Köztudott, hogy . ${\displaystyle g(d)=2^{d))$

Kocka csúcsai

Erdős és Furedi a témában az első igazán áttörő munkában adott feltételeket kielégítő nagy halmazt építettek fel egy -dimenziós kocka csúcsaiból . Ezért a további munkák során az eredmény javítása érdekében a következő problémát esetenként külön-külön is figyelembe vették: $d$ ${\displaystyle {\left\lkapcsos zárójel {0,1}\jobbra\rkapcsos zárójel }^{d))$

Adottnál a -dimenziós kocka különböző csúcsainak maximális számával jelöljük, amelyek közül nem három alkot sem derékszöget, sem tompaszöget, azaz bármelyik háromra , $d$ $f_{\square }(d)$ $d$ $\left\lkapcsos zárójel {0,1}\jobbra\rkapcsos zárójel ^{d}$ $x,y,z$ $\langle {yx,zx}\rangle >0$

Hogyan nő relatíve ? $f_{\square }(d)$ $d$

Nyilvánvaló, hogy . $f_{\square }(d)\leq f(d)$

Tanulmánytörténet

Első említések (Erdős, 1948, 1957)

A probléma története 1948-ban kezdődik, amikor Erdős Pál az American Mathematical Monthly "Additional Problems to Solve " rovatában publikálta a jövőbeli Danzer-Grünbaum probléma alábbi speciális esetét [2] :

Legyen adott nyolc pont a térben . Bizonyítsuk be, hogy ezek közül mindig lehet hármat találni, amelyek nem alkotnak hegyesszögű háromszöget. ${\mathbb {R} }^{3}$

Vagyis a probléma azt kérdezte, hogy ez igaz-e $f(3)<8$

Erdős 1957-ben a Michigan Mathematical Journalban egy sok sejtést tartalmazó cikkben általános sejtést közölt, de a tompahalmazokra vonatkozóan.

Legyen pontok halmaza egy dimenziós térben . Igaz-e, hogy akkor ezek között szükségszerűen van három tompaszöget bezáró pont? $S$ $2^{d}+1$ $k$

Vagyis a hipotézis azt állította, hogy . ${\displaystyle g(d)\leq 2^{d))$

A cikk szerint Nicolas Kuiper és Boerdijk találtak bizonyítékot , de bizonyítékukat még nem tették közzé. $d=3$

A hipotézis mellett a következő kérdés volt:

Igaz-e, hogy van egy hat (hét) pontból álló halmaz a háromdimenziós térben úgy, hogy bármelyik három hegyesszöget alkot?

Vagy más szóval igaz-e, hogy vagy . [egy] $f(3)\geq 6$ $f(3)\geq 7$

Az első hipotézis (Danzer és Grünbaum, 1962)

Az első általános konstrukciót ennek a problémának a megoldására Ludwig Danzer és Branko Grünbaum építette meg egy 1962-es tanulmányában. A dimenziós térben egy pontot építettek , amelynek koordinátái így nézett ki (a sorok különböző pontok, az oszlopok különböző koordináták): $d$ $2d-1$

{\begin{pmatrix}1&0&0&\cdots &0&0\\-\delta _{1}&1&0&\cdots &0&0\\-\delta _{1}&-1&0&\cdots &0&0\\-\delta _{2} &0&1&\cdots &0&0\\-\delta _{2}&0&-1&\cdots &0&0\\\vdots &\vdots &\ddots &\vdots \\-\delta _{d-2}&0&0&\cdots &1&0\\- \delta _{d-2}&0&0&\cdots &-1&0\\-\delta _{d-1}&0&0&\cdots &0&1\\-\delta _{d-1}&0&0&\cdots &0&-1\end{pmátrix }}

ahol páronként különböző számok vannak, mindegyik kisebb. ${\displaystyle \delta _{1},\dots ,\delta _{d-1))$

A különböző típusú szögek egyszerű kombinatorikus felsorolása lehetővé teszi annak kimutatását, hogy ezek közül a pontok közül három sem alkot derékszöget vagy tompaszöget. Ebből következik, hogy $f(d)\geq 2d-1$

Ugyanebben a munkában a szerzők azt feltételezték, hogy lehetetlen több olyan pontot konstruálni, amely teljesíti ezt a feltételt, vagyis azt, hogy [3] . $f(d)=2d-1$

Ebben a munkában is igazolták a felső határt , amelyet korábban Erdős javasolt. ${\displaystyle f(d)\leq g(d)\leq 2^{d))$

A valószínűségi módszer alkalmazása (Erdős, Furedi, 1983)

1983-ban Paul Erdős és Zoltan Furedy valószínűségi módszerrel cáfolta a Danzer-Grünbaum hipotézist , megmutatva, hogy

f(d)\geq f_{\square }(d)\geq \left\lfloor {{\frac {1}{2}}{\left({\frac {2}{\sqrt {3} }}\jobbra)}^{d}}\jobbra\rpadló

Ez lehetővé tette ellenpéldák megalkotását a Danzer-Grünbaum sejtésre . [4] [5] $d\geq 35$

Bizonyításuk azonban a valószínűségi módszer sajátosságai miatt nem volt hatékony, és nem tette lehetővé ennek a halmaznak az explicit felépítését (kivéve közvetlen felsorolással) [3] .

Erdős és Furedy fő gondolata az volt, hogy olyan pontkészletet válasszanak, amelynek (pozitív valószínűséggel) nagyon kevés derékszögű és tompaszöge lesz, majd egyszerűen eltávolítanak egy-egy pontot ezekből a szögekből, ezáltal az összeset megszüntetik.

A bizonyítási ötlet rövid leírása

Erdős és Furedi bizonyítása az volt, hogy az egységkockából véletlenszerűen és egymástól függetlenül kiválasztottak olyan pontokat , ahol és bebizonyították, hogy ilyen választással pozitív a valószínűsége annak, hogy közöttük csak tompa vagy elfajult háromszögek lesznek. $2n$ $\left\lkapcsos zárójel {0,1}\jobbra\rkapcsos zárójel ^{d}$ $n=\left\lfloor {{\frac {1}{2}}{\left({\frac {2}{\sqrt {3}}}\right)}^{d}}\right\ rfloor$ $n$

Egy pont véletlenszerű kiválasztása itt azt jelenti, hogy a Bernoulli-séma szerint generálják azt a valószínűséget , hogy a pont egyik vagy másik koordinátáján egy vagy nulla keletkezik, függetlenül a többi koordinátától. $p={\frac {1}{2}}$

A tompa háromszögek számának becslésére a matematikai elvárás linearitási tulajdonságát használtuk. Annak a valószínűsége, hogy a pontok adott hármasa derékszöget alkot, egyenlő - ezt könnyű bizonyítani, ha külön-külön figyelembe vesszük az egyes koordináták hozzájárulását a skalárszorzathoz. Ezt a valószínűséget megszorozva az ilyen hármasok számával, megkapjuk a matematikai elvárás értékét, és ez már a Markov-egyenlőtlenség szerint pozitív valószínűséget ad arra, hogy a valószínűségi változó nem haladja meg azt. $\left({\frac {3}{4}}\right)^{d}$

Erdős-Füredi Állandó fejlesztések

Javítás a módszer megváltoztatása nélkül

Az Erdős-módszer lényegének megváltoztatása nélkül is jobb becslést kaphatunk, ha egy másik számot választunk paraméterként, amely meghatározza, hogy hány véletlenszerű pontot választunk.

Aigner és Ziegler 2003-ban a Proofs from the Book című ismertető könyvében leírták az Erdős-tételt , kijavították ezt a paramétert, és azt kapták, hogy . [6] Ez a legjobb, amit így lehet megszerezni. $f_{\square }(d)\geq 2\left\lfloor {{\frac {\sqrt {6}}{9}}{\left({\frac {2}{\sqrt {3}} }\jobbra)}^{d}}\jobbra\rpadló$

Bizonyíték

A kiválasztott pontok számának Erdős-módszere megállapította, hogy ezek között legalább egyszer nincs több hegyesszög. $k$ $3{\binom {k}{3}}{\left({\frac {3}{4}}\right)}^{n}\leq {\frac {k^{3}}{2 }}{\left({\frac {3}{4}}\right)}^{d}$

Ez garantálja egy ponthalmaz létezését derékszögek vagy tompaszögek nélkül. $h(k)=k-{\frac {k^{3}}{2}}{\left({\frac {3}{4}}\right)}^{d}$

Ha vesszük a deriváltot, és optimalizáljuk ezt a függvényt -re vonatkoztatva , akkor azt kapjuk $k$

h'(k)=1-{\frac {3}{2}}{\left({\frac {3}{4}}\right)}^{d}k^{2}

k^{2}={\frac {2}{3}}{\left({\frac {4}{3}}\right)}^{d}

k_{best}={\sqrt {\frac {2}{3}}}{\left({\frac {2}{\sqrt {3}}}\right)}^{d}

h(k_{best})={\left({\frac {2}{\sqrt {3}}}\right)}^{d}{\sqrt {\frac {2}{3}} }\left({1-{\frac {2}{3}}\cdot {\frac {1}{2}}}\right)={\left({\frac {2}{\sqrt {3} }}\right)}^{d}{\sqrt {\frac {2}{3}}}\cdot {\frac {2}{3}}={\frac {2{\sqrt {6}}} {9}}{\left({\frac {2}{\sqrt {3}}}\right)}^{d}

Bevan (2006)

2006-ban D. Bevan a becslést -ra javította . [7] $f(d)\geq 2\left\lfloor {{\frac {1}{3}}{\left({\frac {2}{\sqrt {3}}}\right)}^{d +1}}\jobbra\rpadló$

Konstrukciójának pontjai azonban nem egy egységkocka csúcsai voltak, így nem javította a becslést. $f_{\square }(d)$

A bizonyítási ötlet rövid leírása

Bevan konstrukciójában minden kiválasztott véletlenszerű ponthoz egy nagyon rövid véletlen vektort adtunk (mindegyiknek megvan a maga sajátja), folyamatosan és egyenletesen elosztva a -dimenziós kockában néhány kellően kicsi számára . $d$ ${\displaystyle [-\varepsilon ;\varepsilon ]^{d))$ $\varepsilon$

Bevan számos lemmát vezetett be, amelyek azt mutatják, hogy az egyenletes és szimmetrikus eloszlású valószínűségi változókban (amit új valószínűségi változónak tekintünk) bizonyos polinomok valószínűsége nem kisebb, mint . Ezek a lemmák lehetővé tették annak kimutatását, hogy az esetek több mint felében a további vektorokkal történő eltolódás nem élesíti ki az előtte derékszögben elhelyezkedő pontok közötti szöget (hiszen a skaláris szorzat változása, ami kvantitatív a szög élességének mutatója, pontosan polinomokon keresztül fejeződik ki további vektorok koordinátáiban). ${\frac {1}{2))$

Mindez lehetővé tette a nem hegyesszögek számának matematikai elvárására vonatkozó becslés megerősítését, és megmutatta, hogy a véletlenszerűen kiválasztott pontok között csak nem hegyesszögek lehetnek. $k$ ${\frac {3}{2}}{\binom {k}{3}}{\left({\frac {3}{4}}\right)}^{n}$

Ezenkívül Bevan számos eredményt kapott kis méretekre , amelyek eredményeként a Danzer-Grünbaum sejtést cáfolták a címen . [nyolc] $d$ $d\geq 7$

Buchok (2009)

2009-ben Larisa Buchok, anélkül, hogy Erdős, Furedi és Bevan pontszerzési módszerét megváltoztatta volna, pontosabban számolta ki a nem éles kanyarokban érintett pontok törléséből származó veszteségeket. Kiderült, hogy ez lehetővé teszi a következő becsléseket [8] :

f_{\square }(d)\geq {\frac {3}{2}}\left\lfloor {{\frac {11{\sqrt {66}}}{243}}{\left({ \frac {2}{\sqrt {3}}}\right)}^{d}}\right\rfloor

f(d)\geq {\frac {3}{2}}\left\lfloor {{\frac {22{\sqrt {33}}}{243}}{\left({\frac {2 }{\sqrt {3}}}\right)}^{d}}\right\rfloor

A bizonyítási ötlet rövid leírása

Mindenekelőtt Buchok egy tetszőlegesen generált ponthalmazt figyelembe véve kiemelte belőle azokat a tompaszögű háromszögleteket, amelyek (pontok szerint) nem metszik egymást. Nyilvánvalóan kevés ilyen háromszög van - legalább háromszor kevesebb, mint az összes pont.

A többi háromszög „átlapolásuk” miatt lehetővé teszi nagyszámú háromszög eltávolítását egyetlen pont eltávolításával. Ha ennek során új háromszögek keletkeznek, amelyek nem metszik egymást a többivel (melyek mindegyikét külön ponton keresztül kell eltávolítani), akkor kiderül, hogy számukat kompenzálja a több háromszögben lévő csúcs eltávolításával kapott erősítéssel , amelyek eltávolítása valójában nem teszi őket átfedővé.

Mindez lehetővé teszi, hogy tudva, hogy a pontok között vannak nem hegyesszögek, hegyesszögű ponthalmazt alkothatunk , ellentétben a triviális becsléssel, amikor csak pontokat választunk. $k$ $s$ $k-{\frac {k}{3}}-{\frac {3}{4}}\left({s-{\frac {k}{3}}}\right)={\frac {11}{12}}k-{\frac {3}{4}}s$ $ks$

Buchok (2009/2010)

2010-ben a Buchok két módszert tett közzé az eredmények korábbi egyenlőtlenségének javítására:

f(d)\geq {\frac {3}{2}}\left\lfloor {{\frac {11{\sqrt {165}}}{243}}{\left({\frac {2 }{\sqrt {3}}}\right)}^{d}}\right\rfloor

A bizonyítási ötlet rövid leírása

Ebben a munkában Buchok ötvözi a pontok fix halmazból történő kiválasztását és a pontok egy kocka csúcsaitól való kis eltérésének hozzáadását.

Az Erdős és Furedy módszerhez hasonlóan Buchok véletlenszerűen választ ki pontokat, és mindegyik koordináta egymástól függetlenül, a Bernoulli-séma szerint, de nem valószínűségekkel

P(v_{i}=0)=P(v_{i}=1)={\frac {1}{2))

de sok lehetőséggel, valószínűségekkel

$P(v_{i}=0)=P(v_{i}=1)=P(v_{i}=-\varepsilon _{i})=P(v_{i}=1+\varepszilon _{i})={\frac {1}{4}}$

ahol kellően kis számok vannak (minden koordinátához külön szám), amelyek kielégítik a feltételeket ${\displaystyle \varepsilon _{1},\dots ,\varepsilon _{n))$

\sum \limits _{i=1}^{d}{(\varepsilon _{i}+{\varepsilon _{i}}^{2})}<1

\varepsilon _{j}^{2}>\sum \limits _{i=j+1}^{d}{(\varepsilon _{i}+{\varepsilon _{i))^{2 })},1\leq j\leq d-1

Mindez lehetővé teszi, hogy a kőzettermék egyik vagy másik koordinátájának megváltoztatására szolgáló 64 lehetőség felsorolásával csökkentsük annak valószínűségét, hogy néhány három pont nem hegyesszöget képez, ellentétben az Erdősben található szabványos szöggel. -Füredy módszerrel, és ennek megfelelően csökkenti a nem hegyesszögek számának matematikai elvárását. ${\frac {2}{5}}{\left({\frac {3}{4}}\right)}^{d}+{\frac {3}{5}}{\left( {\frac {7}{16}}\right)}^{d}$ ${\left({\frac {3}{4}}\right)}^{d}$

Ezt követően a Butchok technikával eltávolítható a tompa sarkok korábbi munkáiból, amivel teljes a bizonyítás.

f(d)\geq {\frac {2}{3}}\left\lfloor {{\sqrt {2}}{\left({\frac {2}{\sqrt {3}}}\ jobb)}^{d}}\jobbra\rpadló

A bizonyítási ötlet rövid leírása

Ugyanezen munka első módszerétől eltérően, amely a véletlen pontok kiválasztásának algoritmusának megváltoztatásából állt, a második módszer az Erdős-Füredy séma szerint a szokásos választást kínálta minden pont minden koordinátájára való valószínűséggel. A fő nyereség ebben az esetben a pontok "okos" kivonása volt a legjobb kombinációban (a legkevesebb tompaszög mellett). $P(v_{i}=0)=P(v_{i}=1)={\frac {1}{2))$

Az első módszerhez hasonlóan a pontokat egy kis fix hosszúságú vektorral mozgattuk el (elég elvenni ) a kockától, de csak egy koordináta mentén, és szigorúan attól függően, hogy van-e más tompaszög egy adott központi ponthoz. egy tompaszög, amelyre oldalpont (vagyis, mint Buchok első művében, a derékszögű háromszögeket metszőkre és nem metszőkre osztották fel, de kicsit másképp elemezték, mint az első műben). $\varepsilon >0$ $\varepsilon <{\frac {1}{4))$

Pontosabban, a legjobb kombináció minden pontját négy osztályba osztották a tulajdonságok elégedettsége szerint:

$Q_1$ : minden olyan szög, amelynek egy adott pontban egy csúcsa van, hegyesszögű;
$Q_{2}$ : egy pont legalább egy derékszögű csúcs, és minden olyan hegyesszög, amelynek ebben a pontban van csúcsa, hegyesszögű háromszögekhez tartozik;
$Q_{3}$ : egy pont egy derékszögű háromszögnek legalább egy derékszögű és pontosan egy hegyesszögű csúcsa;
${\displaystyle Q_{4))$ : a pont legalább egy derékszögű és legalább két hegyesszögű derékszögű háromszög csúcsa.

A tulajdonságnak megfelelő pontokat egyszerűen eltávolítottuk a halmazból (mivel nem lehet sok belőlük), a többiek koordinátáit pedig a fent leírtak szerint megváltoztattuk. ${\displaystyle Q_{4))$

Az első módszerhez hasonlóan a 64 lehetőség táblázatának teljes keresése egy vagy másik koordinátának a skaláris szorzathoz való hozzájárulására lehetővé tette annak bizonyítását, hogy a koordináták ezen változásai után nem lesz derékszög vagy tompaszög háromszögek a készletben.

A második eredmény igazolása legkésőbb 2009-ben megtörtént, mivel egy e témában készült felmérésben szerepel. [9] [10]

Valószínűségi séma javítása hipergráfokon keresztül (Ackerman és Ben-Zvi, 2008/2009)

Míg más matematikusok az Erdős-módszer elemi fejlesztésén dolgoztak, Eyjal Ackerman és Oren Ben-Zvi 2009-ben egymástól függetlenül publikált egy 2008-ban szerzett bizonyítékot egy olyan állandó létezésére , $c>0$

f_{\square }(d)\geq c{\sqrt {d}}{\left({\frac {2}{\sqrt {3}}}\right)}^{d}

Az Erdős-Füredy lap óta ez volt a becslés első aszimptotikus javítása .

A bizonyítás mindössze egy oldalt foglalt el, és abból állt, hogy az Erdős-Füredy konstrukcióra egy korábban bizonyított algoritmikus lemmát alkalmaztak a hipergráf független halmazának méretére , speciális feltételek mellett. [tizenegy]

A bizonyítási ötlet rövid leírása

Ackerman és Zvi a lemma egy speciális esetét használta Bertram-Kretzberg és Lefmann felméréséből a független halmazok hipergráfokban történő megtalálásának algoritmikus vonatkozásairól. [12] A vizsgált konkrét eset a következőket mondta ki:

Legyenek adottak az állandók . $c,\varepsilon >0$

Legyen egy hipergráf, amelynek minden éle három csúcsból áll, amely csúcsokat tartalmaz, és csúcsok átlagos foka nem haladja meg a -t , ahol a . $H$ $n$ $t^{2}$ $t\to\infty$ $n\to\infty$

A típusélpárok száma (egyfajta "ciklusok" a hipergráf értelmében) ne haladja meg a -t . $\left({\left\lkapcsos zárójel {a,b,c}\jobbra\rkapcsos zárójel ,\left\lkapcsos zárójel {a,b,d}\jobbra\rkapcsos zárójel }\jobbra)$ ${\displaystyle cnt^{3-\varepsilon ))$

Ekkor polinomiális időben egy független méretű csúcshalmazban találhatunk $n$ $H$ $\Omega \left({\frac {n{\sqrt {\log t}}}{t}}\jobbra)$

A szerzők az Erdős-Fyuredi konstrukciót alkalmazták anélkül, hogy a pontkiválasztási algoritmuson bármilyen módon változtattak volna. De a nem hegyes háromszögek számának átlagával együtt kiszámolták a ciklusok számának átlagát is (a fent említett értelemben) egy hipergráfban, amelynek élei derékszöget vagy tompaszöget képező pontok hármasainak felelnek meg (ezt számítják ki) az átlag linearitásán keresztül, ugyanúgy, mint a tompaszögek száma, de nem a pontok hármasait, hanem a négyeseket figyelembe véve).

Független ponthalmaz egy ilyen hipergráfban csak az a halmaz lesz, amelyik nem tartalmaz tompa háromszögeket, és a paraméterek megválasztásával megvan a mérete. $n=c_{1}{\left({\frac {2}{\sqrt {3}}}\right)}^{{\frac {101}{100}}d},t=c_{ 2}{\left({\frac {2}{\sqrt {3}}}\right)}^{\frac {d}{100}}$ $\Omega \left({{\sqrt {d}}{\left({\frac {2}{\sqrt {3}}}\right)}^{d}}\right)$

A Diploma Alapítvány fejlesztése (Harangi, 2011)

Harangi 2011-ben egy exponenciális becslést igazolt jobb kitevőbázissal, vagyis bebizonyította egy olyan állandó létezését , $c>0$

f(n)\geq c{\left({\sqrt[{10}]{\frac {144}{23))}\right)}^{d}>c\cdot 1.201^{d}

Bizonyítéka volt az Erdős-Füredi konstrukció módosítása is. [13]

Az első konkrét terv (Zakharov, 2017)

2017. április 30-án Dmitrij Zakharov, aki a 10. osztályban tanul, és Andrej Raigorodsky tanítványa , kiadott egy explicit (nem valószínűségi) konstrukció előnyomatát, amely csak hegyesszögeket képező pontokból állt. $2^{\left\lceil {\frac {d}{2}}\right\rceil }$

Zaharov terve nem az Erdős-módszer továbbfejlesztése volt, hanem egy új, egyszerű, egy oldalon leírt ötletet használt. [14] [3]

Ugyanezen év novemberében a bizonyítást a Discrete & Computational Geometry publikálták . [tizenöt]

A bizonyítási ötlet rövid leírása

Zakharov módszere az volt, hogy ismétlődően összeállított egy pontkészletet . Ebben az esetben az átmenet a mérettér halmazáról a mérettér halmazára történt $d$ $d+2$

A kocka (vagy paralelepipedon) felépítésének elvét vették alapul, amikor az összes pontot "lemásolják", és a másolatokat egy új dimenzió mentén áthelyezik egy bizonyos távolságra, merőlegesen az előző konstrukció pontjai közötti összes szegmensre (és általában az előző térben lévő összes egyeneshez). Ez megduplázná a pontok számát, és csak kis mértékben változtatná meg a rendelkezésre álló szögeket (azoknál a szögeknél, amelyek pontjai különböző másolatokhoz tartoznak) (a skaláris szorzat legfeljebb az új dimenzió eltolódásának négyzetével arányos mértékben változik). Azonban egy ilyen konstrukciónál a forma derékszögei keletkeznek , ahol és egy pont különböző másolatai. $\angle {v_{2}v_{1}w_{1}}$ $v_{1}$ $v_{2}$

Hogy megszabaduljon a derékszögektől, Zaharov egyszerre két új dimenzió mentén hajtott végre eltolást egy azonos hosszúságú, de különböző irányú vektorral, és az egyes pontok mindkét másolata az új dimenziók mentén mozgott, ellentétben a kocka építésével. , amikor az előző konstrukcióból származó összes pont a korábbi tér határain belül marad. Mindez lehetővé tette a kialakuló "függőleges" (a bevezetésre kerülő új dimenzió mentén kiterjesztett) szegmensek enyhén "ferdítését" a pontok között, hogy megszabaduljon azoktól a szögektől, amelyeket azokkal a szegmensekkel alkotnak, amelyek kizárólag egy kisebb térben helyezkednek el. dimenzió.

Pontosabban, ha egy halmaz derék- és tompaszögek nélkül van, Zakharov minden ponthoz választ egy kétdimenziós vektort , amelynek hossza kellően kicsi (és ami fontos, hogy mindenre azonos), és olyan módon, hogy az érvényes legyen minden különbözőre. . Ekkor kellően kis hosszúságú vektorok esetén be lehet bizonyítani, hogy a beállított pontok $S$ ${\displaystyle {\mathbb {R} }^{d))$ $x\in S$ $\phi (x)=\left({\alpha (x),\beta (x)}\jobbra)$ $\phi (x)\not =\pm \phi (y)$ $x,y\in S$ $\phi(x)$

S'=\left\lkapcsos zárójel {(x_{1},\pontok ,x_{d},\alpha (x),\beta (x)):x\in S}\right\rbrace \cup \ bal\lkapcsos zárójel {(x_{1},\pontok ,x_{d},-\alpha (x),-\beta (x)):x\in S}\jobbra\rkapcsos zárójel

szintén nem alkotnak derékszöget vagy tompaszöget (és az a tény, hogy ezek a halmazok nem metszik egymást, nyilvánvaló a konstrukcióból ). $\phi(x)$

Ez bizonyítja az ismétlődést és indukcióval a teljes tételt. $f(d+2)\geq 2f(d)$

Becslés a Fibonacci-számokkal (Zakharov, 2017)

2017 júliusában Zakharov kiadott egy nyomtatványt, amely ezt bizonyította

f(d)>F_{n}>c{\left({\frac {1+{\sqrt {5}}}{2}}\right)}^{d}>c\cdot 1,618^ {d}

ahol a -edik Fibonacci-szám , és abszolút állandó. [16] A második egyenlőtlenség Binet képletéből következik . $F_{n}$ $n$ $c>0$

A bizonyítási ötlet rövid leírása

Az ötlet ugyanaz volt, mint az első munkában - a pontok másolása az azt követő eltolással egy kellően kicsi kétdimenziós vektorral új dimenziókban.

Most azonban egy -dimenziós halmazban lévő pontok kombinációját vettük figyelembe, amelyek között a pontok (a lehetséges maximális szám) egyetlen dimenziós hipersíkban helyezkednek el . Ennek megfelelően a másolási és eltolási műveletet csak nekik hajtották végre, és az új dimenziókat ortogonálisan vezették be , így a művelet eredményeként az összes dimenzió csak eggyel nőtt, a pontok számára pedig egy rekurzív kifejezés. megszerezték $d$ $f(d-1)$ ${\displaystyle H\subset {\mathbb {R} }^{d))$ $d-1$ $H$

f(n+1)=f(n)+f(n-1)

Maximális rendelési becslés (Gerencher és Harangi 2017)

Zaharov művének megjelenése arra késztette a kísérleteket, hogy jobb ellenpéldákat találjanak az alacsony méretekre. Feltételezték, hogy ezután hegyesszögű halmazokra állítottak példákat, bizonyítva, hogy $f(d)\geq 2^{d-1}+1$

f(4)\geq 9

f(5)\geq 17

A példák felépítésénél a -dimenziós kocka pontjainak enyhe ingadozása volt ben , beleértve az utolsó koordinátát is, amely nem kapcsolódik a kocka -dimenziós alteréhez. [17] $(d-1)$ ${\displaystyle {\mathbb {R} }^{d))$ $(d-1)$

Ez az elképzelés könnyen általánosítható magasabb dimenziókra, amit Gerincher és Harangi meg is tett 2017 szeptemberében, és publikált egy cikket, amely bizonyítja az eredményt bármely . A grizzly megoldásához hasonlóan ezek eredménye is lehetővé teszi, hogy adott méretű hegyesszögű halmazt építsünk a kocka csúcsaihoz tetszőlegesen közeli pontokból (legfeljebb távolságra tőlük ). Ebben a cikkben is szó esett a fórum vitájáról. [tizennyolc] $f(d)\geq 2^{d-1}+1$ $d$ $\varepsilon >0$

A bizonyítási ötlet rövid leírása

A bizonyítás formalizálására két lemmát használtak:

a -dimenziós kocka egyik pontjának tetszőlegesen kis távolságra mozgatásával az ezt a pontot tartalmazó összes sarkot hegyessé teheti (a kocka tulajdonságai miatt eltűnnek azok a szögek, amelyeknél a pont oldalirányú volt, és azok a sarkok, ahol ez pont középső, ne váljanak tompavá a -edik koordináta mentén további ponteltolás miatt); $(d-1)$ $d$
Bármely véges ponthalmazra létezik olyan, hogy bármelyik pontot bármely irányba tolva kisebb távolsággal , a halmaz pontjai által alkotott hegyesszögek nem lesznek derékszögűek vagy tompaszögek. Ezt az állítást úgy bizonyítjuk, hogy ebből a halmazból kivesszük a pontok közötti szögszegmensek összes pozitív skalárszorzatának minimumát. Mivel a "legrosszabb" szög skaláris szorzata továbbra is pozitív lesz, a változásnak elfogadható határai vannak. $\varepsilon >0$ $\varepsilon$

Ezután a kocka minden csúcsához a következőket hajtottuk végre:

kiderült, hogy mely már meglévő éles sarkok nem sérülnek meg; $\varepsilon$
az adott csúcsot egy kisebb hosszúságú vektorral a kívánt irányba mozgattuk, így a vele bezárt tompaszögek élessé válnak. $\varepsilon$

A végére került még egy pont, ami a -edik koordináta mentén nagyon távol volt a kockától, a többi mentén pedig egybeesett a kocka középpontjával. Az e pont által a többivel alkotott szögek is élesnek bizonyultak. $d$

Jegyzetek

↑ 1 2 The Michigan Mathematical Journal, Volume 4, Issue 3 (1957), 291-300, Paul Erdős, Néhány megoldatlan probléma Archivált 2018. június 3-án a Wayback Machine -nál , p. 296, 19. feladat
↑ The American Mathematical Monthly, Vol. 55, sz. augusztus 7. — 1948. szept.; Paul Erdos, Problémák a 4305-4309 megoldáshoz Archiválva : 2018. augusztus 28. a Wayback Machine -nál , p. 431, 4306. feladat
↑ 1 2 3 Raigorodsky A.M. Hegyesszögű halmazok // Kvant. - 2018. - Kiadás. 3 . — P. 10–13 . (Orosz)
↑ P. Erdos, Z. Furedi. A legnagyobb szög n pont között a d-dimenziós euklideszi térben // Kombinatorikus matematika.--Marseille-Luminy, 1981.--P. 275-283; Észak-Hollandia matematika. Stud.--75.--North-Holland, Amszterdam, 1983 (elérhetetlen link) . Letöltve: 2018. március 19. Az eredetiből archiválva : 2018. augusztus 28.. (határozatlan)
↑ Raygorodsky, 2009 , p. nyolc.
↑ Aigner, 2006 , p. 93-94.
↑ D. Bevan, "Csak akut szögeket meghatározó pontok és néhány kapcsolódó színezési probléma", Electron. J. Combin., 13:1 (2006), 24 p. . Letöltve: 2018. március 19. Az eredetiből archiválva : 2018. május 2. (határozatlan)
↑ 1 2 L. V. Buchok, „Acute Danzer-Grunbaum Triangles”, Uspekhi Mat. Nauk, 2009, 64. kötet, 3. szám (387), 181-182. oldal . Letöltve: 2018. március 19. Az eredetiből archiválva : 2018. június 3. (határozatlan)
↑ L. V. Buchok, „A Danzer-Grunbaum probléma becsléseinek két új megközelítéséről”, Mat. jegyzetek, 2010, 87. kötet, 4. szám, 519-527 . oldal . Letöltve: 2018. március 19. Az eredetiből archiválva : 2018. május 12. (határozatlan)
↑ Raygorodsky, 2009 , p. 21.
↑ Eyal Ackerman, Oren Ben-Zwi, "A csak hegyesszögeket meghatározó pontkészletekről", European Journal of Combinatorics, 30. kötet, 4. szám, 2009. május, 908-910. oldal
↑ Claudia Bertram-Kretzberg, Hanno Lefmann, "The Algorithmic Aspects of Uncrowded Hypergraphs", SIAM J. Comput., 29(1), 201–230
↑ Viktor Harangi, "Acute Sets In Euclidean Spaces", SIAM J. Discrete Math., 25(3), 1212-1229 . Letöltve: 2018. március 19. Az eredetiből archiválva : 2019. május 31. (határozatlan)
↑ arXiv:1705.01171 D. Zakharov, "Akut halmazok" . Letöltve: 2018. március 19. Az eredetiből archiválva : 2018. augusztus 28.. (határozatlan)
↑ Dmitriy Zakharov, "Akut halmazok", "Diszkrét és számítási geometria" . Letöltve: 2018. március 19. Az eredetiből archiválva : 2018. június 10. (határozatlan)
↑ D. Zakharov, "Akut halmazok" . Letöltve: 2018. március 19. Az eredetiből archiválva : 2018. augusztus 28.. (határozatlan)
↑ Továbbfejlesztett (?) Erdős megoldás hegyes háromszögekre; ennek az oldalnak egy másolata csatolva van az arXiv -hez : 0906.0290
↑ arXiv:1709.03411, Gerencsér Balázs, Harangi Viktor, "Exponenciálisan optimális méretű akut halmazok" . Letöltve: 2018. március 19. Az eredetiből archiválva : 2018. augusztus 28.. (határozatlan)

Irodalom

Raigorodsky, A. M. Danzer-Grünbaum hegyesszögű háromszögek . - M. : MTSNMO, 2009. - 31 p. — ISBN 978-5-94057-539-9 . Archiválva : 2018. május 8. a Wayback Machine -nál
Aigner M. Ziegler G. Bizonyítékok a könyvből. A legjobb bizonyíték Eukleidész korától napjainkig. – Mir, 2006.