On short edges in complete topological graphs

2023/07/16 by Suk, Andrew · 1 citation
#Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2307.08165

Abstract

Let h(n) be the minimum integer such that every complete n-vertex simple topological graph contains an edge that crosses at most h(n) other edges. In 2009, Kynčl and Valtr showed that h(n) = O(n²/log^1/4 n), and in the other direction, gave constructions showing that h(n) = Ω(n^3/2). In this paper, we prove that h(n) = O(n^7/4). Along the way, we establish a new variant of Chazelle and Welzl's matching theorem for set systems with bounded VC-dimension, which we believe to be of independent interest.

Cited by

• Girth in GF(q)-representable matroids

Related

• Saturated simple and 2-simple topological graphs with few edges
• Unavoidable patterns in complete simple topological graphs
• Disjoint edges in topological graphs and the tangled-thrackle conjecture
• A stability result for almost perfect matchings
• Disjoint edges in complete topological graphs