The monopole-dimer model and eccentricities for Cartesian product of graphs

Abstract

This thesis comprises two main parts. The details of the two parts are as follows: The first part of the thesis deals with the monopole-dimer model. The dimer (resp. monomer-dimer) model deals with weighted enumeration of perfect matchings (resp. matchings). The monopole-dimer model is a signed variant of the monomer-dimer model which has determinantal structure. A more general model called the loop-vertex model has also been defined for an oriented graph and the partition function in this case can also be written as a determinant. However, this model depends on the orientation of the graph. The monopole-dimer model interprets the loop-vertex model independent of the orientation for planar graphs with Pfaffian orientation. The first part of the thesis focuses on the extension of the monopole-dimer model for planar graphs (Math. Phys. Anal. Geom., 2015) to Cartesian products thereof. We show that the partition function of this model can be expressed as a determinant of a generalised signed adjacency matrix. Wethen show that the partition function is independent of the orientations of the planar graphs so long as they are Pfaffian. When these planar graphs are bipartite, we show that the computation of the partition function becomes especially simple. We then give an explicit product formula for the partition function of three-dimensional grid graphs a la Kasteleyn and Temperley–Fischer, which turns out to be fourth power of a polynomial when all grid lengths are even. Further, we generalise this product formula to higher dimensions, again obtaining an explicit product formula. We also discuss about the asymptotic formulas for the free energy and monopole densities. Lu and Wu (Physics Letters A, 1999) evaluated the partition function of the dimer model on two-dimensional grids embedded on a M¨ obius strip and a Klein bottle. We first prove a product formula for the partition function of the monopole-dimer model for the higher dimensional grid graphs with cylindrical and toroidal boundary conditions. We then consider the monopole-dimer model on high-dimensional M¨obius and Klein grids, and evaluate the partition function for three-dimensional M¨ obius and Klein grids. Further, we show that the formula does not generalise for the higher dimensions in any natural way. Finally, we present a relation between the product formulas for threedimensional grids with cylindrical and M¨ obius boundary conditions, generalising a result of Lu and Wu. Let G be an undirected simple connected graph. We say a vertex u is eccentric to a vertex v in G if d(u,v) = max{d(v,w) : w ∈ V(G)}. The eccentric graph of G, denoted Ec(G), is a graph defined on the vertices of G in which two vertices are adjacent if one is eccentric to the other. In the second part of the thesis, we find the structure and the girth of the eccentric graph of trees, and see that the girth of the eccentric graph of a tree can either be zero, three, or four. Further, we study the structure of the eccentric graph of Cartesian product of graphs and prove that the girth of the eccentric graph of the Cartesian product of trees can only be zero, three, four or six. Furthermore, we provide a complete classification of when the eccentric girth assumes these values. We also give the structure of the eccentric graph of the grid graphs and Cartesian product of two cycles. Finally, we determine the conditions under which the eccentricity matrix of Cartesian product of trees becomes invertible