A Fractional Analogue of Tutte's Perfect Matching TheoremSteve HartkeMon Mar. 29 at 1:10pm in the Graduate Student Lounge Knowing whether or not a bipartite graph has a perfect matching is easy: just use Hall's Marriage Theorem. Tutte gave a generalized condition of Hall's for general graphs which is also easy, but the proof is more difficult. I will present a similar statement characterizing when a graph has a fractional perfect matching, and show the (easy) proof. What even is a fractional perfect matching? Come to the talk and I'll tell you! |
| Back | This page last modified March 30, 2004. |