Please use this identifier to cite or link to this item: http://bura.brunel.ac.uk/handle/2438/589

 Title: Improved bounds for the number of forests and acyclic orientations in the square lattice Authors: Calkin, NMerino, CNoble, S DNoy, M Keywords: ForestsAcyclic orientationsSquare latticeTutte polynomialTransfer matrices Publication Date: 2003 Publisher: Electronic Journal of Combinatorics Citation: Electronic Journal of Combinatorics 10(1): R4, Jan 2003 Abstract: In a recent paper Merino and Welsh (1999) studied several counting problems on the square lattice $L_n$. The authors gave the following bounds for the asymptotics of $f(n)$, the number of forests of $L_n$, and $\alpha(n)$, the number of acyclic orientations of $L_n$: $3.209912 \leq \lim_{n\rightarrow\infty} f(n)^{1/n^2} \leq 3.84161$ and $22/7 \leq \lim_{n\rightarrow\infty} \alpha(n) \leq 3.70925$. In this paper we improve these bounds as follows: $3.64497 \leq \lim_{n\rightarrow\infty} f(n)^{1/n^2} \leq 3.74101$ and $3.41358 \leq \lim_{n\rightarrow\infty} \alpha(n) \leq 3.55449$. We obtain this by developing a method for computing the Tutte polynomial of the square lattice and other related graphs based on transfer matrices. URI: http://bura.brunel.ac.uk/handle/2438/589 ISSN: 1077-8926 Appears in Collections: MathematicsInformation Systems and Computing

Files in This Item:

File Description SizeFormat
forests.pdf226.33 kBAdobe PDFView/Open

Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.

 Library (c) Brunel University.    Powered By: DSpace Send us your Feedback. Last Updated: September 14, 2010. Managed by: Hassan Bhuiyan