Tutte Polynomials in Square Grids

Given any graph G (loops and multiple deges allowed) one can associate to it a two-variable polynomial T(G;x,y), the Tutte polynomial, that contains much information on G. In particular, T(G;1,1) gives the number of spanning trees of G, T(G;2,1) the number of forests (acyclic spanning subgrpahs) of G, and T(G;2,0) the number of acyclic orientations of G. We explore these values when G is an n x n square grid and deduce upper and lower bounds for the quantities of interest.

(Joint work with Criel Merino and Dominic Welsh).