Geodesic
Chip removal for computing the number of perfect matchings
Zapiski Nauchnykh Seminarov POMI, Representation theory, dynamical systems, combinatorial and algoritmic methods. Part XXVI. Representation theory, dynamical systems, combinatorial methods, Tome 437 (2015), pp. 62-80 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

We consider a transformation of a graph $G$ that replaces an induced subgraph $H$ of arbitrary size by a little new subgraph $h$. We choose $h$ in such a way that the equality $M(G)=xM(G')$ holds (where $G'$ is the new graph and the factor $x$ depends on the numbers of matchings of $H$ and its subgraphs). We describe how one can construct $h$ when $G$ is a planar graph and $H$ is a bipartite graph (with some restriction on the coloring of vertices connecting it with the other part of the graph $G$). For a planar bipartite graph $H$ with a small number of such vertices, we prove that the equality holds for an arbitrary graph $G$. 
@article{ZNSL_2015_437_a3,
     author = {O. V. Bursian},
     title = {Chip removal for computing the number of perfect matchings},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {62--80},
     year = {2015},
     volume = {437},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2015_437_a3/}
}
TY  - JOUR
AU  - O. V. Bursian
TI  - Chip removal for computing the number of perfect matchings
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2015
SP  - 62
EP  - 80
VL  - 437
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2015_437_a3/
LA  - ru
ID  - ZNSL_2015_437_a3
ER  - 
%0 Journal Article
%A O. V. Bursian
%T Chip removal for computing the number of perfect matchings
%J Zapiski Nauchnykh Seminarov POMI
%D 2015
%P 62-80
%V 437
%U http://geodesic.mathdoc.fr/item/ZNSL_2015_437_a3/
%G ru
%F ZNSL_2015_437_a3
O. V. Bursian. Chip removal for computing the number of perfect matchings. Zapiski Nauchnykh Seminarov POMI, Representation theory, dynamical systems, combinatorial and algoritmic methods. Part XXVI. Representation theory, dynamical systems, combinatorial methods, Tome 437 (2015), pp. 62-80. http://geodesic.mathdoc.fr/item/ZNSL_2015_437_a3/

[1] V. Aksenov, K. Kokhas, “Udalenie chipov. Urban Renewal revisited”, Zap. nauchn. semin. POMI, 432, 2014, 5–29

[2] V. Aksenov, K. Kokhas, “Udalenie chipov pri podschete pfaffianov”, Zap. nauchn. semin. POMI (to appear)

[3] K. Kokhas, “Razbienie atstekskikh diamantov i kvadratov na domino”, Zap. nauchn. semin. POMI, 360, 2008, 180–230 | MR

[4] L. Lovas, M. Plammer, Prikladnye zadachi teorii grafov, Mir, M., 1998

[5] M. Fulmek, “Graphical condensation, overlapping pfaffians and superpositions of matchings”, Electron. J. Combin., 17:1 (2010), Research Paper 83 | MR | Zbl

[6] E. Kuo, “Application of graphical condensation for enumerating matchings”, Theoret. Comput. Sci., 319 (2004), 29–57 | DOI | MR | Zbl

[7] G. Kuperberg, “An exploration of the permanent-determinant method”, Electron. J. Combin., 5 (1998), #R46 | MR | Zbl

[8] J. Propp, “Generalized domino-shuffling”, Theoret. Comput. Sci., 303:2–3 (2003), 267–301 | DOI | MR | Zbl