From Crossing-Free Graphs on Wheel Sets to Polytopes with Few Vertices

by
• Emo Welzl

· Jul 23, 2016 · 709 views ·

A perfect matching on a finite planar point set SS is crossing-free if all of its edges are disjoint in the straight-line embedding on SS. In 1948 Motzkin was interested in the number of such crossing-free perfect matchings for SS the 2m2m vertices of a convex polygon and he proved that to be the mm-th Catalan number. SS is called a wheel set if all but exactly one point in SS are vertices of its convex hull. Again we start by asking for the number of crossing-free perfect matchings of such a wheel set SS, going the smallest possible step beyond Motzkin's endeavor. Since position matters now, in the sense that the number is not determined by the cardinality of the wheel set alone, this immediately raises extremal and algorithmic questions. Answering these comes with all kinds of surprises. In fact, it turns out that for the purpose of counting crossing-free geometric graphs (of any type, e.g. triangulations or crossing-free spanning trees) on such a set PP it suffices to know the so-called frequency vector of PP (as opposed to the full order type information) – a simple formula dependent on this frequency vector exists. Interestingly, the number of order types of nn points in almost convex position is roughly 2n2n, compared to the number of frequency vectors which is about 2n/22n/2. Finally, this takes us on a journey to the rectilinear crossing-number of the complete graph, to counting of origin-embracing triangles and simplices (simplicial depth) and to (algorithms for) counting facets of high-dimensional polytopes with few vertices. Based on recent joint work with Andres J. Ruiz-Vargas, Alexander Pilz, and Manuel Wettstein.