Szemeredi-Trotters teorem

Szemeredi-Trotter-satsen är ett resultat av kombinatorisk geometri . Satsen säger att givet n punkter och m linjer i ett plan är antalet infalls (dvs antalet punkt/linjepar där en punkt ligger på en linje)

och denna gräns kan inte förbättras.

En ekvivalent formulering av satsen är följande. Givet n punkter och ett heltal k > 2 är antalet linjer som går genom minst k punkter

Szemeredi och Trotters [1] originalbevis var komplext och använde en kombinatorisk teknik som kallas celldelning . Senare upptäckte Szekei ett mycket enklare bevis genom att använda skärningsnummerolikheten för grafer [2] (se nedan).

Szemeredi–Trotter-satsen har flera konsekvenser, inklusive Becks -sats i incidensgeometri .

Bevis på det första påståendet

Vi kan kassera linjer som innehåller två eller färre punkter, eftersom de kan ge maximalt 2 m infall. Vi kan alltså anta att vilken linje som helst innehåller minst tre punkter.

Om en linje innehåller k punkter, så innehåller den k − 1 linjesegment som förbinder två av de n punkterna. I synnerhet kommer linjen att innehålla åtminstone k /2 sådana segment, eftersom vi antog k ≥ 3 . Lägga till alla sådana incidenser längs alla m linjer, finner vi att antalet segment som erhålls på detta sätt är minst lika med hälften av antalet av alla incidenser. Om vi ​​betecknar antalet sådana segment med e , räcker det för att visa det

Betrakta nu en graf som bildas av n punkter som hörn och e -segment som kanter. Eftersom varje segment ligger på en av de m linjerna och två linjer skär högst i en punkt, överstiger inte antalet skärningar i denna graf m 2 . Från skärningstalets olikhet drar vi slutsatsen att antingen e ≤ 7,5 n eller m 2 ≥ e 3 / 33,75 n 2 . I vilket fall som helst, e ≤ 3,24( nm ) 2/3 + 7,5 n och vi får den nödvändiga gränsen

Bevis på den andra formuleringen

Eftersom vilket par av punkter som helst kan kopplas samman med högst en linje, kan det finnas högst n ( n − 1)/2 l linjer som kan förbinda k eller flera punkter eftersom k ≥ 2 . Denna gräns bevisar satsen för litet k (till exempel om k ≤ C för någon absolut konstant C ). Därför är det bara meningsfullt att överväga fall där k är stort, säg k ≥ C.

Anta att det finns m linjer som var och en innehåller minst k punkter. Dessa linjer bildar åtminstone mk incidenser, och sedan, genom den första varianten av Szemerédy-Trotter-satsen, har vi

och minst en jämställdhet från eller är uppfylld . Vi förkastar den tredje möjligheten eftersom vi antog att k är stort, så de två första finns kvar. Men i båda fallen, efter enkla algebraiska beräkningar, får vi , vilket krävs.

Optimalitet

Om konstanta faktorer inte beaktas kan gränsen för Szemeredy-Trotter-incidensen inte förbättras. För att se detta, överväg ett positivt heltal N ∈ Z + uppsättningen av punkter för heltalsgittret

och en uppsättning linjer

Det är klart att och . Eftersom varje linje är infallande mot N punkter (dvs en gång för varje ), är antalet incidenser lika med , vilket motsvarar den övre gränsen [3] .

Generalisering för R d

En generalisering av detta resultat för en godtycklig dimension R d hittades av Agaval och Aronov [4] . Givet en mängd S som innehåller n punkter och en mängd H som innehåller m hyperplan, begränsas antalet förekomster av punkter från S och hyperplan från H ovanför av antalet

På motsvarande sätt begränsas antalet hyperplan i H som innehåller k eller fler punkter ovanför av antalet

Edelbrunnerkonstruktionen visar att gränsen är asymptotiskt optimal [5] .

Soimoshi och Tao fick en nästan exakt övre gräns för antalet förekomster mellan punkter och algebraiska varianter i högdimensionella utrymmen. Deras bevis använder polynomens sandwichsats [6] .

Applikationer

Szemeredy-Trotter-satsen finner många tillämpningar inom additiv [7] [8] [9] och aritmetisk kombinatorik (till exempel för att bevisa summa-produktsatsen [10] ).

Anteckningar

  1. ↑ Szemerédi, Trotter, 1983 , sid. 381–392.
  2. ↑ Szekely, 1997 , sid. 353–358.
  3. ↑ Tao, 2011 .
  4. ↑ Agarwal, Aronov, 1992 , sid. 359–369.
  5. ↑ Edelsbrunner, 1987 .
  6. ↑ Solymosi, Tao, 2012 .
  7. ↑ Tomasz Schoen, Ilya Shkredov, "Om summan av konvexa uppsättningar" . Hämtad 19 november 2018. Arkiverad från originalet 12 juni 2018.
  8. ↑ A. Iosevich, S. Konyagin, M. Rudnev och V. Ten, "Om kombinatorisk komplexitet av konvexa sekvenser", 19 juli 2004 . Hämtad 19 november 2018. Arkiverad från originalet 12 juni 2018.
  9. ↑ Elekes, Nathanson, Ruzsa, "Konvexitet och sumsets" (länk inte tillgänglig) . Hämtad 19 november 2018. Arkiverad från originalet 12 juni 2018. 
  10. ↑ G. Elekes, Om antalet summor och produkter, Acta Arith. 81 (1997), 365-367. . Datum för åtkomst: 19 november 2018. Arkiverad från originalet den 7 februari 2019.

Litteratur

Ytterligare läsning