Rejilla de Bethe

Una vez que un vértice se marca como la raíz, podemos agrupar los demás vértices en capas según su distancia a la raíz. El número de vértices a una distancia${\displaystyle d>0}$desde la raíz es${\displaystyle z(z-1)^{d-1}}$, ya que cada vértice que no sea la raíz es adyacente a${\displaystyle z-1}$vértices a una distancia uno mayor de la raíz, y la raíz es adyacente a${\displaystyle z}$vértices a una distancia 1.

El modelo de Ising es un modelo matemático del ferromagnetismo , en el que las propiedades magnéticas de un material están representadas por un "espín" en cada nodo de la red, que es +1 o -1. El modelo también está equipado con una constante${\displaystyle K}$representando la fuerza de la interacción entre nodos adyacentes y una constante${\displaystyle h}$representando un campo magnético externo.

El modelo de Ising en la red de Bethe se define mediante la función de partición.

${\displaystyle Z=\sum _{\{\sigma \}}\exp \left(K\sum _{(i,j)}\sigma _{i}\sigma _{j}+h\sum _{i}\sigma _{i}\right).}$

La probabilidad de que un paseo aleatorio en una red de Bethe de grado${\displaystyle z}$El punto de partida en un vértice dado, que eventualmente regresa a ese vértice, está dado por${\displaystyle {\frac {1}{z-1}}}$Para demostrar esto, dejemos${\displaystyle P(k)}$sea ​​la probabilidad de regresar a nuestro punto de partida si estamos a una distancia${\displaystyle k}$lejos. Tenemos la relación de recurrencia

${\displaystyle P(k)={\frac {1}{z}}P(k-1)+{\frac {z-1}{z}}P(k+1)}$

a pesar de${\displaystyle k\geq 1}$, ya que en cada ubicación distinta del vértice inicial hay${\displaystyle z-1}$aristas que se alejan del vértice inicial y 1 arista que se acerca a él. Sumando esta ecuación sobre todos${\displaystyle k\geq 1}$, obtenemos

${\displaystyle \sum _{k=1}^{\infty }P(k)={\frac {1}{z}}P(0)+{\frac {1}{z}}P(1)+\sum _{k=2}^{\infty }P(k)}$.

Tenemos${\displaystyle P(0)=1}$, ya que esto indica que acabamos de regresar al vértice inicial, por lo tanto${\displaystyle P(1)=1/(z-1)}$, que es el valor que queremos.

Nótese que esto contrasta marcadamente con el caso de las caminatas aleatorias en la red cuadrada bidimensional, que tiene una probabilidad de retorno de 1. ^{[ 2 ]} Dicha red es 4-regular, pero la red de Bethe 4-regular tiene una probabilidad de retorno de 1/3.

Se puede acotar fácilmente el número de caminos cerrados de longitud${\displaystyle 2k}$comenzando en un vértice dado de la red de Bethe con grado${\displaystyle z}$desde abajo. Al considerar cada paso como un paso hacia afuera (alejándose del vértice inicial) o un paso hacia adentro (hacia el vértice inicial), vemos que cualquier camino cerrado de longitud${\displaystyle 2k}$debe tener exactamente${\displaystyle k}$pasos hacia afuera y${\displaystyle k}$pasos hacia adentro. Es posible que en ningún momento hayamos dado más pasos hacia adentro que hacia afuera, por lo que el número de secuencias de direcciones de pasos (ya sean hacia adentro o hacia afuera) viene dado por el${\displaystyle k}$número catalán${\displaystyle C_{k}}$Hay al menos${\displaystyle z-1}$opciones para cada paso hacia afuera, y siempre exactamente 1 opción para cada paso hacia adentro, por lo que el número de recorridos cerrados es al menos${\displaystyle (z-1)^{k}C_{k}}$.

Este límite no es ajustado, ya que en realidad hay${\displaystyle z}$opciones para un paso hacia afuera desde el vértice inicial, que ocurre al principio y cualquier número de veces durante el recorrido. El número exacto de recorridos es más difícil de calcular y viene dado por la fórmula

${\displaystyle (z-1)^{k}C_{k}\cdot {\frac {z-1}{z}}\ _{2}F_{1}(k+1/2,1,k+2,4(z-1)/z^{2}),}$

dónde${\displaystyle _{2}F_{1}(\alpha,\beta,\gamma,z)}$es la función hipergeométrica de Gauss . ^{[ 3 ]}

Podemos usar este hecho para acotar el segundo mayor valor propio de un${\displaystyle d}$-grafo regular. Deje${\displaystyle G}$ser un${\displaystyle d}$-gráfico regular con${\displaystyle n}$vértices, y deje${\displaystyle A}$sea ​​su matriz de adyacencia . Entonces${\displaystyle {\text{tr }}A^{2k}}$es el número de recorridos cerrados de longitud${\displaystyle 2k}$. El número de paseos cerrados en${\displaystyle G}$es al menos${\displaystyle n}$veces el número de caminos cerrados en la red de Bethe con grado${\displaystyle d}$comenzando en un vértice particular, ya que podemos mapear los caminos en la red de Bethe a los caminos en${\displaystyle G}$que comienzan en un vértice determinado y solo regresan por caminos que ya fueron recorridos. A menudo hay más caminatas en${\displaystyle G}$, ya que podemos utilizar ciclos para crear recorridos adicionales. El mayor valor propio de${\displaystyle A}$es${\displaystyle d}$y dejar${\displaystyle \lambda _{2}}$Si el segundo valor absoluto más grande de un valor propio, tenemos

${\displaystyle n(d-1)^{k}C_{k}\leq {\text{tr}}A^{2k}\leq d^{2k}+(n-1)\lambda _{2}^{2k}.}$

Esto da${\displaystyle \lambda _{2}^{2k}\geq {\frac {1}{n-1}}(n(d-1)^{k}C_{k}-d^{2k})}$. Observando que${\displaystyle C_{k}=(4-o(1))^{k}}$como${\displaystyle k}$crece, podemos dejarlo${\displaystyle n}$crecen mucho más rápido que${\displaystyle k}$ver que solo hay un número finito de ellos${\displaystyle d}$-gráficos regulares${\displaystyle G}$para el cual el segundo mayor valor absoluto de un valor propio es como máximo${\displaystyle \lambda }$, para cualquier${\displaystyle \lambda <2{\sqrt {d-1}}.}$Este es un resultado bastante interesante en el estudio de los (n,d,λ)-grafos .

Un grafo de Bethe de número de coordinación par 2 n es isomorfo al grafo de Cayley no orientado de un grupo libre de rango n con respecto a un conjunto generador libre.

Las retículas de Bethe también aparecen como subgrupos discretos de ciertos grupos de Lie hiperbólicos , como los grupos fuchsianos . Por lo tanto, también son retículas en el sentido de una retícula en un grupo de Lie .

Los vértices y aristas de un orden-${\displaystyle k}$El teselado aperiógonal del plano hiperbólico forma una red de Bethe de grado${\displaystyle k}$. ^{[ 4 ]}