 Info
Perfect Matchings on a Nonplanar Graph
Charles McCauley, SLU
What 
 PhD Oral Exam
 Combinatorics Seminar

When 
Thu, Feb 25, 2016
from
02:30 PM
to
03:30 PM

Where 
RH 242

Add event to calendar 
vCal
iCal

Let G=(V,E) be a graph, where V=V(G) is the vertex set and E=E(G) is the edge set for the graph. A perfect matching of G is a subgraph H of G such that V(H)=V(G) and every vertex of H is incident to exactly one edge. Perfect matchings are used in physics to study, among other topics, crystal formations. While counting the number of perfect matchings on general graph G is a #Pcomplete problem, it has been known for over fifty years that the number of perfect matchings for a planar graph can be found in polynomial time using Pfaffians and determinants. In this talk, I will be talking about a nonplanar graph I have be studying, the difficulties in enumerating its perfect matchings, and how I am using a random walk on the space of perfect matchings to analyze the graph and the matchings.

