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

Export talk to