Large chirotopes with computable numbers of triangulations

Mathilde Bouvel, Valentin Féray, Xavier Goaoc, Florent Koechlin · 2026

Read Large chirotopes with computable numbers of triangulations by Mathilde Bouvel, Valentin Féray, Xavier Goaoc, Florent Koechlin (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-10251.txt.

Introduction

Bouvel and coauthors develop decomposition methods for chirotopes, a combinatorial abstraction of planar point sets. Their aim is counting how many triangulations a given point set supports in total. They generalise the convex and concave sum operations known for a special family called chains. With the kernel method and a functional equation, they get a tight asymptotic count for triangulations of the double circle configuration.

Catalog record

CREATORMathilde Bouvel, Valentin Féray, Xavier Goaoc, Florent Koechlin
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE83009
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.10251

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Large chirotopes with computable numbers of triangulations Mathilde Bouvel, Valentin Féray, Xavier Goaoc, Florent Koechlin Abstract Chirotopes are a common combinatorial abstraction of (planar) point sets. In this paper we investigate decomposition methods for chirotopes, and their application to the problem of counting the number of triangulations supported by a given planar point set. In particular, we generalize the convex and concave sums operations defined by Rutschmann and Wettstein for a particular family of chirotopes (which they call chains), and obtain a precise asymptotic estimate for the number of triangulations of the double circle, using a functional equation and the kernel method. file NoyauDoubleCerle.mw file NoyauDoubleCerle.pdf 1 Introduction Oriented matroids are combinatorial structures that can be used to describe a variety of objects, from acyclic orientations of graphs to the mutual position of points, vectors or hyperplanes in \mathbb{R}^{d} . Here we consider the oriented matroids that arise from point configurations in the plane, given by their chirotope , that is the function mapping each ordered triple of points to its orientation. Formally, the chirotope of a set {\mathcal{P}}=\{\mathfrak{p}_{\ell}\}_{\ell\in X} of points in general position labeled by X is the function \chi_{\mathcal{P}}:\left\{\begin{array}[]{rcl}(X)_{3}&\to&\{-1,+1\}\\ (x,y,z)&\mapsto&\left\{\begin{array}[]{rl}+1&\text{ if $\mathfrak{p}_{x},\mathfrak{p}_{y},\mathfrak{p}_{z}$ are in counterclockwise order,}\\ -1&\text{ if $\mathfrak{p}_{x},\mathfrak{p}_{y},\mathfrak{p}_{z}$ are in clockwise order.}\\ \end{array}\right.\end{array}\right. Here, (X)_{3} is the set of triples (x,y,z) of distinct elements in X . This function encodes the labeled order type [ GP83 ] of the point set. We say that chirotopes of point sets are realizable to distinguish them from their combinatorial (abstract) generalization (see Section 1.1 ). In this paper, we investigate a decomposition method for chirotopes, that is, a process to describe large rooted chirotopes in terms of smaller parts. (A rooted chirotope is a chirotope with a distinguished label.) This method is based on two operations, joins and meets , which generalize similar operations on chains defined by Rutschmann and Wettstein [ RW23 ] . We make the following contributions: • We prove that the join and meet operations, which are natural for point sets, can be defined at the abstract level of (rooted) chirotopes. In particular, the join/meet of two realizable chirotopes is again a realizable chirotope (Propositions 2.2 and 2.10 ). • We associate to each rooted chirotope a bivariate polynomial such that (i) the number of triangulations of the chirotope can be easily recovered from this bivariate polynomial (Lemma 3.2 ), and (ii) these bivariate polynomials can be recursively computed along join and meet operations (Proposition 3.3 ). • As an application, we obtain precise asymptotic formulas for the number of triangulations of the double circle \DC_{n} with n external (and thus n internal) points ( Theorem 4.1 ). Throughout the paper, all point sets are finite, planar and in general position, meaning that no three points are ever aligned (for simplicity). In other words, all (realizable) chirotopes we consider are simple . 1.1 Context and related work (Abstract) chirotopes. The chirotopes of sets of labeled points are called realizable chirotopes and are special cases of purely combinatorial objects which we now define. Given a finite set X , we write (X)_{3} for the set of triples (x,y,z) of distinct elements in X . A chirotope on a finite set X is a function \chi:(X)_{3}\to\{-1,1\} that satisfies the following properties: (symmetry) for any distinct x,y,z\in X , \chi(x,y,z)=\chi(y,z,x)=\chi(z,x,y)=-\chi(z,y,x)=-\chi(y,x,z)=-\chi(x,z,y); (1) (interiority) for any distinct t,x,y,z\in X , \chi(t,y,z)=\chi(x,t,z)=\chi(x,y,t)=1\quad\Rightarrow\quad\chi(x,y,z)=1; (2) (transitivity) for any distinct s,t,x,y,z\in X , \chi(t,s,x)=\chi(t,s,y)=\chi(t,s,z)=\chi(x,y,t)=\chi(y,z,t)=1\quad\Rightarrow\quad\chi(x,z,t)=1. (3) Actually, such a map is a simple chirotope since no triple is mapped to 0 , but we drop the word “simple” throughout the paper. One can check by elementary geometric arguments that every realizable chirotope is indeed a chirotope. We may use the term abstract chirotope to emphasize that a chirotope is not necessarily realizable. Finally, functions from (X)_{3} to \{-1,1\} satisfying the symmetry axiom but not necessarily the interiority and transitivity ones will be referred to as sign functions . Geometric properties for abstract chirotopes. Geometric notions that can be expressed only through orientations of triples of points generalize from planar point sets to abstract chirotopes. Let us give two important example. First, an element x\in X is extreme in a chirotope \chi on X if there exists y\in X\setminus\{x\} such that \chi(x,y,z) is the same for all z\in X\setminus\{x,y\} . With this definition, extreme elements of realizable chirotopes correspond precisely to the vertices of their convex hulls. Second, given a point set P=\{\mathfrak{p}_{\ell}\}_{\ell\in X} , two segments \mathfrak{p}_{x}\mathfrak{p}_{y} and \mathfrak{p}_{z}\mathfrak{p}_{t} with distinct endpoints in P cross if and only if \chi_{P}(x,y,z)=-\chi_{P}(x,y,t) and \chi_{P}(z,t,x)=-\chi_{P}(z,t,y) . We can therefore define the crossing of segments for abstract chirotopes: a segment in a chirotope \chi on X is a pair of elements of X , and the segments xy and zt cross in \chi if they satisfy the above condition (with \chi instead of \chi_{P} ). xe Numbers of triangulations A triangulation of a chirotope \chi is an inclusion-maximal family of segments such that no two cross in \chi . This naturally extends the notion of triangulation of a point set. Let \mathfrak{T}(\chi) denote the set of triangulations of the chirotope \chi . When \chi is the chirotope of n points in convex position, |\mathfrak{T}(\chi)| is the (n-2) th Catalan number. In general, the problem of maximizing or minimizing the number of triangulations among all possible sets of n points is open (even at an asymptotic level). Indeed, for every realizable chirotope \chi of size n , it is proven that |\mathfrak{T}(\chi)| is at most 30^{n} [ SS11 ] and is at least \Omega(2.63^{n}) [ AAH+16 ] . By comparison, the known construction with the largest number of triangulations is the so-called Koch chain K_{s} , with n=2^{s}+1 points and |\mathfrak{T}(K_{s})|=\Omega(9.08^{n}) [ RW23 ] (more below). As for the lower bound, the known construction with the smallest number of triangulations is the double circle \DC_{n} , with 2n points and |\mathfrak{T}(\DC_{n})|=(12+o(1))^{n} [ HN97 ] . 1 1 1 To be more specific, this result is often mentioned in the literature with reference to [ HN97 ] ; however, we could not find it precisely in [ HN97 ] , neither can we derive it simply from their signed explicit formula. Nevertheless, we shall compute the precise asymptotic of |\mathfrak{T}(\DC_{n})| in Section 4 , confirming this statement. The double circle is actually conjectured to minimize the number of triangulations among n -point realizable chirotopes. (Koch) chains, convex and concave sums. Let us outline some of the ideas behind the construction of the Koch chain (in a language better suited for our purpose). A segment in a chirotope \chi is unavoidable if it belongs to every triangulation of \chi . A chain is a chirotope \chi on X such that the elements of X can be arranged into a sequence x_{1},x_{2},\ldots,x_{n} where each pair \{x_{i},x_{i+1}\} is an unavoidable segment in \chi . Ruschmann and Wettstein [ RW23 ] defined two operations (shown in Fig. 1 ), called convex sum ( \vee ) and concave sum ( \wedge ), that combine two smaller chains into a larger one. They also introduce a flip operation \bar{\cdot} , which simply consists in reversing all orientations. Figure 1: Two chains (left), their convex sum (center) and

Read the complete text