Persistent graphs and cyclic polytope triangulations

DOI10.1007/S00493-020-4369-5zbMATH Open1499.05307arXiv1911.05012OpenAlexW3106323798MaRDI QIDQ2043765FDOQ2043765

Malte Renken, Vincent Froese

Publication date: 3 August 2021

Published in: Combinatorica (Search for Journal in Brave)

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).

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)

Cites Work

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

Cited In (6)

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

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)