Limits of Order Types *

Limites de types d'ordre

Xavier Goaoc (1) , Alfredo Hubard (2) , Rémi de Joannis de Verclos (3) , Jean-Sébastien Sereni (4) , Jan Volec (5)

1 GAMBLE - Geometric Algorithms and Models Beyond the Linear and Euclidean realm
2 LIGM - Laboratoire d'Informatique Gaspard-Monge
3 Radboud University [Nijmegen]
4 CNRS - Centre National de la Recherche Scientifique
5 Department of Mathematics and Computer Science [Emory University]

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.

Nous utilisons des idées issues de la théorie des limites de structures combinatoires denses afin d'étudier les types d'ordre, qui sont un encodage combinatoire d'ensembles finis de points. À l'aide des algèbres de drapeaux, nous obtenons de nouveaux résultats numériques sur le problème, soulevé par Erdős, consistant à trouver la densité minimale de quintuplets ou sextuplets en position convexe dans un ensemble arbitraire de points, et nous obtenons également une inégalité traduisant la difficulté d'échantillonner les types d'ordre de manière uniforme. Ensuite nous établissons des résultats sur les représentations analytiques des limites de types d'ordre par des mesures du plan. Notre résultat principal est un théorème de rigidité : nous montrons que les échantillonnages de deux mesures produisent la même distribution de probabilité sur les types d'ordre alors ces mesures sont projectivement équivalentes pourvu que le support de l'une d'elles au moins soit d'intérieur non vide. Nous montrons également que certaines conditions sur la dimension de Hausdorff du support est nécessaire afin d'obtenir cette rigidité projective, et nous construisons des limites de types d'ordre qui ne peuvent pas être représentées par des mesures du plan. Revenant à la géométrie combinatoire, nous établissons un lien entre la régularité de cette représentation analytique et le problème d'Erdős sur la densité des k-gones en position convexe lorsque k tend vers l'infini.

Mots clés: Limits of discrete structures; Flag algebras; geometric measure theory; Rigidity properties; Erdős-Szekeres theorem; Sylvester's problem

Domaines: Combinatoire [math.CO]; Mathématique discrète [cs.DM]

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