Szemedi-Trotter tétel

A Szemedi-Trotter tétel a kombinatorikus geometria eredménye . A tétel kimondja, hogy adott n pont és m egyenes egy síkban az előfordulások száma (azaz azon pont/egyenes párok száma, ahol egy pont egy egyenesen fekszik)

és ezen a korláton nem lehet javítani.

A tétel egyenértékű megfogalmazása a következő. Ha adott n pont és egy k > 2 egész szám, akkor legalább k ponton átmenő egyenesek száma

Szemedi és Trotter [1] eredeti bizonyítása összetett volt, és a sejtosztódásként ismert kombinatorikus technikát alkalmazta . Később Szekei egy sokkal egyszerűbb bizonyítást fedezett fel a metszésszám- egyenlőtlenség segítségével gráfokra [2] (lásd alább).

A Szemedi–Trotter-tételnek számos következménye van, beleértve a Beck-féle -tételt a beesési geometriában .

Az első állítás bizonyítéka

A két vagy annál kevesebb pontot tartalmazó vonalakat elvethetjük, mivel maximum 2 m beesést adhatnak. Így feltételezhetjük, hogy bármely egyenes legalább három pontot tartalmaz.

Ha egy egyenesben k pont van, akkor az n pont közül kettőt összekötő k − 1 szakaszt tartalmaz. Konkrétan, az egyenes legalább k /2 ilyen szakaszt fog tartalmazni, mivel azt feltételeztük, hogy k ≥ 3 . Összeadva az összes ilyen előfordulást az összes m egyenes mentén , azt kapjuk, hogy az így kapott szegmensek száma legalább egyenlő az összes előfordulás számának felével. Ha e - vel jelöljük az ilyen szegmensek számát, akkor ezt elég megmutatni

Tekintsünk most egy gráfot , amelyet n pont alkot csúcsnak és e szakaszt élnek. Mivel minden szakasz az m egyenes egyikén fekszik, és két egyenes legfeljebb egy pontban metszi egymást, ennek a gráfnak a metszéspontjainak száma nem haladja meg az m 2 -t . A metszésszám-egyenlőtlenségből azt a következtetést vonjuk le, hogy vagy e ≤ 7,5 n vagy m 2 ≥ e 3 / 33,75 n 2 . Mindenesetre e ≤ 3,24( nm ) 2/3 + 7,5 n és megkapjuk a szükséges korlátot

A második megfogalmazás bizonyítéka

Mivel bármely pontpárt legfeljebb egy egyenes köthet össze, legfeljebb n ( n − 1)/2 l olyan egyenes lehet, amely k vagy több pontot köthet össze, mivel k ≥ 2 . Ez a korlát bizonyítja a tételt kis k -ra (például ha k ≤ C valamilyen C abszolút állandóra ). Így csak olyan eseteket van értelme figyelembe venni, ahol k nagy, mondjuk k ≥ C.

Tegyük fel, hogy van m egyenes, amelyek mindegyike legalább k pontot tartalmaz. Ezek a sorok legalább mk incidenciát képeznek, majd a Szemerédy–Trotter tétel első változata szerint

és legalább egy egyenlőség teljesül . A harmadik lehetőséget elvetjük, mert feltételeztük, hogy k nagy, így az első kettő marad. De mindkét esetben egyszerű algebrai számítások után megkapjuk , amire szükség van.

Optimalitás

Ha nem vesszük figyelembe az állandó tényezőket, a Szemedy–Trotter előfordulási korlát nem javítható. Ennek megtekintéséhez vegyük figyelembe bármely pozitív egész N ∈ Z + az egész rács pontkészletét

és egy sor sor

Egyértelmű, hogy és . Mivel minden egyenes N pontba esik (azaz mindegyikhez egyszer ), az előfordulások száma egyenlő -vel , ami megfelel a felső korlátnak [3] .

R d általánosítása

Ennek az eredménynek egy tetszőleges R d dimenzióra vonatkozó általánosítását Agaval és Aronov találta [4] . Adott egy n pontot tartalmazó S halmaz és egy m hipersíkot tartalmazó H halmaz, akkor az S -ből származó pontok és a H - ból származó hipersíkok előfordulási számát a fenti szám határolja.

Ezzel egyenértékűen a k vagy több pontot tartalmazó H -beli hipersíkok számát a szám határolja

Az Edelbrunner-konstrukció azt mutatja, hogy a határ aszimptotikusan optimális [5] .

Soimoshi és Tao majdnem pontos felső korlátot kapott a pontok és algebrai változatok közötti előfordulások számára nagydimenziós terekben. Bizonyításuk a polinomiális szendvicstételt [6] használja .

Alkalmazások

A Szemeredy-Trotter tétel számos alkalmazást talál az additív [7] [8] [9] és az aritmetikai kombinatorikában (például az összeg-szorzat tétel [10] bizonyítására ).

Jegyzetek

  1. ↑ Szemerédi, Trotter, 1983 , p. 381–392.
  2. ↑ Székely, 1997 , p. 353–358.
  3. ↑ Tao, 2011 .
  4. ↑ Agarwal, Aronov, 1992 , p. 359–369.
  5. ↑ Edelsbrunner, 1987 .
  6. ↑ Solymosi, Tao, 2012 .
  7. ↑ Tomasz Schoen, Ilya Shkredov, "A konvex halmazok összegeiről" . Letöltve: 2018. november 19. Az eredetiből archiválva : 2018. június 12.
  8. ↑ A. Iosevich, S. Konyagin, M. Rudnev és V. Ten, "A konvex sorozatok kombinatorikus összetettségéről", 2004. július 19 . Letöltve: 2018. november 19. Az eredetiből archiválva : 2018. június 12.
  9. ↑ Elekes, Nathanson, Ruzsa, "Konvexitás és summák" (hivatkozás nem elérhető) . Letöltve: 2018. november 19. Az eredetiből archiválva : 2018. június 12. 
  10. ↑ Elekes G., Az összegek és szorzatok számáról, Acta Arith. 81 (1997), 365–367. . Hozzáférés dátuma: 2018. november 19. Az eredetiből archiválva : 2019. február 7.

Irodalom

További olvasnivalók