Department
Home Page
About Us:
• Contact Info.
• Faculty
• Staff
• Teaching Assistants
Academic Program:
• Admission
• Undergraduate
• Graduate
• Certificates
Courses:
• Course Description
• Class Web Pages
• Class Syllabi
Research:
• Colloquium
• Interdisciplinary Seminar
• Seminars
• Steve Goldman Lectures in Mathematical Physics
Links:
| • Completing Online GEP Courses |
| • Best Jobs |
| • Newsletter |
| • Math Lab |
| •Math Placement Test |
| • Careers |
| • American Mathematical Society |
| • Mathematical Association of America |
03/08/07 Colloquium
Dr. Robin Thomas
School of Mathematics
Georgia Institute of Technology
School of Mathematics
Georgia Institute of Technology
Pfaffian Orientations of Graphs
Abstract: An orientation of a graph G is Pfaffian if every even cycle C such that G\V(C) has a perfect matching has an odd number of edges directed in either direction of the cycle. The significance of Pfaffian orientations is that if a graph has one, then the number of perfect matchings (a.k.a. the dimer problem) can be computed in polynomial time.The question of what bipartite graphs have Pfaffian orientations is equivalent to many other problems of interest, such as a permanent problem of Polya, the even directed cycle problem, or the sign-nonsingular matrix problem for square matrices. These problems are now reasonably well-understood.
The speaker will briefly survey the above topics, and then will discuss recent results toward characterizing general graphs that admit Pfaffian orientations. These were obtained by or jointly with Serguei Norine.
