Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Improved bounds for the number of forests and acyclic orientations in the square lattice | Improved bounds for the number of forests and acyclic orientations in the square lattice N. Calkin C. Merino Department of Mathematical Sciences Martin Hall Box 341907 Clemson SC 29634-1907 USA. calkin@ S. Noble Department of Mathematical Sciences Brunel University Kingston Lane Uxbridge UB8 3PH . Instituto de Matemáticas Universidad Nacional de Mexico. Ciudad Universitaria 04510 . Mexico. merino@ M. Noy Dep. Matemàtica Aplicada II Universitat Politecnica de Catalunya Pau Gargallo 5. 08028 Barcelona Spain. noy@ Submitted Oct 20 2001 Accepted Mar 25 2002 Published Jan 15 2003 MR Subject Classifications 05A16 05C50 Abstract In a recent paper Merino and Welsh 1999 studied several counting problems on the square lattice Ln. There the authors gave the following bounds for the asymptotics of f n the number of forests of Ln and a n the number of acyclic orientations of Ln lim _ f n 1 n2 and 22 7 lim _ a n 1 n2 . In this paper we improve these bounds as follows lim _ f n 1 n and limn x a n 1 n2 . We obtain this by developing a method for computing the Tutte polynomial of the square lattice and other related graphs based on transfer matrices. 1 Introduction Given a graph G V E a forest of G is a subset A of E that contains no cycle. A spanning forest of G is a spanning subgraph whose edge set is a forest. An acyclic orientation of G is an assignment of a direction to every edge in E such that there is no directed cycle. We denote by n G the number of acyclic orientations of G and by f G the number of spanning forests of G. Partially supported by projects SEUI-PB98-0933 and by CUR Gen. Cat. 1999SGR00356. THE ELECTRONIC JOURNAL OF COMBINATORICS 10 2003 R4 1 In a recent paper Merino and Welsh 7 studied several counting problems on the square lattice Ln the graph having as vertices the set 1 . n X 1 . n and where two vertices i j and i j are .
