2026-09-05T11:58:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25831 2026-06-23T12:59:11Z ddc:004 open_access

The Typical Algebraic Shifting of Graphs and Surfaces Bulavka, Denys Nevo, Eran Peled, Yuval Algebraic shifting Delaunay triangulation surfaces random triangulation area rigidity We initiate a statistical study of Kalai’s exterior algebraic shifting, focusing on concentration phenomena for random triangulations of a fixed space. First, for a uniform n-vertex refinement of any given graph G, we show that asymptotically almost-surely (a.a.s.) its exterior algebraic shifting is an explicit shifted graph depending only on n and the Betti numbers of G. Next, for any given compact connected Riemannian surface S, sample n points independently at random according to the volume measure, and consider the resulted a.a.s. unique Delaunay triangulation. We prove that a.a.s. its exterior algebraic shifting is an explicit shifted complex depending only on n and the Euler genus of S, and in particular is area-rigid. In both results the expected shifted complex is a homology lex-segment complex, a notion we define combinatorially and characterize numerically à la Björner-Kalai. As a tool to prove the result on surfaces, we prove a universality result on edge contractions: for every fixed surface triangulation K, every dense enough point set in the surface yields a Delaunay triangulation that edge contracts to K. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Denys Bulavka and Eran Nevo and Yuval Peled 2026 Is Part Of LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2026.25 urn:nbn:de:0030-drops-258312 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.25 eng https://creativecommons.org/licenses/by/4.0/legalcode