Fórmula exacta para el número de árboles de expansión de un rectángulo

10

Este blog habla de generar "pequeños laberintos retorcidos" usando una computadora y enumerándolos. La enumeración se puede hacer usando el algoritmo de Wilson para obtener el UST , pero no recuerdo la fórmula de cuántos hay.

http://strangelyconsistent.org/blog/youre-in-a-space-of-twisty-little-mazes-all-alike

En principio, el teorema del árbol de matriz establece que el número de árboles de expansión de un gráfico es igual al determinante de la matriz laplaciana del gráfico. Supongamos que $G= (E,V)$ sea el gráfico y $A$ sea la matriz de adyacencia, $D$ sea la matriz de grados, luego $\Delta = D - A$ con valores propios $\lambda$ , luego:

k (G) = \frac{1}{n} \prod_{k = 1}^{n - 1} λ_{k}

$k(G) = \frac{1}{n} \prod_{k=1}^{n-1} \lambda_k$

En el caso de un rectángulo $m \times n$ tanto $A$ como los valores propios deberían tomar una forma particularmente simple, que no puedo encontrar.

¿Cuál es la fórmula exacta (y los asintóticos) para el número de árboles de expansión de un rectángulo $m \times n$ ?

ingrese la descripción de la imagen aquí

Aquí hay un bonito ejemplo del algoritmo de Wilson en acción.

graph-theory randomized-algorithms matrices tree john mangual
fuente

2

Enciclopedia en línea de secuencias enteras Las fórmulas exactas no parecen fáciles de derivar.

Peter Shor

@PeterShor OEIS cita: Germain Kreweras, Complexite et circuitos Euleriens dans les sommes tensorielles de graphes , J. Combin. Teoría, B 24 (1978), 202-212. Él es los mismos objetos que nosotros, ¿verdad?

john mangual

m \times n

$m \times n$

9

De acuerdo con https://www.cse.ust.hk/~golin/pubs/ANALCO_05.pdf, no se conoce una fórmula de forma cerrada.

$n$ $m$

Exp (z_{s q} metro norte)

$\exp (z_{\mathrm{sq}}mn)$

z_{s q} = \frac{4 4}{π} \sum_{yo = 0 0}^{\infty} \frac{(- 1)^{yo}}{(2 yo + 1)^{2}} \approx 1.16624

$z_{\mathrm{sq}}=\frac{4}{\pi}\sum_{i=0}^\infty\frac{(-1)^i}{(2i+1)^2}\approx 1.16624$

m

$m$

n

$n$

David Eppstein
fuente

Hay fórmulas asintóticas precisas para el número de árboles que se extienden en un rectángulo (y secuencias más generales de subgrafías descritas por polígonos rectilíneos) dados aquí: arxiv.org/pdf/math-ph/0011042.pdf (específicamente, corolario 2 y proposición 13 )

Lorenzo Najt

De nuevo, eso está en un repositorio de física matemática. ¿Prueban rigurosamente las fórmulas asintóticas o simplemente usan un razonamiento ansatz similar a la física?

David Eppstein

Fue publicado en Acta Math 185 (2000) no. 2, 239-286.

Lorenzo Najt

0

Los valores propios del gráfico de rectángulo m-por-n se pueden usar para obtener una expresión para el número de coincidencias perfectas en dichos gráficos. Vea el artículo de Wikipedia sobre las inclinaciones de dominó .

Tyson Williams
fuente

Esto es interesante, pero ¿puedes explicar cómo responde esto a la pregunta? ¿Hay algún tipo de mapeo entre emparejamientos perfectos y árboles de expansión en este caso particular?

Saeed

Fórmula exacta para el número de árboles de expansión de un rectángulo

Respuestas: