UBC CORDS/COCANA Operations Research Seminar: Olha Silina
Topic
A Polyhedral View on the Perfect Matching Lattice and Petersen Graph
Speakers
Details
Abstract: Let $G=(V,E)$ be a matching covered graph, let $P$ be its perfect matching polytope, and let $L$ be
the integer lattice generated by the integral points in $P$. In well-celebrated works of Lovász (1987),
and Carvalho, Lucchesi, and Murty (series of three papers, 2002), it was shown that: (a) $L$ has a lattice basis consisting solely of incidence vectors of some perfect matchings of $G$, (b) $2x \in L$ for all integral $x \in lin(P)$, and (c) if $G$ has no Petersen brick then $x \in L$. The original proofs are heavily reliant on the structure of perfect matchings, odd cuts, and removable edges in the graph. In this talk, we will give a short novel proof of these results by studying the facial structure of $P$ and its relationship with the lattice $L$. In our approach, the Petersen graph emerges naturally as the only graph with a specific polyhedral formulation.
Additional Information
This event is a part of the CORDS/COCANA Operations Research Seminar.
For the current seminar schedule please go to the Seminar website.