Random triangulations of the d-sphere with minimum volume

2024/08/30 by Agelos Georgakopoulos, Georgakopoulos, Agelos, John Haslegrave +3
Computer Science · #05C65 #60C05 (Primary) #60D05 #90C27 (Secondary) #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Data Management and Algorithms #Digital Image Processing Techniques #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2409.00235

openalex publication_date 2024/08/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30

Abstract

We study a higher-dimensional analogue of the Random Travelling Salesman Problem: let the complete d-dimensional simplicial complex K_n^d on n vertices be equipped with i.i.d. volumes on its facets, uniformly random in [0,1]. What is the minimum volume M_n,d of a sub-complex homeomorphic to the d-dimensional sphere \mathbbS^d, containing all vertices? We determine the growth rate of M_n,2, and prove that it is well-concentrated. For d>2 we prove such results to the extent that current knowledge about the number of triangulations of \mathbbS^d allows. We remark that this can be thought of as a model of random geometry in the spirit of Angel & Schramm's UIPT, and provide a generalised framework that interpolates between our model and the uniform random triangulation of \mathbbS^d.

Related

• The scaling limit of random simple triangulations and random simple quadrangulations
• Sampling triangulations of manifolds using Monte Carlo methods
• The threshold for collapsibility in random complexes
• Filling a triangulation of the 2-sphere
• Randomized construction of complexes with large diameter