On 2-partitionable clutters and the MFMC property

MaRDI QIDQ3626867zbMATH OpenFDO

Authors Alejandro Flores-Méndez, Isidoro Gitler, Enrique Reyes

Publication date 14 May 2009

Full work available at URL https://arxiv.org/abs/0806.1772, http://pphmj.com/abstract/3581.htm

zbMATH Keywords

normalityhypergraphsRees algebrascluttersMax-flow min-cutmengerian

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Hypergraphs (05C65) Special types (Cohen-Macaulay, Gorenstein, Buchsbaum, etc.) (13H10)

Abstract: We introduce 2-partitionable clutters as the simplest case of the class of $k$-partitionable clutters and study some of their combinatorial properties. In particular, we study properties of the rank of the incidence matrix of these clutters and properties of their minors. A well known conjecture of Conforti and Cornu'ejols cite{ConfortiCornuejols,cornu-book} states: That all the clutters with the packing property have the max-flow min-cut property, i.e. are mengerian. Among the general classes of clutters known to verify the conjecture are: balanced clutters (Fulkerson, Hoffman and Oppenheim cite{FulkersonHoffmanOppenheim}), binary clutters (Seymour cite{Seymour}) and dyadic clutters (Cornu'ejols, Guenin and Margot cite{CornuejolsGueninMargot}). We find a new infinite family of 2-partitionable clutters, that verifies the conjecture. On the other hand we are interested in studying the normality of the Rees algebra associated to a clutter and possible relations with the Conforti and Cornu'ejols conjecture. In fact this conjecture is equivalent to an algebraic statement about the normality of the Rees algebra cite{rocky}.

Recommendations

• A note on Rees algebras and the MFMC property
• Clutters with \(\tau_ 2 \Relbar 2\tau\)
• On ideal minimally non-packing clutters
• Cohen-Macaulay clutters with combinatorial optimization properties and parallelizations of normal edge ideals
• Mengerian quasi-graphical families and clutters

Cited in

(5)

• A note on clutter partitions
• Cuboids, a class of clutters
• A note on Rees algebras and the MFMC property
• Mengerian quasi-graphical families and clutters
• Clutters with \(\tau_ 2 \Relbar 2\tau\)

This page was built for publication: On 2-partitionable clutters and the MFMC property

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