Séminaire Lotharingien de Combinatoire, 82B.51 (2019), 12 pp.

Henri Derycke and Yvan Le Borgne

Restricted Tutte polynomials for some periodic oriented forests on infinite square lattice

Abstract. For any finite graph, the Tutte polynomial is the generating function of spanning trees counted by their numbers of active external, respectively internal, edges. We consider two restrictions of this definition, either summing over a subset of spanning trees or counting only the activities in a subset of edges. Adding to the (infinite) square lattice one projective vertex in a (rational) direction θ, we define the restricted Tutte polynomial Tθ,W x H(q,t) summing over some periodic spanning forests of period W x H and considering only activities on edges of the fundamental domain. Those polynomials are symmetric in q and t by self-duality of square lattice. Our main result is a family of bijections indexed by a finite number of θ proving that (Tθ,W x H(q,1))θ does not depend on θ. Auto-duality preserving the number of trees per period and their common slope, we obtain refinements (Tθ,W x H}(w,z;q,t))θ still symmetric in q and t.


Received: November 15, 2018. Accepted: February 17, 2019. Final version: April 1, 2019.

The following versions are available: