Journal
ADVANCES IN MATHEMATICS
Volume 331, Issue -, Pages 908-940Publisher
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.aim.2018.03.015
Keywords
Extremal problems; Combinatorial geometry; Arrangements of curves; Crossing Lemma; Separators; Contact graphs
Categories
Funding
- Swiss National Science Foundation [200020-162884, 200021-175977]
- European Research Council (ERC) under the European Union [678765]
- Israel Science Foundation [1452/15]
- United States-Israel Binational Science Foundation [2014384]
- Ralph Selig Career Development Chair in Information Theory
- National Research, Development and Innovation Office - NKFIH [K-116769, SNN-117879]
- Hungarian Academy of Sciences
- European Research Council (ERC) [678765] Funding Source: European Research Council (ERC)
Ask authors/readers for more resources
If two Jordan curves in the plane have precisely one point in common, and there they do not properly cross, then the common point is called a touching point. The main result of this paper is a Crossing Lemma for simple curves: Let X and T stand for the sets of intersection points and touching points, respectively, in a family of n simple curves in the plane, no three of which pass through the same point. If vertical bar T vertical bar > cn, for some fixed constant c > 0, then we prove that vertical bar X vertical bar = Omega(vertical bar T vertical bar(log log(vertical bar T vertical bar/n))(1/504)). In particular, if vertical bar T vertical bar/n -> infinity, then the number of intersection points is much larger than the number of touching points. As a corollary, we confirm the following long-standing conjecture of Richter and Thomassen: The total number of intersection points between n pairwise intersecting simple closed (i.e., Jordan) curves in the plane, no three of which pass through the same point, is at least (1 - o(1))n(2). (C) 2018 Published by Elsevier Inc.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available