Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Limits of Order Types *

Abstract : We apply ideas from the theory of limits of dense combinatorial structures to study order types, which are combinatorial encodings of finite point sets. Using flag algebras we obtain new numerical results on the Erdős problem of finding the minimal density of 5-or 6-tuples in convex position in an arbitrary point set, and also an inequality expressing the difficulty of sampling order types uniformly. Next we establish results on the analytic representation of limits of order types by planar measures. Our main result is a rigidity theorem: we show that if sampling two measures induce the same probability distribution on order types, then these measures are projectively equivalent provided the support of at least one of them has non-empty interior. We also show that some condition on the Hausdorff dimension of the support is necessary to obtain projective rigidity and we construct limits of order types that cannot be represented by a planar measure. Returning to combinatorial geometry we relate the regularity of this analytic representation to the aforementioned problem of Erdős on the density of k-tuples in convex position, for large k.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [43 references]  Display  Hide  Download
Contributor : Jean-Sébastien Sereni Connect in order to contact the contributor
Submitted on : Tuesday, November 6, 2018 - 9:33:17 AM
Last modification on : Friday, February 4, 2022 - 9:00:13 AM
Long-term archiving on: : Thursday, February 7, 2019 - 12:59:06 PM


Files produced by the author(s)


  • HAL Id : hal-01913144, version 1


Xavier Goaoc, Alfredo Hubard, Rémi de Joannis de Verclos, Jean-Sébastien Sereni, Jan Volec. Limits of Order Types *. 2018. ⟨hal-01913144⟩



Record views


Files downloads