Limits of order types
From MaRDI portal
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 ErdH{o}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 ErdH{o}s on the density of k-tuples in convex position, for large k.
Recommendations
Cited in
(11)- Semantic limits of dense combinatorial objects
- Convex hulls of random order types
- Decomposing graphs into edges and triangles
- Closing in on Hill's conjecture
- Poset limits can be totally ordered
- Bounds on small Ramsey numbers by semidefinite programming
- Clique-width of point configurations
- Automated mathematical discovery and verification: minimizing pentagons in the plane
- Inducibility of directed paths
- Semidefinite programming and Ramsey numbers
- Compactness and finite forcibility of graphons
This page was built for publication: Limits of order types
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5368695)
