tailieunhanh - Báo cáo toán học: "Improved bounds for the number of forests and acyclic orientations in the square lattice"

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 .