Personal tools

Perfect Matchings on a Nonplanar Graph

Charles McCauley, SLU

  • 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
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 #P-complete 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.
« June 2018 »