Algebraic and combinatorial properties of ideals and algebras of uniform clutters of TDI systems

DOI10.1007/S10878-009-9244-7zbMATH Open1319.05068arXiv0801.1478OpenAlexW2159261699MaRDI QIDQ491193FDOQ491193

Authors: Luis A. Dupont, Rafael H. Villarreal 

Publication date: 24 August 2015

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Abstract: Let C be a uniform clutter, i.e., all the edges of C have the same size, and let A be the incidence matrix of C. We denote the column vectors of A by v1,...,vq. The vertex covering number of C, denoted by g, is the smallest number of vertices in any minimal vertex cover of C. Under certain conditions we prove that C is vertex critical. If C satisfies the max-flow min-cut property, we prove that A diagonalizes over the integers to an identity matrix and that v1,...,vq is a Hilbert basis. It is shown that if C has a perfect matching such that C has the packing property and g=2, then A diagonalizes over the integers to an identity matrix. If A is a balanced matrix we prove that any regular triangulation of the cone generated by v1,...,vq is unimodular. Some examples are presented to show that our results only hold for uniform clutters. These results are closely related to certain algebraic properties, such as the normality or torsion freeness, of blowup algebras of edge ideals and to finitely generated abelian groups. They are also related to the theory of Gr"obner bases of toric ideals and to Ehrhart rings.

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

Recommendations

• Cohen-Macaulay clutters with combinatorial optimization properties and parallelizations of normal edge ideals
• Edge ideals of clique clutters of comparability graphs and the normality of monomial ideals
• Blowup algebras of square-free monomial ideals and some links to combinatorial optimization problems
• A note on Rees algebras and the MFMC property

zbMATH Keywords

normalityedge idealRees algebraSmith normal formbalanced matrixuniform clutterEhrhart ringHilbert basesmax-flow min-cutunimodular regular triangulation

Mathematics Subject Classification ID

Polynomial rings and ideals; rings of integer-valued polynomials (13F20) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Cites Work

• The Two-Triangle Case of the Acquaintance Graph
• Title not available (Why is that?)
• Combinatorics and commutative algebra.
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Combinatorial optimization. Packing and covering
• Title not available (Why is that?)
• Base-sortable matroids and Koszulness of semigroup rings
• Relative volumes and minors in monomial subrings.
• Rees cones and monomial rings of matroids
• Blowup algebras of square-free monomial ideals and some links to combinatorial optimization problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Bounds For Invariants of Edge-Rings
• A note on Rees algebras and the MFMC property
• Rees algebras and polyhedral cones of ideals of vertex covers of perfect graphs

Cited In (5)

• Consequences of the packing problem
• Depth and regularity of monomial ideals via polarization and combinatorial optimization
• Cohen-Macaulay clutters with combinatorial optimization properties and parallelizations of normal edge ideals
• Toric algebra of hypergraphs
• Rees algebras of filtrations of covering polyhedra and integral closure of powers of monomial ideals

Uses Software

• Macaulay2
• Normaliz

This page was built for publication: Algebraic and combinatorial properties of ideals and algebras of uniform clutters of TDI systems

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