Probabilidad de que un vértice en el árbol de expansión de un $N$ x $N$ cuadrícula gráfica es una hoja de

Question

Supongamos que tenemos una $N$ x $N$ cuadrícula gráfico de $G(V,E)$ y se construye un árbol de expansión de este gráfico de la siguiente manera.

Comience con un conjunto $S$, que sólo contiene el vértice en la esquina superior izquierda de la cuadrícula de la gráfica (i.e $(0,0)$), y un conjunto vacío $T$ que contendrá nuestro árbol de expansión.
Ahora elige un borde al azar (con igual probabilidad) de que el conjunto de aristas $(p,q)\in E(G)$ tal que $p \in S$$q \not \in S$.
Agregar esta ventaja a nuestro set $T$ y añadir $q$ establecer $S$, repita este proceso hasta la obtención de un árbol de expansión.

Ahora, el problema es este:
¿Cuál es la probabilidad de que un determinado vértice de la cuadrícula gráfico en la ubicación de $(x,y)$ es una hoja en nuestro árbol de expansión? En general, ¿cuál es el número esperado de las hojas en un árbol de expansión construido de esta manera? Si este problema es demasiado difícil, ¿qué podemos decir acerca de un menor tamaño de la cuadrícula? Por ejemplo, si consideramos un $N$ x $2$, $N$ x $3$, e....t.c cuadrícula gráfico

Nota:
Esto fue inspirado por una cuestión de carácter más general se le preguntó por Nick Wu en Quora

Answer 1

He utilizado un ordenador para calcular las probabilidades en redes pequeñas.

Para $2x2$ :

$$\begin{array}{|c|c|}\hline\frac{1}{4}&\frac{1}{2}\\\hline\frac{1}{2}&\frac{3}{4}\\\hline\end{array}=\begin{array}{|c|c|}\hline \frac{ 1}{4 } & \frac{ 2}{4 } \\\hline \frac{ 2}{4 } & \frac{ 3}{4 } \\\hline \end{array}$$

Para $3x2$ :

$$\begin{array}{|c|c|}\hline \frac{7}{27}&\frac{19}{144}&\frac{5}{8}\\\hline \frac{14}{27}&\frac{7}{24}&\frac{161}{216}\\\hline\end{array}= \begin{array}{|c|c|}\hline \frac{112}{432} & \frac{57}{432} & \frac{270}{432} \\\hline \frac{224}{432} & \frac{126}{432} & \frac{322}{432} \\\hline \end{array}$$

Para $4x2$ : $$\begin{array}{|c|c|}\hline \frac{299}{1152}&\frac{4261}{31104}&\frac{1949}{10368}&\frac{41491}{62208}\\\hline \frac{7177}{13824}&\frac{6283}{20736}&\frac{1829}{6912}&\frac{29843}{41472}\\\hline\end{array}= \begin{array}{|c|c|}\hline \frac{32292}{124416} & \frac{17044}{124416} & \frac{23388}{124416} & \frac{82982}{124416} \\\hline \frac{64593}{124416} & \frac{37698}{124416} & \frac{32922}{124416} & \frac{89529}{124416} \\\hline \end{array}$$

Para $3x3$ :

$$\begin{array}{|c|c|}\hline \frac{1459}{5400} & \frac{6359}{43200} & \frac{143129}{216000} \\\hline \frac{6359}{43200} & \frac{153293}{972000} & \frac{483341}{1296000} \\\hline \frac{143129}{216000} & \frac{483341}{1296000} & \frac{1217}{1500} \\\hline \end{array}$$

Para grandes redes, numeradores y denominadores no encajan en la versión de 64 bits de los números enteros, y los cálculos se vuelven lentos. Pero los resultados parecen mostrar que no existe una clara respuesta a su pregunta.

Answer 2

Le hizo algunas preguntas relacionadas con el Uniforme de Árbol de expansión en el modelo de la Mecánica Estadística y la Combinatoria. Vamos a tratar de abordar su primera pregunta:

¿Cuál es la probabilidad de un determinado vértice de la cuadrícula $(x,y) \in N \times N$ es una hoja en nuestro árbol de expansión?

En primer lugar, tenemos que contar todos los árboles de expansión de la $N \times N$ cuadrícula. Esto es en la Enciclopedia en Línea de Secuencias de Enteros A007341

1, 4, 192, 100352, 557568000, ...

Este número crezca muy rápidamente. Y tenemos una fórmula exacta:

$$a_n = \frac{2^{n^2-1} }{n^2} \prod_{m_1, m_2 =1}^{n-1} \left(2 - \cos \frac{\pi m_1}{n} - \cos \frac{\pi m_2}{n}\right) \in \mathbb{Z}$$

One way to check this is an integer is to verify this is invariant under the Galois group of $\mathbb{Q}[\omega]$ with $\omega^n = 1$ is a root of unity.

We can also tell that from the $2^{n^2}$ factor that we need $n^2$ bits in order to uniquely describe our spanning tree.

This formula is disccussed on MathOverflow: http://mathoverflow.net/questions/8497/number-of-spanning-trees-in-a-grid

Deriving the Product Formula for the Number of Spanning Trees

We can use the Matrix Tree Theorem which states that number of trees of any graph - in our case the $N \times N$ grid - is equal to the determinant of the Laplacian of the grid.

$$\# \{ \text{spanning trees}\} = \det \Delta_G = \frac{1}{n}\lambda_1\dots \lambda_{n-1}$$

In the case of the $\{ 1, 2, \puntos n \} \times \{ 1, 2, \dots n \}$ we can write down explicit eigenfunctions so that

$$\lambda \; f(x,y) = \frac{1}{4} \big[ f(x+1,y) + f(x-1,y) + f(x,y+1) + f(x,y-1)\big]$$

The functions we get are $(x,y) \mapsto \exp\left(\frac{\pi m_1 x}{n}\right)\exp\left(\frac{\pi m_2 x}{n}\right)$ with eigenvalues $\lambda = 2 - \cos \frac{\pi m_1}{n} - \cos \frac{\pi m_2}{n}$.

So, the number of spanning trees on the grid has something to do with Harmonic analysis on $\mathbb{Z}_N^2$, el paseo aleatorio y las raíces de la unidad.

Answer 3

No sabes si es de ayuda y es un poco tarde, pero para el caso de la $N\times N$ cuadrícula en el límite de $N\rightarrow \infty$ el siguiente resultado exacto de la hoja de la probabilidad que se haya obtenido aquí se basa en una equivalencia a la Abelian sandpile modelo:

$$\frac{8}{\pi^2}\left( 1 - \frac{2}{\pi}\right) \approx 0.29454$$