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

Jul 23, 2016

Speakers

About

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.

Organizer

Categories

About The Mathematics of Jiří Matoušek

International Conference on The Mathematics of Jiří Matoušek, Charles University, Prague 2016

Store presentation

Should this presentation be stored for 1000 years?

How do we store presentations

Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%

Sharing

Recommended Videos

Presentations on similar topic, category or speaker

Interested in talks like this? Follow The Mathematics of Jiří Matoušek