Persistent graphs and cyclic polytope triangulations

DOI10.1007/S00493-020-4369-5MaRDI QIDQ2043765zbMATH OpenOpenAlexFDO

Authors Vincent Froese, Malte Renken

Publication date 3 August 2021

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1911.05012

zbMATH Keywords

triangulationspersistent graphs

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Three-dimensional polytopes (52B10) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Enumeration in graph theory (05C30) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: We prove a bijection between the triangulations of the 3-dimensional cyclic polytope C(n+2, 3) and persistent graphs with n vertices. We show that under this bijection the Stasheff-Tamari orders on triangulations naturally translate to subgraph inclusion between persistent graphs. Moreover, we describe a connection to the second higher Bruhat order B(n, 2). We additionally give an algorithm to efficiently enumerate all persistent graphs on n vertices and thus all triangulations of C(n+2, 3).

Recommendations

• New combinatorial descriptions of the triangulations of cyclic polytopes and the second higher Stasheff--Tamari posets
• On subdivision posets of cyclic polytopes
• Triangulations of cyclic polytopes and higher Bruhat orders
• scientific article; zbMATH DE number 1741017
• New counts for the number of triangulations of cyclic polytopes

Cites work

• scientific article; zbMATH DE number 29045 (Why is no real title available?)
• A fast shortest path algorithm on terrain-like graphs
• A survey of the higher Stasheff-Tamari orders
• From time series to complex networks: the visibility graph
• Lectures on Polytopes
• New combinatorial descriptions of the triangulations of cyclic polytopes and the second higher Stasheff--Tamari posets
• New counts for the number of triangulations of cyclic polytopes
• On characterizing terrain visibility graphs
• On counting triangulations in \(d\) dimensions
• Primitive Radon partitions for cyclic polytopes
• Sweeps, arrangements and signotopes
• Terrain visibility graphs: persistence is not enough
• The higher Stasheff‐Tamari posets
• The maximum numbers of faces of a convex polytope
• The number of triangulations of the cyclic polytope \(C(n,n-4)\)
• Triangulations of cyclic polytopes
• Triangulations of cyclic polytopes and higher Bruhat orders
• Triangulations. Structures for algorithms and applications
• VISIBILITY GRAPHS OF STAIRCASE POLYGONS WITH UNIFORM STEP LENGTH
• Visibility graphs of staircase polygons and the weak Bruhat order. I: From visibility graphs to maximal chains

Cited in

(7)

• Terrain-like graphs and the median Genocchi numbers
• Recursive constructions for the higher Stasheff-Tamari orders in dimension three using the outer Tamari and Tamari block posets
• Reeb graphs: approximation and persistence
• On persistent directed graphs
• Maximally persistent cycles in random geometric complexes
• Triangulations of cyclic polytopes
• New interpretations of the higher Stasheff-Tamari orders

This page was built for publication: Persistent graphs and cyclic polytope triangulations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2043765)