Szemerédi–Trotter-tétel

A Szemerédi–Trotter-tétel a matematika, ezen belül a diszkrét geometria egyik fontos tétele. Pach János, Radoš Radoičić, Tóth Géza és Tardos Gábor megmutatták, hogy legfeljebb 2 , 5 n 2 3 m 2 3 + n + m {\displaystyle 2{,}5n^{\frac {2}{3}}m^{\frac {2}{3}}+n+m} illeszkedés lehetséges.[1] A jelenlegi ismert legjobb felső határ 2,44.[2] A felső határ nem teljesül 0,42-os együttható esetén.[3]

A tétel állítása

Ha a síkban adott n pont és m egyenes, akkor a köztük levő illeszkedések száma O ( n 2 / 3 m 2 / 3 + n + m ) {\displaystyle O(n^{2/3}m^{2/3}+n+m)} .

A tétel másik formája

Ha a síkban adott n pont és k>2, akkor azon egyenesek száma, amelyek a pontok közül legalább k-t tartalmaznak, O ( n 2 / k 3 + n / k ) {\displaystyle O(n^{2}/k^{3}+n/k)} . Ezt Szemerédi és Trotter cellafelbontással bizonyították.[4][5]

Jegyzetek

  1. ↑ Pach János (2006). „Improving the Crossing Lemma by Finding More Crossings in Sparse Graphs”. Discrete & Computational Geometry 36 (4), 527–552. o. DOI:10.1007/s00454-006-1264-9.  
  2. ↑ Ackerman, Eyal (2019. december 1.). „On topological graphs with at most four crossings per edge”. Computational Geometry 85, 101574. o. DOI:10.1016/j.comgeo.2019.101574. ISSN 0925-7721.  
  3. ↑ (1997) „Graphs drawn with few crossings per edge”. Combinatorica 17 (3), 427–439. o. DOI:10.1007/BF01215922.  
  4. ↑ Szemerédi Endre (1983). „Extremal problems in discrete geometry”. Combinatorica 3 (3–4), 381–392. o. DOI:10.1007/BF02579194.  
  5. ↑ Szemerédi Endre (1983). „A Combinatorial Distinction Between the Euclidean and Projective Planes”. European Journal of Combinatorics 4 (4), 385–394. o. DOI:10.1016/S0195-6698(83)80036-5.  
  • Matematika Matematikaportál • összefoglaló, színes tartalomajánló lap
Ez a geometriai témájú lap egyelőre csonk (erősen hiányos). Segíts te is, hogy igazi szócikk lehessen belőle!