Szemedi-Trotter lause

Szemeredi-Trotter -lause on kombinatorisen geometrian tulos . Lauseen mukaan annetuilla n pisteillä ja m viivalla tasossa esiintymien lukumäärä (eli piste/viiva-parien määrä, jossa piste on suoralla) on

O\left(n^{\frac {2}{3}}m^{\frac {2}{3}}+n+m\right),

ja tätä rajaa ei voi parantaa.

Vastaava lauseen muotoilu on seuraava. Kun on annettu n pistettä ja kokonaisluku k > 2 , vähintään k pisteen läpi kulkevien viivojen määrä on

O\left({\frac {n^{2}}{k^{3}}}+{\frac {n}{k}}\oikea).

Szemedin ja Trotterin [1] alkuperäinen todistus oli monimutkainen ja käytti kombinatorista tekniikkaa, joka tunnetaan solunjakautumisena . Myöhemmin Szekei löysi paljon yksinkertaisemman todisteen käyttämällä leikkauslukuepäyhtälöä kaavioille [ 2] (katso alla).

Szemeredi–Trotter-lauseella on useita seurauksia, mukaan lukien Beckin lause ilmaantuvuusgeometriassa .

Todiste ensimmäisestä lausumasta

Voimme hylätä viivat, joissa on kaksi tai vähemmän pistettä, koska ne voivat antaa korkeintaan 2 metrin osuman. Siten voimme olettaa, että mikä tahansa suora sisältää vähintään kolme pistettä.

Jos suora sisältää k pistettä, se sisältää k − 1 janaa, jotka yhdistävät kaksi n pisteestä. Erityisesti suora sisältää vähintään k /2 tällaista segmenttiä, koska oletimme k ≥ 3 . Kun lasketaan yhteen kaikki tällaiset esiintymät kaikilla m viivoilla, havaitaan, että tällä tavalla saatujen segmenttien lukumäärä on vähintään puolet kaikkien esiintymisten lukumäärästä. Jos merkitsemme tällaisten segmenttien lukumäärää e :llä, se riittää osoittamaan sen

e=O\left(n^{\frac {2}{3}}m^{\frac {2}{3}}+n+m\right).

Tarkastellaan nyt kuvaajaa , jonka muodostaa n pistettä kärkeinä ja e janat reunoina. Koska kukin jana on yhdellä m suorasta ja kaksi suoraa leikkaa enintään yhdessä pisteessä, tämän kaavion leikkauspisteiden määrä ei ylitä m 2 . Leikkauslukuepäyhtälöstä päätämme , että joko e ≤ 7,5 n tai m 2 ≥ e 3 / 33,75 n 2 . Joka tapauksessa e ≤ 3,24( nm ) 2/3 + 7,5 n ja saamme vaaditun rajan

e=O\left(n^{\frac {2}{3}}m^{\frac {2}{3}}+n+m\right).

Todiste toisesta formulaatiosta

Koska mikä tahansa pistepari voidaan yhdistää enintään yhdellä suoralla, voi olla enintään n ( n − 1)/2 l suoraa, jotka voivat yhdistää k tai useampia pisteitä, koska k ≥ 2 . Tämä raja todistaa lauseen pienelle k :lle (esimerkiksi jos k ≤ C jollekin absoluuttiselle vakiolle C ). Siksi on järkevää tarkastella vain tapauksia, joissa k on suuri, sanotaan k ≥ C.

Oletetaan, että on m suoraa, joista jokainen sisältää vähintään k pistettä. Nämä viivat muodostavat ainakin mk - insidenssit, ja sitten Szemerédy–Trotter-lauseen ensimmäisellä muunnelmalla meillä on

mk=O\left(n^{\frac {2}{3}}m^{\frac {2}{3}}+n+m\right),

ja vähintään yksi yhtäläisyys osoitteesta tai täyttyy . Hylkäämme kolmannen mahdollisuuden, koska oletimme, että k on suuri, joten kaksi ensimmäistä säilyvät. Mutta molemmissa tapauksissa yksinkertaisten algebrallisten laskelmien jälkeen saamme , joka vaaditaan. $mk=O(n^{2/3}m^{2/3}),mk=O(n)$ $mk=O(m)$ $m=O(n^{2}/k^{3}+n/k)$

Optimaalisuus

Jos vakiotekijöitä ei oteta huomioon, Szemedy–Trotter-ilmaantuvuusrajaa ei voida parantaa. Nähdäksesi tämän, harkitse mille tahansa positiiviselle kokonaisluvulle N ∈ Z + kokonaislukuhilan pistejoukkoa

P=\left\{(a,b)\in \mathbf {Z} ^{2}\ :\ 1\leq a\leq N;1\leq b\leq 2N^{2}\right\ },

ja joukko rivejä

L=\left\{(x,mx+b)\ :\ m,b\in \mathbf {Z} ;1\leq m\leq N;1\leq b\leq N^{2}\ oikea\}.

