A new infinite class of ideal minimally non-packing clutters

Abdi, A.ORCID logo, Cornuéjols, G. & Superdock, M. (2021). A new infinite class of ideal minimally non-packing clutters. Discrete Mathematics, 344(7). https://doi.org/10.1016/j.disc.2021.112413
Copy

The τ = 2 Conjecture predicts that every ideal minimally non-packing clutter has covering number two. In the original paper where the conjecture was proposed, in addition to an infinite class of such clutters, thirteen small instances were provided. The construction of the small instances followed an ad-hoc procedure and why it worked has remained a mystery, until now. In this paper, using the theory of clean tangled clutters, we identify key structural features about these small instances, in turn leading us to a second infinite class of ideal minimally non-packing clutters with covering number two. Unlike the previous infinite class consisting of cuboids with unbounded rank, our class is made up of non-cuboids, all with rank three.

picture_as_pdf

subject
Accepted Version

Download

Export as

EndNote BibTeX Reference Manager Refer Atom Dublin Core JSON Multiline CSV
Export