Friday, January 6, 2012 — 3:30 PM EST

On minimal non-Pfaffian graphs

Speaker: U.S.R. Murty
Affiliation: University of Waterloo
Room: Mathematics & Computer Building (MC) 5158

Abstract:

Let $G$ be a graph. An even cycle in $G$ is alternating if its edges belong alternately to two different perfect matchings of $G$. An orientation $D$ of $G$ is Pfaffian if, in every alternating cycle of $G$, an odd number of edges are oriented `clock-wisely' (and, consequently, an odd number of edges are oriented `anti-clock-wisely'). 

An amazing fact is that if $D$ is a Pfaffian orientation of $G$, then the determinant of the adjacency matrix of $D$ is the square of the number of perfect matchings of $G$. 

A graph is Pfaffian if it admits a Pfaffian orientation. 

POP (The Pfaffian Orientation Problem): Given a graph $G$, determine whether or not $G$ is Pfaffian. 

Charles Little (1973) showed that, in a certain sense, $K_{3,3}$ is the only minimal non-Pfaffian bipartite graph. 

(Robertson, Seymour and Thomas (1999), and independently McCuaig (2004), showed that, for bipartite graphs, POP is in ${\cal P}$. Their work has applications to many seemingly unrelated problems in algorithmic graph theory.) 

Using a stronger notion of minimality than Little did, we show that every minimal non-Pfaffian non-bipartite graph $G$ must contain two disjoint odd cycles $C_1$ and $C_2$ such that $G-\{V(C_1)\cup V(C_2)\}$ has a perfect matching. This result has an amusing interpretation in terms of Edmonds' description of perfect matching polytopes.



Co-authors:

This talk is based on a joint paper with Marcelo Carvalho and Cláudio Lucchesi which has been accepted for publication in JCT-B.

Location 
MC - Mathematics & Computer Building
5158
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
26
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
6
  1. 2021 (95)
    1. November (2)
    2. October (6)
    3. September (12)
    4. August (6)
    5. July (10)
    6. June (12)
    7. May (7)
    8. April (9)
    9. March (13)
    10. February (8)
    11. January (10)
  2. 2020 (119)
    1. December (5)
    2. November (12)
    3. October (12)
    4. September (12)
    5. August (11)
    6. July (17)
    7. June (11)
    8. May (6)
    9. March (11)
    10. February (11)
    11. January (11)
  3. 2019 (167)
  4. 2018 (136)
  5. 2017 (103)
  6. 2016 (137)
  7. 2015 (136)
  8. 2014 (88)
  9. 2013 (48)
  10. 2012 (39)
  11. 2011 (36)
  12. 2010 (40)
  13. 2009 (40)
  14. 2008 (39)
  15. 2007 (15)