Theoretical Computer Science
graph-theory co.combinatorics graph-algorithms randomness matching
Updated Sat, 11 Jun 2022 03:52:33 GMT

In a random perfect matching of a regular bipartite graph, are all edges equally probable?


Consider a d-regular bipartite graph G, for d>=1. Obviously, G contains a perfect matching. Consider a perfect matching M in G chosen uniformly at random from all perfect matchings in G. Is it the case that, for arbitrary edges e and e', the probability e is in M is the same as the probability e' is in M?

Stated differently, I am asking the following: Is it the case that, for an edge e of a regular bipartite graph G, the number of perfect matchings that include e does not depend on e?

Solution

No.

Construction: Take two copies of $K_{3,3}$, one with the nodes $\{a,b,c\} \cup \{a',b',c'\}$ and the other one with the nodes $\{d,e,f\} \cup \{d',e',f'\}$. Remove the edges $(c,c')$ and $(d,d')$. Add the edges $(c,d')$ and $(d,c')$.

Comments (1)

  • +1 – Thank you for finding this. For the record, I count 6 matchings that include (a,a), and 4 matchings that include (c,d'). — Apr 30, 2012 at 03:48  

References