On selvää, että ja . Koska jokainen suora osuu N pisteeseen (eli kerran kullekin ), esiintymien lukumäärä on yhtä suuri kuin , mikä vastaa ylärajaa [3] . $|P|=2N^{3}$ $|L|=N^{3}$ $x\in \{1,\cdots ,N\}$ ${\displaystyle N^{4))$

R d :n yleistys

Agaval ja Aronov löysivät tämän tuloksen yleistyksen mielivaltaiselle ulottuvuudelle Rd [4] . Jos joukko S sisältää n pistettä ja joukko H , joka sisältää m hypertasoa, S :stä peräisin olevien pisteiden ja H :n hypertasojen esiintymisten määrä on rajattu edellä numerolla

O\left(m^{\frac {2}{3}}n^{\frac {d}{3}}+n^{d-1}\oikea).

Vastaavasti H :n hypertasojen lukumäärä, jotka sisältävät k tai enemmän pistettä, on yläpuolella numeron rajoittama

O\left({\frac {n^{d}}{k^{3}}}+{\frac {n^{d-1}}{k}}\oikea).

Edelbrunner-konstruktio osoittaa, että raja on asymptoottisesti optimaalinen [5] .

Soimoshi ja Tao saivat lähes tarkan ylärajan esiintymien lukumäärälle pisteiden ja algebrallisten variaatioiden välillä korkeadimensionaalisissa tiloissa. Heidän todistuksessaan käytetään polynomin sandwich-lausetta [6] .

Sovellukset

Szemeredy-Trotter -lause löytää monia sovelluksia additiivisessa [7] [8] [9] ja aritmeettisessa kombinatoriikassa (esimerkiksi summatulolauseen [10] todistamiseksi ).

Muistiinpanot

↑ Szemerédi, Trotter, 1983 , s. 381-392.
↑ Szekely, 1997 , s. 353-358.
↑ Tao, 2011 .
↑ Agarwal, Aronov, 1992 , s. 359-369.
↑ Edelsbrunner, 1987 .
↑ Solymosi, Tao, 2012 .
↑ Tomasz Schoen, Ilja Shkredov, "Kuperien joukkojen summista" . Haettu 19. marraskuuta 2018. Arkistoitu alkuperäisestä 12. kesäkuuta 2018. (määrätön)
↑ A. Iosevich, S. Konyagin, M. Rudnev ja V. Ten, "Convex sekvenssien kombinatorisesta kompleksisuudesta", 19. heinäkuuta 2004 . Haettu 19. marraskuuta 2018. Arkistoitu alkuperäisestä 12. kesäkuuta 2018. (määrätön)
↑ Elekes, Nathanson, Ruzsa, "Kuperuus ja summat" (linkki ei saatavilla) . Haettu 19. marraskuuta 2018. Arkistoitu alkuperäisestä 12. kesäkuuta 2018. (määrätön)
↑ G. Elekes, Summien ja tuotteiden lukumäärästä, Acta Arith. 81 (1997), 365-367. . Käyttöpäivä: 19. marraskuuta 2018. Arkistoitu alkuperäisestä 7. helmikuuta 2019. (määrätön)

Kirjallisuus

Endre Szemerédi, William T. Trotter. Äärimmäiset ongelmat diskreetissä geometriassa // Combinatorica. - 1983. - T. 3 , no. 3-4 . — S. 381–392 . - doi : 10.1007/BF02579194 .
László A. Szekely. Ristikkäiset luvut ja kovat Erdősin ongelmat diskreetissä geometriassa // Kombinatoriikka, todennäköisyys ja laskeminen . - 1997. - T. 6 , no. 3 . — S. 353–358 . - doi : 10.1017/S0963548397002976 .
Terence Tao. Ilmaantuvuuslause korkeammissa ulottuvuuksissa. – 2011.
Pankaj Agarwal, Boris Aronov. Fasettien ja esiintymisten laskeminen // Diskreetti ja laskennallinen geometria . - Springer, 1992. - V. 7 , no. 1 . — S. 359–369 . - doi : 10.1007/BF02187848 .
Herbert Edelsbrunner. 6.5 Alarajat monille soluille // Kombinatorisen geometrian algoritmit . - Springer-Verlag, 1987. - ISBN 3-540-13722-X .
J. Solymosi, Terence Tao. Insidenssilause korkeammissa ulottuvuuksissa // Diskreetti ja laskennallinen geometria . - 2012. - T. 48 , no. 2 . - doi : 10.1007/s00454-012-9420-x .

Lue lisää

Fedor Nilov, Aleksanteri Poljanski, Nikita Poljanski Kansainvälisen kaupunkien matemaattisen turnauksen 26. kesäkonferenssi (02.8.2014-11.8.2014). - Kaliningrad-Ushakovo, 2014.