Please use this identifier to cite or link to this item:
http://bura.brunel.ac.uk/handle/2438/589
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Calkin, N | - |
dc.contributor.author | Merino, C | - |
dc.contributor.author | Noble, S D | - |
dc.contributor.author | Noy, M | - |
dc.coverage.spatial | 18 | en |
dc.date.accessioned | 2007-01-30T09:11:02Z | - |
dc.date.available | 2007-01-30T09:11:02Z | - |
dc.date.issued | 2003 | - |
dc.identifier.citation | Electronic Journal of Combinatorics 10(1): R4, Jan 2003 | en |
dc.identifier.issn | 1077-8926 | - |
dc.identifier.uri | http://bura.brunel.ac.uk/handle/2438/589 | - |
dc.description.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. | en |
dc.format.extent | 231767 bytes | - |
dc.format.mimetype | application/pdf | - |
dc.language.iso | en | - |
dc.publisher | Electronic Journal of Combinatorics | en |
dc.subject | Forests | en |
dc.subject | Acyclic orientations | en |
dc.subject | Square lattice | en |
dc.subject | Tutte polynomial | en |
dc.subject | Transfer matrices | en |
dc.title | Improved bounds for the number of forests and acyclic orientations in the square lattice | en |
dc.type | Research Paper | en |
Appears in Collections: | Computer Science Mathematical Sciences |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
forests.pdf | 226.33 kB | Adobe PDF | View/Open |
Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.