Cycle algebras and polytopes of matroids

DOI10.1016/J.JPAA.2023.107574arXiv2105.00185OpenAlexW3158812388MaRDI QIDQ6199040FDOQ6199040

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)

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.

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)

Cites Work

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

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)