Large chirotopes with computable numbers of triangulations

This paper generalizes decomposition methods for chirotopes to develop a precise asymptotic estimate for the number of triangulations of the double circle by applying functional equations and the kernel method.

The Gist

Imagine you have a scattered group of dots on a piece of paper. Your goal is to connect them all with straight lines to form triangles, covering the entire area without any lines crossing each other. This is called a triangulation.

The big question mathematicians ask is: How many different ways can you do this?

For some arrangements of dots, there are only a few ways. For others, there are millions. The paper you're asking about is a detective story about finding the "champion" arrangements—the ones that allow for the maximum (or minimum) number of these triangle puzzles.

Here is the story of the paper, broken down into simple concepts:

1. The Map vs. The Territory

First, the authors introduce a concept called a Chirotope.

• The Territory: This is the actual physical dots on the paper.
• The Map: This is a "chirotope." It's a set of rules that just tells you the order of the dots. If you look at three dots, the map says: "Are they arranged clockwise or counter-clockwise?"
• Why it matters: You don't need to know the exact coordinates of the dots to solve the puzzle; you only need to know their relative order. It's like knowing the rules of a game without needing to know the exact weight of the dice.

2. The Lego Bricks: Joins and Meets

The authors discovered a way to build complex dot arrangements out of smaller ones, like snapping Lego bricks together. They invented two new moves:

• The Join (The "Glue" Move): Imagine you have two separate groups of dots. You take a specific "root" dot from each group and glue them together. Then, you arrange the groups so that one group sits "above" the other, like a sandwich. This creates a new, bigger group.
• The Meet (The "Hinge" Move): This is the opposite. You glue the roots together, but this time you arrange the groups so they face "inward" or "downward," like a V-shape.

The Magic: The authors proved that if you start with two valid dot arrangements and use these "Join" or "Meet" moves, the result is always a valid arrangement. This allows them to build massive, complex shapes from tiny, simple ones.

3. The Counting Machine: Polynomials

Counting the triangles for a huge shape is hard. Doing it one by one would take forever.

• The Trick: Instead of counting triangles directly, the authors invented a special mathematical recipe (a polynomial). Think of this recipe as a machine. You put in the shape, and it spits out a number.
• The Superpower: Because they figured out how the "Join" and "Meet" moves work, they also figured out how to combine the recipes. If you know the recipe for Shape A and Shape B, you can instantly calculate the recipe for the new Shape C created by joining them. No need to start from scratch!

4. The Double Circle: The "Minimum" Champion

There is a famous shape called the Double Circle. Imagine two rings of dots, one inside the other, like a donut with a hole in the middle.

• For a long time, mathematicians suspected this shape has the fewest possible ways to triangulate it.
• The authors used their new "recipe machine" to prove this suspicion. They calculated the exact number of ways to triangulate a Double Circle with thousands of dots.
• The Result: They found a precise formula that predicts this number. It's much more accurate than previous guesses. It's like going from saying "There are about a million ways" to saying "There are exactly 1,042,567 ways, give or take a tiny fraction."

5. The "Koch Chain": The "Maximum" Champion

On the other end of the spectrum, there is a shape called the Koch Chain (named after the famous fractal snowflake).

• This shape is known to have the most triangulations of any shape we know of.
• The authors tried to beat the record. They asked: "Can we build a shape with even more triangles by mixing and matching our Lego bricks (Joins and Meets)?"
• The Verdict: They ran computer experiments and tried thousands of combinations. They failed. The Koch Chain still holds the record. It seems nature (or math) has a limit, and the Koch Chain is the king of complexity.

Summary Analogy

Think of the paper as a guide for building skyscrapers:

1. Chirotopes are the blueprints that only care about the floor plan, not the exact brick size.
2. Joins and Meets are the cranes that let you stack smaller buildings to make a giant one.
3. Polynomials are the calculators that instantly tell you how many rooms (triangles) are in the new building without counting them one by one.
4. The Double Circle is the most efficient, compact building (fewest rooms).
5. The Koch Chain is the most chaotic, complex building (most rooms).

The authors built a better calculator and proved that, for now, the Koch Chain is the most complex building we can make using these specific construction rules.

Technical Summary

Here is a detailed technical summary of the paper "Large chirotopes with computable numbers of triangulations" by Bouvel, Féray, Goaoc, and Koechlin.

1. Problem Statement

The paper addresses the combinatorial problem of counting the number of triangulations supported by a given planar point set. While the number of triangulations for points in convex position is given by the Catalan numbers, the problem becomes significantly harder for general point sets.

• Context: The number of triangulations varies wildly depending on the point configuration. The "Koch chain" ($K_s$) is currently the known construction maximizing this number ($\Omega(9.08^n)$), while the "double circle" ($DC_n$) is conjectured to minimize it.
• Gap: There is a lack of general decomposition methods for arbitrary point sets (or their combinatorial abstractions, chirotopes) that allow for efficient, exact counting of triangulations, particularly for large structures. Existing methods often rely on specific geometric properties or modular decomposition, which do not cover all cases.

2. Methodology

The authors develop a framework based on rooted chirotopes (combinatorial abstractions of point sets with a distinguished "root" extreme point) and introduce two new algebraic operations to decompose and reconstruct these structures.

