2012/10/17 by Kenji Kashiwabara, Kashiwabara, Kenji, Tadashi Sakuma +1
Computer Science · Mathematics · #05B40 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #acm:05B40 #cs.DM #math.CO #msc:05B40
paper · pdf · doi:10.48550/arxiv.1210.4753
18 pages, 3 figures
arxiv created 2012/10/17 · arxiv updated 2012/10/18
We consider the following conjecture proposed by Cornuéjols, 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.