UBC Mathematics Colloquium

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

Fri., March 06, 3:00, MATX 1100

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) ∈ E and a monomer is a single vertex w ∈ 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 φ(l,G) ≥ 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 φ(l,G). In the monomer-dimer models in statistical mechanics, as the integer lattice Zd, 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 hG(p), called the monomer-dimer entropy, for dimer density p ∈ [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.

Back to the colloquium page.