A. Decomposition Operations: Join and Meet

The authors generalize the "convex sum" and "concave sum" operations (previously defined by Rutschmann and Wettstein for specific "chains") to arbitrary rooted chirotopes.

• Join ($\vee$): Merges two rooted chirotopes $(\chi_1, u_1)$ and $(\chi_2, u_2)$ by identifying their roots ($u_1 = u_2 = u_3$) and their respective neighbors on the convex hull ($u_1^-$ and $u_2^+$ become a new point $x_0$). Geometrically, this places the two point sets "side-by-side" such that the root sits "above" both.
• Meet ($\wedge$): Defined via a twist operation (reversing orientations relative to the root) followed by a join and another twist. Geometrically, this places the sets such that the root sits "below" both.
• Key Theoretical Result: The authors prove that the join and meet of two realizable chirotopes (those corresponding to actual point sets) result in a realizable chirotope. This is non-trivial as it requires constructing specific geometric realizations (using projective transforms and "squeezing" techniques) to ensure the combinatorial definitions hold geometrically.

B. Counting via Bivariate Polynomials

To count triangulations recursively, the authors introduce weak triangulations and bivariate generating polynomials.

• Weak Triangulation: A maximal non-crossing set of segments on a set $X \cup \{u, v\}$ (where $v$ is a "phantom" point opposite to the root $u$) that does not contain the edge $uv$.
• Bivariate Polynomial $P(\chi, u)(u, v)$: This polynomial enumerates weak triangulations, where the exponents of variables $u$ and $v$ track the degrees of the root and the phantom point, respectively.
• Recursive Formulas: The authors derive explicit recursive formulas to compute the polynomial of a join (or meet) based on the polynomials of the components.
  • For a join $(\chi_1, u_1) \vee (\chi_2, u_2)$, the resulting polynomial is a convolution of the input polynomials weighted by a specific kernel polynomial $N_{d_1, d_2}(u)$.
  • This allows the exact computation of the number of triangulations for any chirotope built from successive joins and meets.

3. Key Contributions

1. Generalization of Operations: Extending convex/concave sums from "chains" to the broader class of rooted chirotopes, proving their realizability, and establishing them as valid combinatorial decomposition tools.
2. Bivariate Polynomial Framework: Introducing a method to count triangulations using bivariate polynomials that track vertex degrees. This generalizes previous univariate methods used for chains and allows for the handling of structures that cannot be split into simple upper/lower parts.
3. Asymptotic Analysis of the Double Circle: Applying the recursive framework to the double circle ($DC_n$), a structure previously difficult to analyze precisely.
4. Numerical Investigation: Implementing the recursive algorithm to test if replacing small components in the Koch chain construction with other high-triangulation chirotopes could yield a new record-holder.

4. Results

A. Asymptotic Estimate for the Double Circle

The paper provides a precise asymptotic formula for the number of triangulations of the double circle with $2k$points ($k$internal,$k$ external).

• Previous Estimate: $|T(DC_k)| = (12 + o(1))^k$ (attributed to Hurtado and Noy).
• New Precise Estimate:
  $$|T(DC_k)| \sim \frac{54}{7\sqrt{\pi}} \frac{\sqrt{21}(5 - \sqrt{21})}{(7 - \sqrt{21})^2} 12^{k-2} k^{-3/2}$$
• Methodology: The authors relate $DC_k$ to a sequence of chirotopes constructed via joins. They derive a functional equation for the generating function $F(z, u)$ of these polynomials. Using the kernel method and analytic combinatorics (specifically singularity analysis near the radius of convergence $z=1/12$), they extract the asymptotic behavior.

B. Numerical Experiments

The authors implemented the recursive counting algorithm to search for chirotopes with more triangulations than the Koch chain.

• Experiment: They replaced the base case of the Koch chain construction ($\bar{K}_3$) with every possible 10-point rooted chirotope and iterated the join/meet process up to size 257.
• Outcome: The Koch chain remained the optimal structure found. This suggests that the Koch chain is likely optimal among chirotopes constructible via generalized joins and meets, though it does not constitute a global proof.

5. Significance

• Theoretical Advancement: The work bridges the gap between abstract combinatorial structures (oriented matroids/chirotopes) and geometric realizability, providing a robust toolkit for decomposing complex point sets.
• Algorithmic Efficiency: The recursive polynomial method allows for the exact counting of triangulations for large, structured chirotopes that were previously intractable, moving beyond brute-force enumeration.
• Resolution of Open Questions: The paper settles the precise asymptotic growth rate of the double circle, a fundamental lower-bound candidate in the field of triangulation counting.
• Relation to Prior Work: The paper acknowledges significant overlap with recent work by Bui (2025) regarding "near-edges" and bivariate polynomials. However, this paper distinguishes itself by providing the precise asymptotic analysis of the double circle, which Bui's work (in its current form) does not address.

In summary, this paper establishes a powerful algebraic-combinatorial framework for analyzing planar point sets, successfully applying it to derive new, precise asymptotic results for the double circle and reinforcing the optimality of the Koch chain within specific construction classes.