Limits of Order Types

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



PDF
Thumbnail PDF

File

LIPIcs.SOCG.2015.300.pdf
  • Filesize: 0.63 MB
  • 15 pages

Document Identifiers

Author Details

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

Cite AsGet BibTex

Xavier Goaoc, Alfredo Hubard, Rémi de Joannis de Verclos, Jean-Sébastien Sereni, and Jan Volec. Limits of Order Types. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 300-314, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.SOCG.2015.300

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.
Keywords
  • order types
  • Limits of discrete structures
  • Flag algebras
  • Erdos-Szekeres
  • Sylvester’s problem

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. B. Abrego, S. Fernandez-Merchant, and G. Salazar. The rectilinear crossing number of k_n: Closing in (or are we?). In Thirty Essays on Geometric Graph Theory, pages 5-18. Springer, 2013. Google Scholar
  2. O. Aichholzer, F. Aurenhammer, and H. Krasser. Enumerating Order Types for Small Point Sets with Applications. In Proc. 17^th Ann. ACM Symp. Computational Geometry, pages 11-18, Medford, Massachusetts, USA, 2001. Google Scholar
  3. N. Alon. The number of polytopes, configurations and real matroids. Mathematika, 33:62- 71, 1986. Google Scholar
  4. G. Aloupis, J. Iacono, S. Langerman, Ö. Özkan, and S. Wuhrer. The complexity of order type isomorphism. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'14, pages 405-415, 2014. Google Scholar
  5. B. Borchers. CSDP, A C library for semidefinite programming. Optimization Methods and Software, 11(1-4):613-623, 1999. Google Scholar
  6. P. Brass, W. Moser, and J. Pach. Research Problems in Discrete Geometry. Springer, 2005. Google Scholar
  7. P. Erdős and G. Szekeres. On some extremum problems in elementary geometry. Eotvos Sect. Math, 3-4:53-62, 1962. Google Scholar
  8. J. D. Horton. Sets with no empty convex 7-gons. Canad. Math. Bull., 26:482-484, 1983. Google Scholar
  9. L. Lovász and B. Szegedy. Limits of dense graph sequences. J. Combin. Theory Ser. B, 96(6):933-957, 2006. Google Scholar
  10. E. Lubetzky and Y. Zhao. On replica symmetry of large deviations in random graphs. Random Structures & Algorithms, 2014. URL: http://dx.doi.org/10.1002/rsa.20536.
  11. A. A. Razborov. Flag algebras. J. Symbolic Logic, 72(4):1239-1282, 2007. Google Scholar
  12. E. Scheinerman and H. Wilf. The rectilinear crossing number of a complete graph and sylvester’s "four point problem" of geometric probability. Amer. Math. Monthly, 101:939-943, 1994. Google Scholar
  13. P. W. Shor. Stretchability of pseudolines is NP-hard. In Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift, volume 4 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 531-554. Amer. Math. Soc., 1991. Google Scholar
  14. W. A. Stein et al. Sage Mathematics Software (Version 6.1). The Sage Development Team, 2013. URL: http://www.sagemath.org.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail