Número de árboles de expansión en una cuadrícula

Question

Dado un$\sqrt{n}\times\sqrt{n}$ pieza de la cuadrícula$\mathbb{Z}^2$, defina un gráfico uniendo cualquiera de estos dos puntos a una unidad de distancia. ¿Cuántos árboles abarca este gráfico (asintóticamente como$n\to\infty$)?

¿Puedes decir algo sobre la cuadrícula triangular generada por$(1,0)$ y$(1/2,\sqrt{3}/2)$?

Answer 1

Creo que la mejor manera de lidiar con las redes es encontrar el general eigenfunction del infinito de la cuadrícula y, a continuación, aplicar condiciones de contorno adecuadas. Esta es una idea de Kenyon, Propp y Wilson, usted puede encontrar un esquema en la última sección de mi Diplomarbeit enlace de texto

Solo lo hacen para el cuadrado de la cuadrícula, que yo recuerde, pero no me sorprendería si el mismo Ansatz trabaja con la malla triangular.

Creo que Richard Kenyon también se muestra cómo calcular el asymptotics en "a Largo plazo de las propiedades de los árboles de expansión en Z^2" (se puede encontrar en su página de inicio) pero yo no comprobar.

Un segundo truco que podría ser útil para la malla triangular (debido a Knuth), es observar que el doble de la cuadrícula es "casi" normal. Usted puede optar por eliminar el vértice correspondiente a la cara exterior en el Laplaciano al aplicar la matriz de árbol teorema, y obtener un muy buen matriz, supongo.

actualización:

Acabo de encontrar una referencia que demuestra la asymptotics para la malla triangular: En la entropía de la distribución de los árboles en una gran celosía triangular. Las fórmulas son una preciosidad...

Yo debería haber comentó que la referencia contiene (exacta) las expresiones para la asymptotics de ambas redes: el límite de $1/n \ln \tau(G_n)$ donde $\tau(G_n)$ es el número de árboles de expansión de la gráfica con $n$ vértices, es

$$4/\pi\sum_{n\geq1} \sin(n\pi/2)/n^2 = 1.166 243 616\dots$$

para el cuadrado de la cuadrícula (debido a Temperly 1972), y

$$5/\pi\sum_{n\geq1} \sin(n\pi/3)/n^2 = 1.615 329 736 097\dots$$

para la malla triangular (demostrado en la referencia).

Answer 2

Ampliación de Steve Cazador de la respuesta, llame al producto, que aparece en A007341 f(n). Es decir,

$$f(n) = \prod_{k=0}^{n-1} {\prod_{l=0}^{n-1}}^\prime \left(2 - \cos {\pi k \over n} - \cos {\pi l \over n } \right)$$

donde el $\prime$ en el segundo producto indica que empezamos a $l=1$ en el caso de $k = 0$. El número de interés aquí es $a(n) = 2^{n^2-1} f(n)/n^2$ .

El producto es la exponencial de una suma, por lo que

$$\log f(n) = \sum_{k=0}^{n-1} {\sum_{l=0}^{n-1}}^\prime \log \left(2 - \cos {\pi k \over n} - \cos {\pi l \over n } \right).$$

Esta suma es, a su vez, $n^2$ veces una suma de Riemann para la integral

$$ C = \int_0^1 \int_0^1 \log(2-\cos x\pi - \cos y\pi) \: dx \: dy $$

que creo que converge, aunque en realidad de evaluar numéricamente es difícil. Si usted cree que, a continuación,$\log f(n) \sim Cn^2$$n \to \infty$, e $\log a(n) \sim (C+\log 2) n^2$$n \to \infty$. De la evaluación de la $f(n)$ varios $n$, parece que $C$ es cerca de $0.473$, $e^C$ está cerca de $1.605$, por lo que tenemos

$$ a(n) \approx 3.21^{n^2} $$

donde escribo $p(n) \approx q(n)$$\log p(n)/\log q(n) \to 1 $$n \to \infty$, yo. e. $\log p(n) \sim \log q(n)$.

Answer 3

Puede intentar mirar:

http://arxiv.org/pdf/0809.2551

Answer 4

Usted puede escribir un programa a) forma de la gráfica de Laplace (para n suficientemente pequeño) y el uso de la matriz de árbol teorema para obtener el número de árboles de expansión. Ver

http://en.wikipedia.org/wiki/Kirchhoff%27s_theorem

La malla triangular es un poco más complicado de manejar, tanto en papel o en una computadora, usted puede encontrar técnicas para el graduado de lexicográfica del índice se describe en

http://blog.eqnets.com/2009/10/06/a-graded-lexicographic-index-part-1/

y posteriores posts de ayuda para tratar con el triangular de celosía.

EDIT: La respuesta está en http://www.oeis.org/A007341.