Szemeredi-Trotter teorem

Szemeredi-Trotter-sætningen er et resultat af kombinatorisk geometri . Sætningen siger, at givet n punkter og m linjer i en plan, er antallet af incidenser (dvs. antallet af punkt/linje-par, hvor et punkt ligger på en linje)

og denne binding kan ikke forbedres.

En tilsvarende formulering af sætningen er som følger. Givet n punkter og et heltal k > 2 er antallet af linjer, der går gennem mindst k punkter,

Szemeredi og Trotters [1] originale bevis var komplekst og brugte en kombinatorisk teknik kendt som celledeling . Senere opdagede Szekei et meget enklere bevis ved at bruge skæringsnummeruligheden for grafer [2] (se nedenfor).

Szemeredi-Trotter-sætningen har flere konsekvenser, herunder Becks -sætning i incidensgeometri .

Bevis for den første erklæring

Vi kan kassere linjer med to eller færre punkter, da de maksimalt kan give 2 m indfald. Vi kan således antage, at enhver linje indeholder mindst tre punkter.

Hvis en linje indeholder k punkter, så indeholder den k − 1 linjestykker, der forbinder to af de n punkter. Især vil linjen indeholde mindst k /2 sådanne segmenter, da vi antog k ≥ 3 . Tilføjer vi alle sådanne forekomster langs alle m linjer, finder vi, at antallet af segmenter opnået på denne måde er mindst lig med halvdelen af ​​antallet af alle forekomster. Hvis vi angiver antallet af sådanne segmenter med e , er det tilstrækkeligt at vise det

Betragt nu en graf dannet af n punkter som hjørner og e segmenter som kanter. Da hvert segment ligger på en af ​​de m linjer og højst to linjer skærer hinanden i ét punkt, overstiger antallet af skæringspunkter i denne graf ikke m 2 . Fra skæringstallets ulighed konkluderer vi, at enten e ≤ 7,5 n eller m 2 ≥ e 3 / 33,75 n 2 . Under alle omstændigheder, e ≤ 3,24( nm ) 2/3 + 7,5 n , og vi får den nødvendige grænse

Bevis for den anden formulering

Da ethvert punktpar højst kan forbindes med én linje, kan der højst være n ( n − 1)/2 l linjer, der kan forbinde k eller flere punkter, da k ≥ 2 . Denne grænse beviser sætningen for lille k (f.eks. hvis k ≤ C for en absolut konstant C ). Det giver således kun mening at overveje tilfælde, hvor k er stor, f.eks. k ≥ C.

Antag, at der er m linjer, som hver indeholder mindst k punkter. Disse linjer danner mindst mk forekomster, og så har vi ved den første variant af Szemerédy-Trotter-sætningen

og mindst én ligestilling fra eller er opfyldt . Vi forkaster den tredje mulighed, fordi vi antog, at k er stor, så de to første forbliver. Men i begge tilfælde, efter simple algebraiske beregninger, opnår vi , som er påkrævet.

Optimalitet

Hvis konstante faktorer ikke tages i betragtning, kan Szemeredy-Trotter-incidensgrænsen ikke forbedres. For at se dette skal du overveje for ethvert positivt heltal N ∈ Z + sættet af punkter i heltalsgitteret

og et sæt linjer

Det er klart, at og . Da hver linje er indfaldende til N punkter (dvs. én gang for hver ), er antallet af forekomster lig med , hvilket svarer til den øvre grænse [3] .

Generalisering for R d

En generalisering af dette resultat for en vilkårlig dimension Rd blev fundet af Agaval og Aronov [4] . Givet et sæt S indeholdende n punkter og et sæt H indeholdende m hyperplaner, er antallet af forekomster af punkter fra S og hyperplaner fra H afgrænset ovenfor af tallet

Tilsvarende er antallet af hyperplaner i H , der indeholder k eller flere punkter, afgrænset ovenfor af tallet

Edelbrunner-konstruktionen viser, at grænsen er asymptotisk optimal [5] .

Soimoshi og Tao opnåede en næsten nøjagtig øvre grænse for antallet af forekomster mellem punkter og algebraiske varianter i højdimensionelle rum. Deres bevis bruger polynomiets sandwich-sætning [6] .

Ansøgninger

Szemeredy-Trotter-sætningen finder mange anvendelser i additiv [7] [8] [9] og aritmetisk kombinatorik (for eksempel for at bevise sum-produktsætningen [10] ).

Noter

  1. ↑ Szemerédi, Trotter, 1983 , s. 381-392.
  2. ↑ Szekely, 1997 , s. 353-358.
  3. ↑ Tao, 2011 .
  4. ↑ Agarwal, Aronov, 1992 , s. 359-369.
  5. ↑ Edelsbrunner, 1987 .
  6. ↑ Solymosi, Tao, 2012 .
  7. ↑ Tomasz Schoen, Ilya Shkredov, "Om mængder af konvekse sæt" . Hentet 19. november 2018. Arkiveret fra originalen 12. juni 2018.
  8. ↑ A. Iosevich, S. Konyagin, M. Rudnev og V. Ten, "Om kombinatorisk kompleksitet af konvekse sekvenser", 19. juli 2004 . Hentet 19. november 2018. Arkiveret fra originalen 12. juni 2018.
  9. ↑ Elekes, Nathanson, Ruzsa, "Konveksitet og sumsets" (link ikke tilgængeligt) . Hentet 19. november 2018. Arkiveret fra originalen 12. juni 2018. 
  10. ↑ G. Elekes, Om antallet af summer og produkter, Acta Arith. 81 (1997), 365-367. . Dato for adgang: 19. november 2018. Arkiveret fra originalen 7. februar 2019.

Litteratur

Yderligere læsning