Evaluations of Tutte polynomials of regular graphs

Ferenc Bencs; Péter Csikvári

paper

Evaluations of Tutte polynomials of regular graphs

arXiv:2105.06798

Abstract

Let $T_{G} (x, y)$ be the Tutte polynomial of a graph $G$ . In this paper we show that if $(G_{n})_{n}$ is a sequence of $d$ -regular graphs with girth $g (G_{n}) \to \infty$ , then for $x \geq 1$ and $0 \leq y \leq 1$ we have $n \to \infty lim T_{G_{n}} (x, y)^{1/ v (G_{n})} = t_{d} (x, y),$ where $$t_d(x,y)=\left\{\begin{array}{lc} (d-1)\left(\frac{(d-1)^2}{(d-1)^2-x}\right)^{d/2-1}&\ \ \mbox{if}\ x\leq d-1,\\ x\left(1+\frac{1}{x-1}\right)^{d/2-1} &\ \ \mbox{if}\ x> d-1. \end{array}\right.$$ independently of $y$ if $0 \leq y \leq 1$ . If $(G_{n})_{n}$ is a sequence of random $d$ -regular graphs, then the same statement holds true asymptotically almost surely. This theorem generalizes results of McKay ( $x = 1, y = 1$ , spanning trees of random $d$ -regular graphs) and Lyons ( $x = 1, y = 1$ , spanning trees of large-girth $d$ -regular graphs). Interesting special cases are $T_{G} (2, 1)$ counting the number of spanning forests, $T_{G} (2, 0)$ counting the number of acyclic orientations.