A Polyhedral View on the Perfect Matching Lattice and Petersen Graph
Olha Silina (UBC Vancouver)
| Tue Nov 24, 22:30-23:30 (8 days from now) | |
| Lecture held in ASB 10908. |
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.
Mathematics
Audience: researchers in the topic
PIMS-CORDS SFU Operations Research Seminar
| Organizer: | Tamon Stephen* |
| *contact for this listing |
