Tutte Colloquium - Ahmad Abdi

Title: Ideal matrices

Abstract:

A 0,1 matrix M is *ideal* if the set covering system Mx>=1, x>=0 gives an integral polyhedron. Ideal matrices are prevalent in Combinatorics and Optimization, coming from totally unimodular matrices, balanced hypergraphs, two-terminal paths in a graph, dijoins of a directed graph, binary matroids with the sums of circuits property, among many other examples.

In this talk, we address the problem of recognizing ideal matrices. We will see how this problem is tied to understanding totally dual integral set covering systems, intersecting families, odd holes in graphs, and projective planes in designs.

Based on joint works with Gerard Cornuejols and Dabeen Lee.