Ramsey-type constructions for arrangements of segments

Abstract

Improving a result of Károlyi, Pach and Tóth, we construct an arrangement of $n$ segments in the plane with at most $n^{\log 8/\log 169}$ pairwise crossing or pairwise disjoint segments. We use the recursive method based on flattenable arrangements which was established by Larman, Matoušek, Pach and Törőcsik. We also show that not every arrangement can be flattened, by constructing an intersection graph of segments which cannot be realized by an arrangement of segments crossing a common line. Moreover, we also construct an intersection graph of segments crossing a common line which cannot be realized by a flattenable arrangement.

arXiv comment11 pages, 6 figures

Cited by in corpus (2)

• Ramsey-type theorems for lines in 3-space
• Improved Ramsey-type results for comparability graphs