×

Cuboids, a class of clutters. (English) Zbl 1436.05023

Summary: The \(\tau =2\) conjecture, the replication conjecture and the \(f\)-flowing conjecture, and the classification of binary matroids with the sums of circuits property are foundational to clutter theory and have far-reaching consequences in combinatorial optimization, matroid theory and graph theory. We prove that these conjectures and results can equivalently be formulated in terms of cuboids, which form a special class of clutters. Cuboids are used as means to (a) manifest the geometry behind primal integrality and dual integrality of set covering linear programs, and (b) reveal a geometric rift between these two properties, in turn explaining why primal integrality does not imply dual integrality for set covering linear programs. Along the way, we see that the geometry supports the \(\tau=2\) conjecture. Studying the geometry also leads to over 700 new ideal minimally non-packing clutters over at most 14 elements, a surprising revelation as there was once thought to be only one such clutter.

MSC:

05B35 Combinatorial aspects of matroids and geometric lattices
52B40 Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.)
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] A. Abdi, A code for generating all non-isomorphic strictly non-polar sets of fixed dimension and bounded degree, GitHub repository, 2019 https://github.com/ahmad-abdi/cuboids-code/.
[2] Abdi, A., Ideal Clutters (2018), University of Waterloo, Ph.D. dissertation · Zbl 1435.90117
[3] Abdi, A.; Cornuéjols, G.; Lee, D., Resistant sets in the unit hypercube, Math. Oper. Res. (2019), in press
[4] Abdi, A.; Cornuéjols, G.; Pashkovich, K., Ideal clutters that do not pack, Math. Oper. Res., 43, 2, 533-553 (2018) · Zbl 1435.90117
[5] Barahona, F.; Grötschel, M., On the cycle polytope of a binary matroid, J. Combin. Theory Ser. B, 40, 1, 40-62 (1986) · Zbl 0596.05018
[6] Bouchet, A., Greedy algorithm and symmetric matroids, Math. Program., 38, 2, 147-159 (1987) · Zbl 0633.90089
[7] Conforti, M.; Cornuéjols, G., Clutters that pack and the max-flow min-cut property: a conjecture, (The Fourth Bellairs Workshop on Combinatorial Optimization (1993))
[8] Conforti, M.; Cornuéjols, G.; Zambelli, G., Integer Programming (2014), Springer · Zbl 1307.90001
[9] Cornuéjols, G., Combinatorial Optimization, Packing and Covering (2001), SIAM: SIAM Philadelphia · Zbl 0972.90059
[10] Cornuéjols, G.; Guenin, B.; Margot, F., The packing property, Math. Program. Ser. A, 89, 1, 113-126 (2000) · Zbl 1033.90099
[11] Cornuéjols, G.; Novick, B., Ideal 0, 1 matrices, J. Combin. Theory Ser. B, 60, 145-157 (1994) · Zbl 0794.05077
[12] Edmonds, J.; Fulkerson, D. R., Bottleneck extrema, J. Combin. Theory Ser. B, 8, 299-306 (1970) · Zbl 0218.05006
[13] Edmonds, J.; Giles, R., A min-max relation for submodular functions on graphs, (Annals of Discrete Math., vol. 1 (1977)), 185-204 · Zbl 0373.05040
[14] Edmonds, J.; Johnson, E. L., Matchings, Euler tours and the Chinese postman problem, Math. Program., 5, 88-124 (1973) · Zbl 0281.90073
[15] Flatt, M.; PLT, Reference: Racket (2010), PLT Design Inc., Technical report PLT-TR-2010-1
[16] Flores, A.; Gitler, I.; Reyes, E., On 2-partitionable clutters and the MFMC property, Adv. Appl. Discrete Math., 2, 1, 59-84 (2008) · Zbl 1211.05090
[17] Fulkerson, D. R., Blocking and anti-blocking pairs of polyhedra, Math. Program., 1, 168-194 (1971) · Zbl 0254.90054
[18] Guenin, B., A short proof of Seymour’s characterization of the matroids with the max-flow min-cut property, J. Combin. Theory Ser. B, 86, 2, 273-279 (2002) · Zbl 1023.05029
[19] Guenin, B., Perfect and ideal \(0, \pm 1\) matrices, Math. Oper. Res., 23, 2, 322-338 (1998) · Zbl 0982.15020
[20] Hoffman, A. J., A generalization of max flow-min cut, Math. Program., 6, 1, 352-359 (1974) · Zbl 0357.90068
[21] Isbell, J. R., A class of simple games, Duke Math. J., 25, 3, 423-439 (1958) · Zbl 0083.14301
[22] Lee, J., Cropped cubes, J. Comb. Optim., 7, 2, 169-178 (2003) · Zbl 1035.90108
[23] Lehman, A., A solution of the Shannon switching game, J. Soc. Indust. Appl. Math., 12, 4, 687-725 (1964) · Zbl 0137.38704
[24] Lehman, A., On the width-length inequality, Math. Program., 17, 1, 403-417 (1979) · Zbl 0418.90040
[25] Lehman, A., The width-length inequality and degenerate projective planes, (DIMACS, vol. 1 (1990)), 101-105 · Zbl 0747.05063
[26] Lovász, L., Minimax Theorems for Hypergraphs, Lecture Notes in Mathematics, vol. 411, 111-126 (1972), Springer-Verlag · Zbl 0305.05129
[27] Mantel, W., Vraagstuk XXVIII, Wiskundige Opgaven, 10, 60-61 (1910) · JFM 38.0270.01
[28] Nobili, P.; Sassano, A., \((0, \pm 1)\) ideal matrices, Math. Program., 80, 3, 265-281 (1998) · Zbl 0894.90126
[29] Novick, B.; Sebő, A., On combinatorial properties of binary spaces, (Integer Programming and Combinatorial Optimization, vol. 4 (1995)), 212-227 · Zbl 1498.90197
[30] Oxley, J., Matroid Theory (2011), Oxford University Press: Oxford University Press New York · Zbl 1254.05002
[31] Schrijver, A., A counterexample to a conjecture of Edmonds and Giles, Discrete Math., 32, 213-214 (1980) · Zbl 0445.05047
[32] Seymour, P. D., Decomposition of regular matroids, J. Combin. Theory Ser. B, 28, 305-359 (1980) · Zbl 0443.05027
[33] Seymour, P. D., Matroids and multicommodity flows, European J. Combin., 2, 257-290 (1981) · Zbl 0479.05023
[34] Seymour, P. D., On Lehman’s width-length characterization, DIMACS, 1, 107-117 (1990) · Zbl 0747.05066
[35] Seymour, P. D., Sums of circuits, (Bondy, J. A.; Murty, U. S.R., Graph Theory and Related Topics (1979), Academic Press: Academic Press New York), 342-355 · Zbl 0465.05042
[36] Seymour, P. D., The matroids with the max-flow min-cut property, J. Combin. Theory Ser. B, 23, 189-222 (1977) · Zbl 0375.05022
[37] Szekeres, G., Polyhedral decomposition of cubic graphs, Bull. Aust. Math. Soc., 8, 367-387 (1973) · Zbl 0249.05111
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.