Over a decade ago Alexander Postnikov developed his own way of looking at perfect matchings of bipartite plane graphs. As I recall, he starts with a 2-coloring of the square grid and creates a new graph whose vertices are the monochromatic patches in the grid and whose edges correspond to adjacencies of patches.

Can anyone give me a reference to existing literature on this approach?

Here are two specific things I want to understand:

1) I recall that this way of looking at perfect matchings admits its own version of Kuo condensation (based on changing the colors of individual vertices in the grid). Can anyone give me a reference for this?

2) Is there a technology of enumeration of perfect matchings of particular graphs associated with Postnikov's point of view? E.g., can one count domino tilings of Aztec diamonds, or lozenge tilings of hexagons, using the monochromatic patches perspective?

Dylan Thurston may have developed this point of view independently; my recollections are a bit hazy.


Lauren Williams pointed me toward http://front.math.ucdavis.edu/0609.5764 (the original reference for Postnikov's work) as well as http://front.math.ucdavis.edu/0706.2501 (an article by Postnikov, Speyer, and Williams with more of an emphasis on matchings and flows). In this setting one has Plucker relations that are essentially the same thing as Kuo's graphical condensation.


Greg Muller and I tried to overview this material in the first three sections of our paper .


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.