The tau=2 conjecture and multipartite clutters

Speaker: Dabeen Lee (IBS)

Abstract: Consider a finite set of elements V and a family C of subsets of V , called members. We say that C is a clutter if no member is contained in another. A cover of C is a subset of V that intersects every member of the family. We say that the family C packs if the minimum size of a cover equals the maximum number of disjoint members. Many well-known classical theorems of combinatorics establish the packing property for relevant particular clutters, and the weighted and fractional versions of these notions have also been extensively studied. As generally stated as it is here, the property is not closed under taking the natural "minors". Cornuéjols, Guenin, and Margot (2000) introduced the packing property of clutters which means that every minor of it packs; ideal clutters characterized by a celebrated property of Lehman, are those satisfying a fractional version.

If true, the heart of the packing property is the so-called "tau = 2" Conjecture, -- analogous to the Strong Perfect Graph Theorem-- , proposed by Cornuéjols, Guenin, and Margot, stating that every ideal minimally non-packing clutter has a cover of size 2. They proved that the conjecture implies the "Replication Conjecture" of Conforti and Cornuéjols (1993), the set covering analogue of the replication lemma for perfect graphs.

In this talk, we discuss the class of "multipartite clutters", designed to provide tools and techniques to certify the "tau = 2" conjecture or to find a possible counterexample to the conjecture. We show that the "tau = 2" conjecture can be equivalently restated in terms of multipartite clutters, thus sitting at the core of answering the "tau = 2" conjecture. Multipartite clutters admit an equivalent graph representation, which makes it easier to decide whether a multipartite clutter is ideal and check if it packs. Based on this, we develop an efficient computational method to look for a possible counterexample. The talk is based on joint work with Ahmad Abdi and Gérard Cornuéjols.

Date and time: 10/12/2020 at 14:30 (Paris time)

Link to the talk: https://bbb-temp.grenet.fr/b/lou-9x7-69p