Cycle algebras and polytopes of matroids

DOI10.1016/J.JPAA.2023.107574MaRDI QIDQ6199040OpenAlexFDO

Authors Tim Römer, Sara Saeedi Madani

Publication date 23 February 2024

Published in Journal of Pure and Applied Algebra (Search for Journal in Brave)

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

zbMATH Keywords

matroidcut polytopecycle idealalgebra retractcycle polytopecycle algebra

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Combinatorial aspects of commutative algebra (05E40) Combinatorial aspects of matroids and geometric lattices (05B35)

Abstract: Cycle polytopes of matroids have been introduced in combinatorial optimization as a generalization of important classes of polyhedral objects like cut polytopes and Eulerian subgraph polytopes associated to graphs. Here we start an algebraic and geometric investigation of these polytopes by studying their toric algebras, called cycle algebras, and their defining ideals. Several matroid operations are considered which determine faces of cycle polytopes that belong again to this class of polyhedral objects. As a key technique used in this paper, we study certain minors of given matroids which yield algebra retracts on the level of cycle algebras. In particular, that allows us to use a powerful algebraic machinery. As an application, we study highest possible degrees in minimal homogeneous systems of generators of defining ideals of cycle algebras as well as interesting cases of cut polytopes and Eulerian subgraph polytopes.

Recommendations

• Retracts and algebraic properties of cut algebras
• Master polytopes for cycles of binary matroids
• Matroid polytopes and their volumes
• Decomposition and optimization over cycles in binary matroids
• On the cycle polytope of a binary matroid

Cites work

• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• scientific article; zbMATH DE number 5567196 (Why is no real title available?)
• scientific article; zbMATH DE number 7351371 (Why is no real title available?)
• A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs
• A note on seminormality of cut polytopes
• Application of cut polyhedra. I
• Applications of cut polyhedra. II
• Betti numbers of cut ideals of trees
• Combinatorial pure subrings.
• Cut ideals of \(K_{4}\)-minor free graphs are generated by quadrics
• Cut polytopes of minor-free graphs
• Decomposition and optimization over cycles in binary matroids
• Generalized cut and metric polytopes of graphs and simplicial complexes
• Geometry of cuts and metrics
• Gorenstein cut polytopes
• Lifting facets of the cut polytope
• Markov bases of binary graph models of \(K_{4}\)-minor free graphs
• Master polytopes for cycles of binary matroids
• Normality of cut polytopes of graphs is a minor closed property
• On cardinality constrained cycle and path polytopes
• On cycle cones and polyhedra
• On the cut polytope
• On the cycle polytope of a binary matroid
• On the cycle polytope of a directed graph and its relaxations
• Parallel recognition of series-parallel graphs
• Polytopes, Rings, and K-Theory
• Properties of cut ideals associated to ring graphs
• Retracts and algebraic properties of cut algebras
• Supereulerian graphs: A survey
• The even and odd cut polytopes
• Toric geometry of cuts and splits
• Toric varieties

This page was built for publication: Cycle algebras and polytopes of matroids

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