Szemerédi-Trotter-teoremet og dets anvendelser i forbindelsesgeometri

Abstract

Vi gir en innføring i utvalgte temaer innen additiv kombinatorikk. Vi presenterer Szemerédi-Trotter-teoremet med bevis og viser hvordan dette sentrale verktøyet fra forbindelsesgeometrien kan brukes til å løse problemer som tilsynelatende er ganske forskjellige. Spesielt ser vi på sum-produkt-problemet og Erdős' unike-avstander-problem. Vi gjennomgår formodningene som er fremsatt, hva som er løst og hva som er åpent.

We give an introduction to selected topics from additive combinatorics. We present the Szemerédi-Trotter theorem with proof and show how this cornerstone tool of incidence geometry can be used to solve problems that at first glance appear to be of quite different natures. In particular, we look at the sum-product problem and the distinct distances problem of Erdős. We state the conjectures made and explain what is solved and what remains open.