Exact and asymptotic enumeration of perfect matchings in self-similar graphs

摘要

We consider self-similar graphs following a specific construction scheme: in each step, several copies of the level-n graph X-n are amalgamated to form Xn+1. Examples include finite Sierpinski graphs or Vicek graphs. For the former, the problem of counting perfect matchings has recently been considered in a physical context by Chang and Chen IS.-C. Chang, L.-C. Chen, Dimer coverings on the Sierpinski gasket with possible vacancies on the outmost vertices, J. Statist. Phys. 131 (4) (2008) 631-650. arXiv:0711.0573v1], and we aim to find more general results. If the number of amalgamation vertices is small or if other conditions are satisfied, it is possible to determine explicit counting formulae for this problem, while generally it is not even easy to obtain asymptotic information. We also consider the statistics "number of matching edges pointing in a given direction" for Sierpinski graphs and show that it asymptotically follows a normal distribution. This is also shown in more generality in the case that only two vertices of X-n are used for amalgamation in each step.