Geodesic
Improved bounds for the number of forests and acyclic orientations in the square lattice
The electronic journal of combinatorics, Tome 10 (2003)

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl EuDML
In a recent paper Merino and Welsh (1999) studied several counting problems on the square lattice $L_n$. There 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 \le \lim_{n\to\infty} f(n)^{1/n^2} \le 3.84161$$ and $$22/7 \le \lim_{n\to\infty} \alpha(n)^{1/n^2} \le 3.70925.$$ In this paper we improve these bounds as follows: $$3.64497 \le \lim_{n\to\infty} f(n)^{1/n^2} \le 3.74101$$ and $$3.41358 \le \lim_{n\to\infty} \alpha(n)^{1/n^2} \le 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.
DOI : 10.37236/1697
Classification : 05C50, 05C35, 05A16
Mots-clés : asymptotics, forests, Tutte polynomial 
N. Calkin; C. Merino; S. Noble; M. Noy. Improved bounds for the number of forests and acyclic orientations in the square lattice. The electronic journal of combinatorics, Tome 10 (2003). doi: 10.37236/1697
@article{10_37236_1697,
     author = {N. Calkin and C. Merino and S. Noble and M. Noy},
     title = {Improved bounds for the number of forests and acyclic orientations in the square lattice},
     journal = {The electronic journal of combinatorics},
     year = {2003},
     volume = {10},
     doi = {10.37236/1697},
     zbl = {1020.05041},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1697/}
}
TY  - JOUR
AU  - N. Calkin
AU  - C. Merino
AU  - S. Noble
AU  - M. Noy
TI  - Improved bounds for the number of forests and acyclic orientations in the square lattice
JO  - The electronic journal of combinatorics
PY  - 2003
VL  - 10
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1697/
DO  - 10.37236/1697
ID  - 10_37236_1697
ER  - 
%0 Journal Article
%A N. Calkin
%A C. Merino
%A S. Noble
%A M. Noy
%T Improved bounds for the number of forests and acyclic orientations in the square lattice
%J The electronic journal of combinatorics
%D 2003
%V 10
%U http://geodesic.mathdoc.fr/articles/10.37236/1697/
%R 10.37236/1697
%F 10_37236_1697

Cité par Sources :