TY - JOUR

T1 - Opposite elements in clutters

AU - Abdi, Ahmad

AU - Fukasawa, Ricardo

AU - Sanità, Laura

PY - 2018/5

Y1 - 2018/5

N2 - Let E be a finite set of elements, and let L be a clutter over ground set E. We say distinct elements e, f are opposite if every member and every minimal cover of L contains at most one of e, f. In this paper, we investigate opposite elements and reveal a rich theory underlying such a seemingly simple restriction. The clutter C obtained from L after identifying some opposite elements is called an identification of L; inversely, L is called a split of C. We will show that splitting preserves three clutter properties, i.e., idealness, the max-flow min-cut property, and the packing property. We will also display several natural examples in which a clutter does not have these properties but a split of them does. We will develop tools for recognizing when splitting is not a useful operation, and as well, we will characterize when identification preserves the three mentioned properties. We will also make connections to spanning arborescences, Steiner trees, comparability graphs, degenerate projective planes, binary clutters, matroids, as well as the results of Menger, Ford and Fulkerson, the Replication Conjecture, and a conjecture on ideal, minimally nonpacking clutters.

AB - Let E be a finite set of elements, and let L be a clutter over ground set E. We say distinct elements e, f are opposite if every member and every minimal cover of L contains at most one of e, f. In this paper, we investigate opposite elements and reveal a rich theory underlying such a seemingly simple restriction. The clutter C obtained from L after identifying some opposite elements is called an identification of L; inversely, L is called a split of C. We will show that splitting preserves three clutter properties, i.e., idealness, the max-flow min-cut property, and the packing property. We will also display several natural examples in which a clutter does not have these properties but a split of them does. We will develop tools for recognizing when splitting is not a useful operation, and as well, we will characterize when identification preserves the three mentioned properties. We will also make connections to spanning arborescences, Steiner trees, comparability graphs, degenerate projective planes, binary clutters, matroids, as well as the results of Menger, Ford and Fulkerson, the Replication Conjecture, and a conjecture on ideal, minimally nonpacking clutters.

KW - Arborescences

KW - Ideal clutters

KW - Packing property

KW - Set covering polyhedron

KW - The replication conjecture

UR - http://www.scopus.com/inward/record.url?scp=85047087456&partnerID=8YFLogxK

U2 - 10.1287/moor.2017.0864

DO - 10.1287/moor.2017.0864

M3 - Article

AN - SCOPUS:85047087456

SN - 0364-765X

VL - 43

SP - 428

EP - 459

JO - Mathematics of Operations Research

JF - Mathematics of Operations Research

IS - 2

ER -