Next week, Tony Huynh is giving a talk in the Combinatorial Mathematics Society of Australasia Seminar which many of our readers may be interested in. Here is the info. The announcement for next week’s Graphs and Matroids talk will follow soon.
Tuesday, October 6, 9pm ET (11am AEST)
Tony Huynh, Monash U
Idealness of k-wise intersecting families
Zoom/password: see CMSA website
A clutter is a hypergraph such that no hyperedge is contained in another hyperedge. It is $k$-wise intersecting if every $k$ hyperedges intersect, but there is no vertex contained in all the hyperedges. We conjecture that every $4$-wise intersecting clutter is not ideal. Idealness is an important geometric property, which roughly says that the minimum covering problem for the clutter can be efficiently solved by a linear program. As evidence for our conjecture, we prove it for the class of binary clutters. Our proof combines ideas from the theory of clutters, graphs, and matroids. For example, it uses Jaeger’s $8$-flow theorem for graphs, and Seymour’s characterization of the binary matroids with the sums of circuits property. We also show that $4$ cannot be replaced by $3$ in our conjecture, where the counterexample of course comes from the Petersen Graph.
This is joint work with Ahmad Abdi, Gérard Cornuéjols, and Dabeen Lee.