License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SOCG.2015.300
URN: urn:nbn:de:0030-drops-51264
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5126/
Go to the corresponding LIPIcs Volume Portal

Goaoc, Xavier ; Hubard, Alfredo ; de Joannis de Verclos, Rémi ; Sereni, Jean-Sébastien ; Volec, Jan

Limits of Order Types

pdf-format:
43.pdf (0.6 MB)

Abstract

The notion of limits of dense graphs was invented, among other reasons, to attack problems in extremal graph theory. It is straightforward to define limits of order types in analogy with limits of graphs, and this paper examines how to adapt to this setting two approaches developed to study limits of dense graphs.

We first consider flag algebras, which were used to open various questions on graphs to mechanical solving via semidefinite programming. We define flag algebras of order types, and use them to obtain, via the semidefinite method, new lower bounds on the density of 5- or 6-tuples in convex position in arbitrary point sets, as well as some inequalities expressing the difficulty of sampling order types uniformly.

We next consider graphons, a representation of limits of dense graphs that enable their study by continuous probabilistic or analytic methods. We investigate how planar measures fare as a candidate analogue of graphons for limits of order types. We show that the map sending a measure to its associated limit is continuous and, if restricted to uniform measures on compact convex sets, a homeomorphism. We prove, however, that this map is not surjective. Finally, we examine a limit of order types similar to classical constructions in combinatorial geometry (Erdos-Szekeres, Horton...) and show that it cannot be represented by any somewhere regular measure; we analyze this example via an analogue of Sylvester's problem on the probability that k random points are in convex position.

BibTeX - Entry

@InProceedings{goaoc_et_al:LIPIcs:2015:5126,
  author =	{Xavier Goaoc and Alfredo Hubard and R{\'e}mi de Joannis de Verclos and Jean-S{\'e}bastien Sereni and Jan Volec},
  title =	{{Limits of Order Types}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{300--314},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Lars Arge and J{\'a}nos Pach},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5126},
  URN =		{urn:nbn:de:0030-drops-51264},
  doi =		{10.4230/LIPIcs.SOCG.2015.300},
  annote =	{Keywords: order types, Limits of discrete structures, Flag algebras, Erdos-Szekeres, Sylvester’s problem}
}

Keywords: order types, Limits of discrete structures, Flag algebras, Erdos-Szekeres, Sylvester’s problem
Collection: 31st International Symposium on Computational Geometry (SoCG 2015)
Issue Date: 2015
Date of publication: 12.06.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI