planaridad de los grafos trivalentes con un ordenamiento cíclico en las aristas de cada vértice

Question

Dejemos que $G$ sea un grafo trivalente (no dirigido). Para cada vértice $v$ de $G$ elegimos una ordenación cíclica de las aristas que entran en $v$ (por lo que si el vértice $A$ tiene vecinos $B, C$ y $D$ decidimos si los vecinos deben ser ordenados $(B, C, D)$ o $(B, D, C)$ donde $(B, C, D)$ se considera lo mismo que $(C, D, B)$ y $(D, B, C)$ para que realmente sólo haya dos opciones para cada vértice.

Ahora bien, por un dibujo que preserva el orden de dicho gráfico en el plano me refiero a un dibujo en el que para cada vector las aristas entrantes siguen el orden prescrito cuando se lee en sentido contrario a las agujas del reloj. Hoy he hecho una observación que debe ser conocida desde hace al menos 100 años:

Para la mayoría de las opciones de ordenación de las aristas en cada vértice, en un dibujo que preserve el orden de $G$ en el plano es necesario/inevitable que algunas de las aristas se crucen, incluso si el gráfico subyacente "desordenado $G$ es planar.

Por ejemplo: para la gráfica del prisma triangular sólo 2 de las $2^6 = 64$ La elección de los ordenamientos de los vértices permite una incrustación en el plano que preserva el orden sin cruces, gracias al hecho de que en cualquier incrustación del gráfico subyacente en el plano la elección del ordenamiento de las aristas en un vértice determina completamente el ordenamiento en los demás.

Así que aquí están mis preguntas:

1) ¿Existe una forma sencilla de determinar el número de ordenamientos que se pueden poner en los vértices de un grafo trivalente que permitan cruzar incrustaciones libres de orden del grafo en el plano?

2) Un resultado clásico afirma que un grafo es plano si y sólo si no tiene $K_{3, 3}$ o $K_5$ como menor de edad. ¿Existe una caracterización similar de los grafos con ordenaciones en las aristas de cada vértice que se puedan incrustar en el plano, preservando el orden, sin que se crucen las aristas?

Answer 1

He recordado dónde he visto antes grafos trivalentes con un ordenamiento cíclico en las aristas: hace mucho tiempo en el intrigante artículo corto 'Lie algebras and the 4 color theorem' de Dror Bar-Natan. (Véase: https://www.math.toronto.edu/drorbn/papers/4CT/4CT.pdf .) Lo he releído y contiene una respuesta a la pregunta 1 anterior. (La pregunta 2 sigue abierta).

Bar-Natan discute lo que él llama "una construcción bien conocida que asocia a cualquier álgebra de Lie metrizada de dimensión finita $L$ un funcional numérico-valorado $W_L$ definido en el conjunto de todos los grafos trivalentes orientados G (es decir, grafos trivalentes en los que cada vértice está dotado de un ordenamiento cíclico de las aristas que emanan de él)". Aparentemente, "esta construcción subyace a la dependencia del grupo de galgas de las teorías gauge en general y de la teoría de campo topológica de Chern-Simons en particular y juega un papel destacado en la teoría de invariantes de tipo finito (Vassiliev) de los nudos y muy probablemente también en la teoría de los invariantes de tipo finito de los 3 manifolds". Así que, en realidad, no parece haber ningún límite superior a la frialdad de esta conocida construcción.

En cualquier caso, para cualquier álgebra de Lie $L$ y el gráfico orientado $G$ tenemos que $W_L(G)$ es un número que depende de los ordenamientos de los vértices, pero sólo modestamente: la inversión del ordenamiento en un solo vértice multiplica el número $W_L(G)$ por $-1$ .

Sin embargo, la nueva idea de este artículo (o eso parece) es calcular $W_L(G)$ no sólo para un álgebra de Lie a la vez, sino para considerar $W_L(G)$ por el hecho de ser fijo $G$ con $L$ que abarca toda una familia de álgebras de Lie: la $\mathfrak{sl}(N)$ . La función resultante que toma el número $N$ como entrada y da como resultado el número $W_{\mathfrak{sl}(N)}(G)$ resulta ser un polinomio con coeficientes enteros y Bar-Natan utiliza alguna topología para demostrar que el grado de ese polinomio es como máximo $v/2 + 2$ donde $v$ es el número de vértices de $G$ .

Esto le lleva a definir el número entero $W_{sl(N)}^{top}(G)$ como el coeficiente de $N^{v/2 + 2}$ en el polinomio $W_{sl(N)}^{top}(G)$ y es este número entero el que da la respuesta a nuestra pregunta.

Por lo que veo no hay una forma más rápida de calcular $W_{sl(N)}^{top}(G)$ de $G$ que calcular $W_L(G)$ durante al menos $v/2 + 3$ diferentes álgebras de Lie $L$ y si lo hay (después de todo, estas álgebras de Lie no están completamente desvinculadas) el artículo no lo aborda. Lo que sí muestra es que el grafo no orientado subyacente de $G$ es planar si y sólo si $W_{sl(N)}^{top}(G)$ es distinto de cero.

Ahora la magia ocurre en la demostración de esta afirmación: en la página 5 aprendemos que el valor absoluto de $W_{sl(N)}^{top}(G)$ es igual al número de ordenamientos en los vértices del gráfico subyacente $G$ que permiten una incrustación que preserva el orden en la esfera orientada (y por tanto en el plano), proporcionando así una respuesta bastante inesperada a la pregunta 1 anterior.

(Observación: como puede verse en el historial de ediciones del post original, hoy mismo estaba bastante confundido sobre lo que sucedía y lo que no sucedía en el artículo de Bar-Natan. Aun así, me alegraría que alguien más conocedor del tema me confirmara (o desmintiera) que esta vez he acertado).