Limits of order types

Xavier Goaoc 1 Alfredo Hubard 2, 1 Rémi De Joannis de Verclos 3 Jean-Sébastien Sereni 4 Jan Volec 5, 6
2 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
3 G-SCOP_GCSP - GCSP
G-SCOP - Laboratoire des sciences pour la conception, l'optimisation et la production
4 ORPAILLEUR - Knowledge representation, reasonning
Inria Nancy - Grand Est, LORIA - NLPKD - Department of Natural Language Processing & Knowledge Discovery
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 semi-definite 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 (Erdős-Szekeres, Horton. . .) and show that it cannot be represented by measures that are somewhere regular; we analyze this example via an analogue of Sylvester's problem on the probability that k random points are in convex position.
Type de document :
Communication dans un congrès
Janos Pach, Larse Arge. Symposium on Computational Geometry 2015, Jun 2015, Eindhoven, Netherlands. 34, pp.876, 2015, Symposium on Computational Geometry 2015: Eindhoven, The Netherlands. <10.4230/LIPIcs.SOCG.2015.300>
Liste complète des métadonnées

https://hal.inria.fr/hal-01172466
Contributeur : Alfredo Hubard <>
Soumis le : mardi 7 juillet 2015 - 14:28:39
Dernière modification le : samedi 18 février 2017 - 01:14:40

Identifiants

Citation

Xavier Goaoc, Alfredo Hubard, Rémi De Joannis de Verclos, Jean-Sébastien Sereni, Jan Volec. Limits of order types. Janos Pach, Larse Arge. Symposium on Computational Geometry 2015, Jun 2015, Eindhoven, Netherlands. 34, pp.876, 2015, Symposium on Computational Geometry 2015: Eindhoven, The Netherlands. <10.4230/LIPIcs.SOCG.2015.300>. <hal-01172466>

Partager

Métriques

Consultations de la notice

363