pith. sign in

arxiv: 1210.4753 · v1 · pith:7I5KTRCHnew · submitted 2012-10-17 · 🧮 math.CO · cs.DM

On ideal minimally non-packing clutters

classification 🧮 math.CO cs.DM
keywords clutteridealminimallynon-packingstepconditionsfirsttilde
0
0 comments X
read the original abstract

We consider the following conjecture proposed by Cornu\'ejols, Guenin and Margot: every ideal minimally non-packing clutter has a transversal of size 2. For a clutter C, the tilde clutter is the set of hyperedges of C which intersect any minimum transversal in exactly one element. We divide the (non-)existence problem of an ideal minimally non-packing clutter D into two steps. In the first step, we give necessary conditions for C = the tilde clutter of D when a clutter D is an ideal minimally non-packing clutter. In the second step, for a clutter C satisfying the conditions in the first step, we consider whether C has an ideal minimally non-packing clutter D with C= the tilde clutter of D. We show that the clutter of a combinatorial affine plane satisfies the conditions in the first step. Moreover, we show that the clutter of a combinatorial affine plane does not have any ideal minimally non-packing clutter of blocking number at least 3.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.