Loading...
Please wait, while we are loading the content...
Similar Documents
Beyond the Richter-Thomassen Conjecture János Pach
| Content Provider | Semantic Scholar |
|---|---|
| Author | Rubin, Natan Tardos, Gábor |
| Copyright Year | 2015 |
| Abstract | If two closed Jordan curves in the plane have precisely one point in common, then it is called a touching point. All other intersection points are called crossing points. The main result of this paper is a Crossing Lemma for closed curves: In any family of n pairwise intersecting simple closed curves in the plane, no three of which pass through the same point, the number of crossing points exceeds the number of touching points by a factor of at least Ω((log logn)). As a corollary, we prove the following long-standing conjecture of Richter and Thomassen: The total number of intersection points between any n pairwise intersecting simple closed curves in the plane, no three of which pass through the same point, is at least (1− o(1))n. EPFL, Lausanne and Rényi Institute, Budapest. Supported by Swiss National Science Foundation Grants 200020144531 and 20021-137574. Email: pach@cims.nyu.edu Ben Gurion University of the Negev, Beer-Sheba, Israel. Email: rubinnat.ac@gmail.com. Supported by Minerva Fellowship Program of the Max Planck Society, by the Fondation Sciences Mathématiques de Paris (FSMP), and by a public grant overseen by the French National Research Agency (ANR) as part of the Investissements dAvenir program (reference: ANR-10-LABX-0098). Rényi Institute, Budapest. Supported by the “Lendület” Project of the Hungarian Academy of Sciences. Email: tardos@renyi.hu 1 Submission number 300 to FOCS 2015: DO NOT DISTRIBUTE! |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.math.nyu.edu/~pach/publications/RichtertThomassenIIFOCS040215.pdf |
| Alternate Webpage(s) | http://real.mtak.hu/44394/1/RichtertThomassenIIFOCS040215.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
