Tutte Colloquium - Ahmad AbdiExport this event to calendar

Friday, March 15, 2019 — 3:30 PM EDT

Title: Ideal matrices

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

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.

Location 
MC - Mathematics & Computer Building
5501
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
  1. 2019 (143)
    1. October (14)
    2. September (15)
    3. August (9)
    4. July (17)
    5. June (18)
    6. May (16)
    7. April (9)
    8. March (24)
    9. February (13)
    10. January (8)
  2. 2018 (138)
    1. December (2)
    2. November (18)
    3. October (14)
    4. September (9)
    5. August (2)
    6. July (10)
    7. June (13)
    8. May (17)
    9. April (9)
    10. March (19)
    11. February (14)
    12. January (11)
  3. 2017 (103)
  4. 2016 (137)
  5. 2015 (136)
  6. 2014 (88)
  7. 2013 (48)
  8. 2012 (39)
  9. 2011 (36)
  10. 2010 (40)
  11. 2009 (40)
  12. 2008 (39)
  13. 2007 (15)