Beckin lause (geometria)

Katso Beckin lause luokkateoriassa (kaima), katso artikkeli Beck's Monadizability Theorem

Beckin lause on yksi useista kombinatorisen geometrian tuloksista , joista kaksi on annettu alla. Molemmat lauseet esiintyivät yhdessä joidenkin muiden tärkeiden lauseiden kanssa Joseph Beckin tunnetussa artikkelissa [1] . Alla kuvatut kaksi tulosta koskevat tason pistejoukon määrittelemien viivojen alarajoja . (Sanomme, että mikä tahansa suora, joka yhdistää vähintään kaksi joukon pistettä, määritellään pistejoukolla.)

Erdős-Beckin lause

Erdős-Beckin lause on muunnos L.M.:n klassisesta tuloksesta. Kelly ja W.O.J. Moser [2] n pisteen konfiguraatioista , joista enintään n − k ovat kollineaarisia jollekin luvulle 0 < k < O (√ n ). He osoittivat, että jos n on riittävän suuri k :n suhteen , niin konfiguraatio sisältää vähintään kn − (1/2)(3 k + 2)( k − 1) riviä [3] .

Elekes ja Csaba Toz huomasivat, että Erdős-Beckin lause ei helposti ulotu korkeampiin ulottuvuuksiin [4] . Otetaan esimerkiksi joukko 2 n pistettä R 3 :ssa , joka sijaitsee kahdella leikkaavalla suoralla . Oletetaan, että kumpikin näistä kahdesta suorasta sattuu n pisteeseen. Tämä kokoonpano kattaa vain 2 n tasoa. Siten hypoteesin triviaali laajentaminen Rd :n pistejoukkoon ei riitä halutun tuloksen saamiseksi.

Erdős ilmaisi tuloksen ensin oletuksena ja osoitti Beckin lauseen [5] .

Lauseen lause

Olkoon S joukko n pistettä tasossa. Jos yksikään yli n − k pisteestä ei ole samalla suoralla jollain 0 ≤ k < n − 2, niin on Ω( nk ) suoraa, jotka määritetään S :n pisteillä .

Todiste

Beckin lause

Beckin lause sanoo, että tasossa oleva äärellinen pisteiden joukko osuu yhteen kahdesta ääritapauksesta. Yhdessä tapauksessa suuri osa pisteistä on yhdellä viivalla, toisessa tapauksessa tarvitaan suuri määrä viivoja kaikkien pisteiden yhdistämiseen.

Vaikka tätä ei mainita artikkelissa, tämä tulos johtuu Erdős-Beckin lauseesta [6]

Lauseen lause

Lauseen mukaan on kaksi positiivista vakiota C ja K siten, että mille tahansa tason n pistemäärälle yksi seuraavista on tosi:

On suora, joka sisältää vähintään n / C pistettä.
On vähintään viivoja, joista jokainen sisältää vähintään kaksi pistettä. $n^{2}/K$

Beckin alkuperäisessä artikkelissa C :n arvo on 100, eikä vakion K arvoa ole määritelty. C :n ja K :n optimaalisia arvoja ei tunneta.

Todiste

Voit todistaa Beckin lauseen seuraavasti. Olkoon P joukko n pistettä tasossa. Olkoon j positiivinen kokonaisluku . Sanotaan, että joukon P pisteiden A ja B pari on j-kytketty , jos A:n ja B :n yhdistävä suora sisältää pisteestä P pisteisiin ( mukaan lukien A ja B ). $2^{j}$ $2^{j+1}-1$

Szemeredi-Trotter-lauseesta seuraa, että tällaisten juovien lukumäärä on yhtä suuri seuraavasta syystä. Olkoon joukko P koostuva n pisteestä ja joukko L kaikista sellaisista suorista, jotka yhdistävät joukon P pistepareja, jotka sisältävät vähintään joukon P pisteitä . Huomaa, että koska kaksi pistettä ei voi sijaita kahdella erillisellä viivalla. Nyt käytämme Szemedi-Trotter-lausetta , joka tarkoittaa, että P :n ja L :n välisten esiintymistiheysten määrä ei ylitä . Kaikki j-kytkettyjä pisteitä yhdistävät suorat ovat myös L :ssä ja jokaisella viivalla on vähintään incidenssit. Siten tällaisten rivien kokonaismäärä on . $O(n^{2}/2^{3j}+n/2^{j})$ $2^{j}$ ${\displaystyle |L|\cdot {2^{j} \choose 2}\leq {n \choose 2))$ $O(n^{2}/2^{2j}+n)$ $2^{j}$ $O(n^{2}/2^{3j}+n/2^{j})$

Koska jokainen tällainen suora yhdistää pistepareja, näemme, että korkeintaan pisteparit voivat olla j - kytkettyjä. $\Omega (2^{2j})$ $O(n^{2}/2^{j}+2^{j}n)$

Olkoon C nyt riittävän suuri vakio. Summaamalla geometrinen progressio saadaan, että joidenkin j : n epäyhtälön tyydyttävien j -kytkettyjen pisteparien määrä ei ylitä . $C\leq 2^{j}\leq n/C$ $O(n^{2}/b\ C)$

Toisaalta pisteparien kokonaismäärä on . Sitten jos valitsemme C :n riittävän suureksi, voimme löytää ainakin (esimerkiksi) pareja, jotka eivät ole j -kytkettyjä millekään . Nämä pisteet yhdistävät viivat, jotka kulkevat alle 2 C - pisteen tai yli n / C - pisteen läpi. Jos viimeinen väite pätee ainakin yhdelle parille, niin Beckin lauseen ensimmäinen väite pätee. Silloin voidaan olettaa, että kaikki parit on yhdistetty viivoilla, jotka kulkevat alle 2 C - pisteen läpi. Tällainen viiva voi kuitenkin yhdistää enintään pisteparin. Sitten tulee olla vähintään suoria, jotka yhdistävät vähintään kaksi pistettä, jotta lauseen lause saadaan, jos hyväksymme . ${\frac {n(n-1)}{2}}$ $n^{2}/4$ $C\leq 2^{j}\leq n/C$ $n^{2}/4$ $C(2C-1)$ $n^{2}/4C(2C-1)$ $K=4C(2C-1)$

Muistiinpanot

↑ Beck, 1983 , s. 281-297.
↑ William OJ Moser . Haettu 10. syyskuuta 2017. Arkistoitu alkuperäisestä 5. lokakuuta 2016. (määrätön)
↑ Kelly ja Moser, 1958 , s. 210-219.
↑ Elekes, Toth, 2005 , s. 16–21.
↑ Beck, 1983 , s. 281–297 Lause 5.2.
↑ Beckin lause saadaan asettamalla k = n (1 − 1/ C ) ja soveltamalla Erdős-Beckin lausetta.

Kirjallisuus

Beck J. Tason hilaominaisuuksista ja eräistä Diracin, Motzkinin ja Erdősin ongelmista kombinatorisessa geometriassa // Combinatorica. - 1983. - T. 3 . — S. 281–297 . - doi : 10.1007/BF02579184 .

Kelly LM, Moser WOJ Tavallisten rivien määrästä n pisteellä // Kanada. J. Math .. - 1958. - T. 10 . - doi : 10.4153/CJM-1958-024-6 .
Elekes G., Tóth CD Ei-liian rappeutuneiden hypertasojen esiintyminen // Proceedings of the twenty-first year symposium on Computational geometry. - Pisa, Italia: Annual Symposium on Computational Geometry, 2005. - ISBN 1-58113-991-8 .