Geodesic
Improved bounds for the number of forests and acyclic orientations in the square lattice
The electronic journal of combinatorics, Tome 10 (2003)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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 
@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
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

Cité par Sources :