Matching, Matroids, and Extensions

Monday, June 11, 2012 (all day)

A conference in honour of Bill Cunningham's 65th birthday

Overview

Bill Cunnignham
Matroid theory and matching theory are among the oldest and most established areas in combinatorics, so progress in these areas is typically hard won; nevertheless, the recent advances have been spectacular. There is now an efficient algorithm for solving the weighted matroid matching problem for linear matroids. The 25-year old conjecture that bridgeless cubic graphs have exponentially many perfect matchings has been proved. Groundbreaking approximation algorithms for the graphical travelling salesman problem rely crucially on significant new insights on matching and T-joins. The graph minors project has been extended to binary matroids. And, a 40-year old unimodality conjecture has been proved for linear matroids.

Matroids and matching are two areas that lie close to Bill Cunningham's heart, and these advances provide the perfect backdrop to a Conference celebrating Bill's 65th birthday. As with Bill's interests, the topics covered in the conference are not limited to matching and matroids.

Some photographs from the conference banquet are now available.

Speakers:

  • Robert Bixby (Gurobi Optimization & Rice University)
    • Reminiscences on Matroids, and 1000x Tricks for Mixed Integer Programming
  • Sylvia Boyd (University of Ottawa)
    • Finding 2-Factors Closer to TSP in Cubic Graphs
  • Eddie Cheng (Oakland University)
    • Sufficient Conditions for Matching Preclusions and Conditional Matching Preclusions
  • Kevin Cheung (Carleton University)
    • Excursions with Matchings
  • Maria Chudnovsky (Columbia University)
    • Coloring Some Perfect Graphs
  • Bill Cook (Georgia Tech)
    • Parallel Computation of Lower Bounds for the TSP
  • Jim Geelen (University of Waterloo)
    • Characterizing Graphic Matroids by a System of Linear Equations
  • Satoru Iwata (Kyoto University)
    • Weighted Linear Matroid Parity
  • Kazuo Murota (University of Tokyo)
    • Discrete Legendre Duality in Matrix Pencils
  • Sergey Norin (McGill University)
    • Pairs of Disjoint Cycles
  • Gyula Pap (Eötvös University)
    • Weighted Linear Matroid Matching
  • Bill Pulleyblank (United States Military Academy)
    • Data Analytics, Sports and Optimization
  • Alexander Schrijver (CWI)
    • Stable Sets and Codes
  • András Sebö (CNRS, G-SCOP, Grenoble)
    • TSP and 2ECSS with Matchings, Matroids and Extensions
  • Bruce Shepherd (McGill University)
    • From Online Colouring to Online Vector Bin Packing
  • Donald Wagner (Office of Naval Research)
    • Decomposition of 3-Connected Graphs
  • Francisco Zaragoza (Universidad Autónoma Metropolitana)
    • From Perfect Matchings to the Four Colour Theorem