Graphs and Matroids - Ahmad Abdi

Wednesday, March 13, 2019 3:30 pm - 3:30 pm EDT (GMT -04:00)

Title: Ideal clutters and k-wise intersecting families

Speaker: Ahmad Abdi
Affiliation: Carnegie Mellon University
Room: MC 5501

Abstract:

A clutter is *ideal* if the corresponding set covering polyhedron has no fractional vertices, and it is *k-wise intersecting* if the members don’t have a common element but every k members do. We conjecture that there is a constant k such that every k-wise intersecting clutter is non-ideal.

I will show how this conjecture for k=4 would be an extension of Jaeger’s 8-flow theorem, and how a variation of the conjecture for k=3 would be an extension of Tutte’s 4-flow conjecture. I will also discuss connections to tangential 2-blocks, binary projective geometries, the sums of circuits property, etc.

Joint work with Gerard Cornuejols and Dabeen Lee.