Counting matchings in graphs with applications to the monomer-dimer models

Abstract: Let G=(V,E) be an undirected graph with vertices V and edges E. A dimer is a domino occupying an edge e=(u,v)\in E and a monomer is a single vertex w\in V. An l-match, or a monomer-dimer cover of G, is a subset E' of E, of cardinality l, such that no two distinct edges e,f in E have a common vertex. Let \phi (l,G)\geq 0 be the number of l-matchings in G for any l\in Z_+. In many combinatorial problems it is of interest to estimate from above and below the number \phi (l,G). In the monomer-dimer models in statistical mechanics, as the integer lattice Z^d, or the Bethe lattice, i.e. an infinite k-regular tree, one needs to estimate the number of l-matching in bipartite regular graphs. Moreover, one needs to estimate the corresponding quantities h_G(p), called the monomer-dimer entropy, for dimer density p\in [0,1], for infinite graphs G.

In this lecture we will survey the recent developments in this area and pose several conjectures.

The slides of the lecture are available here.

Refreshments will be served at 2:45 p.m. (Math Lounge, MATX 1115).