×

zbMATH — the first resource for mathematics

Ideal clutters that do not pack. (English) Zbl 1435.90117
Summary: For a clutter \(\mathcal{C}\) over ground set \(E\), a pair of distinct elements \(e, f \in E\) are coexclusive if every minimal cover contains at most one of them. An identification of \(\mathcal{C} \) is another clutter obtained after identifying coexclusive elements of \(\mathcal{C} \). If a clutter is nonpacking, then so is any identification of it. Inspired by this observation, and impelled by the lack of a qualitative characterization for ideal minimally nonpacking (mnp) clutters, we reduce ideal mnp clutters even further by taking their identifications. In doing so, we reveal chains of ideal mnp clutters, demonstrate the centrality of mnp clutters with covering number two, as well as provide a qualitative characterization of irreducible ideal mnp clutters with covering number two. At the core of this characterization lies a class of objects, called marginal cuboids, that naturally give rise to ideal nonpacking clutters with covering number two. We present an explicit class of marginal cuboids, and show that the corresponding clutters have one of \(Q_6, Q_{2, 1}, Q_{10}\) as a minor, where \(Q_6, Q_{2, 1}\) are known ideal mnp clutters, and \(Q_{10}\) is a new ideal mnp clutter.

MSC:
90C27 Combinatorial optimization
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abdi A, Pashkovich K (2017) Deltas, delta minors and delta-free clutters. Submitted.Google Scholar · Zbl 1397.90403
[2] Abdi A, Fukasawa R, Sanità L (2017) Opposite elements in clutters. Math. Oper. Res. ePub ahead of print September 18, https://doi.org/10.1287/moor.2017.0864.Link, Google Scholar
[3] Abdi A, Cornuéjols G, Guričanová N, Lee D (2017) The polarity conjecture. In preparation.Google Scholar
[4] Conforti M, Cornuéjols G, Zambelli G (2014) Integer Programming (Springer, Cham, Switzerland).Crossref, Google Scholar · Zbl 1307.90001
[5] Cornuéjols G, Lee D (2016) On some polytopes contained in the 0, 1 hypercube that have a small Chvátal rank. Louveaux Q, Skutella M, eds. Proc. 18th Internat. Conf. Integer Programming Combinatorial Optimization, IPCO ’16, Lecture Notes in Computer Science, Vol. 9682 (Springer International, Cham, Switzerland), 300-311.Crossref, Google Scholar · Zbl 1419.90092
[6] Cornuéjols G, Guenin B, Margot F (2000) The packing property. Math. Programming 89(1):113-126.Crossref, Google Scholar · Zbl 1033.90099
[7] Edmonds J, Fulkerson DR (1970) Bottleneck extrema. J. Combin. Theory Ser. B 8(3):299-306.Crossref, Google Scholar · Zbl 0218.05006
[8] Fulkerson DR (1971) Blocking and anti-blocking pairs of polyhedra. Math. Programming 1(1):168-194.Crossref, Google Scholar · Zbl 0254.90054
[9] Guenin B (1998) Perfect and ideal 0, ± 1 matrices. Math. Oper. Res. 23(2):322-338.Link, Google Scholar · Zbl 0982.15020
[10] Isbell JR (1958) A class of simple games. Duke Math. J. 25(3):423-439.Crossref, Google Scholar · Zbl 0083.14301
[11] Lehman A (1979) On the width-length inequality. Math. Programming 17(1):403-417.Crossref, Google Scholar · Zbl 0418.90040
[12] Lehman A (1990) The width-length inequality and degenerate projective planes. DIMACS, Vol. 1, 101-105.Google Scholar · Zbl 0747.05063
[13] Lovász L (1972) Minimax Theorems for Hypergraphs, Lecture Notes in Mathematics, Vol. 411 (Springer, Berlin), 111-126.Google Scholar
[14] Lucchesi CL, Younger DH (1978) A minimax relation for directed graphs. J. London Math. Soc. 2(17):369-374.Crossref, Google Scholar · Zbl 0392.05029
[15] Nobili P, Sassano A (1998) (0, ± 1) ideal matrices. Math. Programming 80(3):265-281.Crossref, Google Scholar · Zbl 0894.90126
[16] Schrijver A (1980) A counterexample to a conjecture of Edmonds and Giles. Discrete Math. 32(2):213-214.Crossref, Google Scholar · Zbl 0445.05047
[17] Seymour PD (1976) The forbidden minors of binary matrices. J. London Math. Soc. 2(12):356-360.Crossref, Google Scholar · Zbl 0351.05023
[18] Seymour PD (1977) The matroids with the max-flow min-cut property. J. Combin. Theory Ser. B 23(2-3):189-222.Crossref, Google Scholar · Zbl 0375.05022
[19] Seymour PD (1990) On Lehman’s width-length characterization. DIMACS, Vol. 1, 107-117.Google Scholar · Zbl 0747.05066
[20] Woodall DR (1978) Menger and Kőnig Systems , · Zbl 0391.05016
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.