Root polytopes and Jaeger‐type dissections for directed graphs

DOI10.1112/MTK.12163MaRDI QIDQ6074977zbMATH OpenOpenAlexFDO

Authors Tamás Kálmán, Lilla Tóthmérész

Publication date 20 September 2023

Published in Mathematika (Search for Journal in Brave)

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

zbMATH Keywords

layer-complete directed graphsribbon structuresspanning trees

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph polynomials (05C31) Graph representations (geometric and intersection representations, etc.) (05C62) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Shellability for polytopes and polyhedra (52B22)

Abstract: We associate root polytopes to directed graphs and study them by using ribbon structures. Most attention is paid to what we call the semi-balanced case, i.e., when each cycle has the same number of edges pointing in the two directions. Given a ribbon structure, we identify a natural class of spanning trees and show that, in the semi-balanced case, they induce a shellable dissection of the root polytope into maximal simplices. This allows for a computation of the $h^{\ast }$-vector of the polytope and for showing some properties of this new graph invariant, such as a product formula and that in the planar case, the $h^{\ast }$-vector is equivalent to the greedoid polynomial of the dual graph. We obtain a general recursion relation as well. We also work out the case of layer-complete directed graphs, where our method recovers a previously known triangulation. Indeed our dissection is often but not always a triangulation; we address this with a series of examples.

Recommendations

• Faces of root polytopes
• scientific article; zbMATH DE number 617570
• Root polytopes, Tutte polynomials, and a duality theorem for bipartite graphs
• Root polytopes, triangulations, and the subdivision algebra, II
• Complexes of directed trees of complete multipartite graphs

Cites work

• A characterization of the Tutte polynomial via combinatorial embeddings
• A combinatorial model for the homfly polynomial
• A version of Tutte's polynomial for hypergraphs
• Abelian sandpile model and Biggs-Merino polynomial for directed graphs
• Arithmetic aspects of symmetric edge polytopes
• Biased graphs. I: Bias, balance, and gains
• Chip-firing game and a partial Tutte polynomial for Eulerian digraphs
• Faces of root polytopes
• Homotopy properties of greedoids
• scientific article; zbMATH DE number 988665 (Why is no real title available?)
• scientific article; zbMATH DE number 3742601 (Why is no real title available?)
• Hypergraph polynomials and the Bernardi process
• Integer points in polyhedra
• Interior polynomial for signed bipartite graphs and the HOMFLY polynomial
• Normal polytopes arising from finite graphs
• Permutohedra, Associahedra, and Beyond
• Root polytopes, parking functions, and the HOMFLY polynomial
• Root polytopes, Tutte polynomials, and a duality theorem for bipartite graphs
• Signed graphs
• Tutte polynomial, subgraphs, orientations and sandpile model: new connections via embeddings

Cited in

(7)

• The separator theorem for rooted directed vertex graphs
• Faces of root polytopes
• h^* -vectors of graph polytopes using activities of dissecting spanning trees
• A geometric proof for the root-independence of the greedoid polynomial of Eulerian branching greedoids
• A Whitney polynomial for hypermaps
• Degrees of interior polynomials and parking function enumerators
• A Whitney polynomial for hypermaps

This page was built for publication: Root polytopes and Jaeger‐type dissections for directed graphs

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