A new infinite class of ideal minimally non-packing clutters

Abdi, AhmadORCID logo; Cornuéjols, Gérard; and Superdock, Matt (2021) A new infinite class of ideal minimally non-packing clutters. Discrete Mathematics, 344 (7): 112413. ISSN 0012-365X
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

picture_as_pdf
subject
Accepted Version

Download

Atom BibTeX OpenURL ContextObject in Span OpenURL ContextObject Dublin Core MPEG-21 DIDL Data Cite XML EndNote HTML Citation METS MODS RIOXX2 XML Reference Manager Refer ASCII Citation
Export

Downloads