Vamos a G un grafo finito gráfica conectada. Un divisor en G es un elemento de la libre abelian grupo de Div(G) en los vértices de G (o un valor entero de la función en los vértices.) Sumando sobre todos los vértices da un homomorphism de Div(G) a la Z que llamamos grado.
Para cada vértice v, al que D(v) es el divisor
$d_v v - \sum_{w \sim v} w$
donde $d_v$ es el valor de v y $v \sim w$ significa "$v$ e $w$ son adyacentes."
Tenga en cuenta que D(v) tiene grado 0. El subgrupo de Div(G) generado por la D(v) es llamado el grupo de los principales divisores. Denotamos por Pic(G) el cociente de Div(G) por el grupo generado por el director divisores, y por Pic^0(G) el núcleo de la licenciatura mapa de Pic(G) a la Z.
La notación aquí sugiere que realmente estoy pensando acerca de las curvas algebraicas, no gráficos; y eso es en parte cierto! En el trabajo de Matt Baker y sus colaboradores, usted puede encontrar realmente una hermosa traducción de gran parte de los fundamentos de la teoría de las curvas algebraicas (Riemann-Roch, Brill-Noether, etc.) en este lenguaje.
Pero eso no es realmente lo que trata esta cuestión.
Muchas de las personas de estudio de este grupo abelian, tal vez más en particular de la estadística físicos y probabilists que el estudio de los procesos dinámicos en los gráficos. En esas comunidades, Pic^0(G) se llama la pila de arena de grupo, debido a su relación con el abelian modelo de pila de arena.
Pero eso también no es realmente lo que trata esta cuestión.
Lo que trata esta cuestión es el hecho siguiente: por la matriz de árbol teorema, el número de árboles de expansión de G es igual a |Pic^0(G)|.
Cuando uno se encuentra un conjunto finito que tiene la misma cardinalidad como un grupo finito, pero el conjunto no tiene ningún visibles natural de la estructura del grupo, un extravagante ligeramente vueltas a los pensamientos de torsors. Así:
PREGUNTA: Es el conjunto de árboles de expansión de G, naturalmente, de un torsor de la pila de arena grupo Pic^0(G)? Si es así, ¿cómo podemos describir esta "pila de arena torsor?"
(Por "naturalmente", nos referimos a "functorially" -- en particular, este torsor debe ser equivariant para la automorphism grupo de G.)
Esa pregunta es muy vaga, así que permítanme hacer que sea más precisa, y al mismo tiempo tratar de argumentar que, al menos en algunos casos, la cuestión no es ridículamente especulativo. El papel de "Chip de Disparo y el Rotor de Enrutamiento en Gráficos," por (respiración profunda) Alejandro E. Holroyd, Lionel Levine, Karola Meszaros, Yuval Peres, James Propp y David B. Wilson, contiene una muy interesante la construcción de un "local" torsor de la estructura de la pila de arena de grupo. Supongamos que G es un plano gráfico -- o, más generalmente, cualquier gráfico dotado de una cíclico de orden de las aristas incidentes a cada vértice. A continuación, el "rotor-router proceso" que se describe en Holroyd et al da S de la estructura de un Pic^0(G)-torsor! (Ver Def 3.11 - Co 3.18) Esto parece responder a mi pregunta; salvo que el torsor estructura que defina depende, a priori, sobre la elección de los vértices de G. Una forma mejor de describir su resultado es como sigue: para cada v, vamos a S_v el conjunto de orientado árboles de expansión de G con v como root. Entonces el rotor-modelo de router se da cuenta de S_v como un torsor para el grupo Pic(G) / $\mathbf{Z}$ v.
Pero S_v es, naturalmente, identificado con S (sólo olvidar la orientación) y la natural mapa Pic^0(G) -> Pic(G) / $\mathbf{Z}$ v es un isomorfismo. Así, para cada elección de v, el rotor-router construcción dota a S con la estructura de Pic^0(G)-torsor. Ahora uno puede preguntar:
PREGUNTA (más preciso): Son los torsor de estructuras proporcionados por el rotor-modelo de router, de hecho, independiente de v? Hacer que proporcione un Pic^0(G)-torsor estructura en S que es functorial de mapas compatible con el ciclo de borde órdenes, y en particular para los automorfismos de G como un plano gráfico? Si esto es falso en general, existe alguna clase de niza de los grafos G para el que es verdadero?
NOTA: Si usted está acostumbrado a pensar acerca de las curvas algebraicas, como yo, su primer instinto podría ser "bien, seguro que si el conjunto de árboles de expansión es un torsor para el Pic^0, debe ser Pic^d para algunos d". Pero no creo que este puede ser a la derecha. He aquí un ejemplo: sea G ser un 4-ciclo, que pensamos como incrustado en el plano. Ahora el estabilizador de un vértice v en el plano automorphism grupo de la gráfica es un grupo de orden 2, generado por una reflexión de la plaza a través de la diagonal que contiene v. En particular, usted puede ver inmediatamente que no spanning tree en S es fijado por este grupo; la involución actúa como un doble flip en los cuatro árboles de expansión en S. Por otro lado, Pic^d(G) siempre va a tener un punto fijo para esta acción: es decir, el divisor d*v.
OBSERVACIÓN 2: Obviamente la cosa correcta a hacer es calcular un montón de ejemplos, que podrían instantáneamente dar negativo respuestas a estas preguntas! Pero se pone un poco cansado de hacer esto por la mano; he comprobado que todo está bien para el grafo completo en 3 vértices (en cuyo caso el torsor de hecho es Pic^1(G)) y, a continuación, me acabó de vapor. Pero el sabio se ha construido en una pila de arena rutinas.....
