Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Graphical condensation, overlapping Pfaffians and superpositions of matchings. | Graphical condensation overlapping Pfaffians and superpositions of matchings Markus Fulmek Submitted Dec 10 2009 Accepted May 25 2010 Published Jun 7 2010 Mathematics Subject Classification 05C70 05A19 05E99 Abstract The purpose of this paper is to exhibit clearly how the graphical condensation identities of Kuo Yan Yeh and Zhang follow from classical Pfaffian identities by the Kasteleyn-Percus method for the enumeration of matchings. Knuth termed the relevant identities overlapping Pfaffian identities and the key concept of proof superpositions of matchings . In our uniform presentation of the material we also give an apparently unpublished general overlapping Pfaffian identity of Krattenthaler. 1 Introduction In the last 7 years several authors 11 12 16 22 23 came up with identities related to the enumeration of matchings in planar graphs together with a beautiful method of proof which they termed graphical condensation. In this paper we show that these identities are special cases of certain Pfaffian identities in the simplest case Tanner s identity 19 by simply applying the Kasteleyn-Percus method 7 15 . These identities involve products of Pfaffians for which Knuth 9 coined the term overlapping Pfaffians. Overlapping Pfaffians were further investigated by Hamel 6 . Knuth gave a very clear and concise exposition not only of the results but also of the main idea of proof which he termed superposition of matchings. Tanner s identity dates back to the 19th century and so does the basic idea of superposition of matchings which was used for a proof of Cayley s Theorem 1 by Veltmann Research supported by the National Research Network Analytic Combinatorics and Probabilistic Number Theory funded by the Austrian Science Foundation. THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R83 1 in 1871 20 and independently by Mertens in 1877 13 as was already pointed out by Knuth 9 . Basically the same proof of Cayley s Theorem was presented by Stembridge 18 who gave a very .
