Coloreado de vértices heredado de los emparejamientos perfectos (motivado por la física cuántica)

Question

Añadido (19.01.2021): Dustin Mixon escribió una entrada en el blog sobre la cuestión donde reformuló y generalizó la pregunta.

Añadido (25.12.2020): Hice un video youtube para explicar detalladamente la cuestión.

Añadido (24.08.2019): Como considero que esta cuestión es importante para la física cuántica, he anunciado un premio de 3.000 euros sobre su solución, véase aquí para más detalles .

---

La siguiente pregunta puramente grafo-teórica está motivada por la mecánica cuántica (y es un caso especial de las preguntas formuladas aquí ).

Gráfico bicolor : Un grafo ponderado bicolor $G=(V(G),E(G))$ el $n$ vértices con $d$ colores es un grafo no dirigido, no necesariamente simple, en el que existe un orden fijo de los vértices $V(G)=v_1, \ldots, v_n$ y a cada arista $e \in E(G)$ existe un peso complejo $w_e$ y un par ordenado de colores (no necesariamente diferentes) $(c_1(e),c_2(e))$ asociado a él desde el $d$ posibles colores. Decimos que una arista es monocromática si el par de colores asociado no es diferente; en caso contrario, la arista es bicromática. Además, si $e$ es una arista incidente a los vértices $v_i,v_j \in V(G)$ con $i<j$ y el par ordenado de colores asociado a $e$ es $(c_1(e),c_2(e))$ entonces decimos que $e$ es de color $c_1$ en $v_i$ y $c_2$ en $v_j$ .

Nos interesará una coloración especial de este grafo:

Coloreado de vértices heredado: Sea $G$ sea un grafo ponderado bicolor y $PM$ denotan una coincidencia perfecta en $G$ . Asociamos una coloración de los vértices de G con PM de la forma natural: para cada vértice $v_i$ hay una única arista $e(v_i) \in PM$ que afecta a $v_i$ que el color de $v_i$ sea el color de $e(v_i)$ en $v_i$ . Llamamos a esta coloración $c$ la coloración de vértices heredada (IVC) del PM de coincidencia perfecta.

Peso de la coloración de vértices : Sea $G$ sea un grafo ponderado bicolor. Sea $\mathcal{M}$ sea el conjunto de emparejamientos perfectos de $G$ que tienen la coloración $c$ como su coloración de vértice heredada. Definimos el peso de $c$ como $$w(c) := \sum_{PM \in \mathcal{M}} \prod_{e \in PM}w_e. $$ Además, si $w(c)$ =1 decimos que la coloración tiene peso unitario, y si $w(c)$ =0 decimos que la coloración se anula.

Pregunta : Para qué valores de $n$ y $d$ ¿existen grafos bicolores en $n$ vértices y $d$ diferentes colores con la propiedad de que todos los $d$ ¿las coloraciones monocromáticas tienen peso unitario, y cualquier otra coloración se anula?

Llamamos a tales grafos monocromáticos con respecto al IVC.

• Los únicos ejemplos conocidos son $C_{2n}$ y $K_4$ . Además, Ilya Bogdanov ha demostrado que, si todos $w_e$ son números reales positivos, estos ejemplos son las únicas soluciones.

---

Ejemplo de coloración heredada de vértices: En la parte superior izquierda se muestra una arista ponderada bicromática con una arista doble entre los vértices 4 y 6, los pesos de las aristas $E_{ij}$ se muestran a continuación. En la parte superior derecha, se muestran sus ocho coincidencias perfectas, y $w(PM_i)$ denota el producto de los pesos de las aristas del emparejamiento perfecto $PM_i$ . Las coincidencias perfectas 4 y 5 tienen la misma coloración de vértices heredada. Como $w(c)=w(PM_4)+w(PM_5)=0$ decimos que esta coloración se anula. Quedan seis IVCs con pesos distintos de cero, tres de ellos son monocromáticos, mientras que otros tres son no monocromáticos. Por lo tanto, el grafo no es monocromático.

---

PS: Este problema puede ser reformulado completamente en términos de sistemas de ecuaciones sin las conexiones con la teoría de grafos, como Alex Ravsky ya ha sugerido.

Answer 1

Formularé la esencia del problema con la esperanza de que un especialista lo lea y resuelva. Su formulación en teoría de grafos es sólo introductoria, porque en realidad se trata de emparejamientos en un grafo de competencia con posibles pesos de arista cero. A continuación, el problema teórico de grafos se transforma en un problema algebraico sobre la existencia de soluciones de un sistema especial de ecuaciones polinómicas. Su origen grafoteórico sólo determina la estructura del sistema.

Según nuestra conjetura tenemos que demostrar que el sistema es solucionable si $d=2$ o $d=3$ y $n=4$ . Ya conocemos la solvencia para la mencionada $(n,d)$ . Además, la existencia de soluciones sólo en casos muy especiales es muy esperable porque el sistema tiene exponencialmente muchos ( $d^n$ ) pero sólo cuadráticamente muchas ( $d^2n(n-1)/2$ ).

Debido al sistema de origen de la familia $\mathcal M$ de todos los emparejamientos perfectos en un grafo completo, la estructura del sistema es relativamente simple y altamente simétrica. Así que leí "Symmetry "de Hermann Weyl y en su conclusión encontré el siguiente consejo.

Lo que aprendemos de toda nuestra discusión y lo que de hecho se ha convertido en un principio rector de las matemáticas modernas es esta lección: Siempre que tenga que ver con una entidad dotada de estructura $\Sigma$ intentar determinar su grupo de automorfismos, el grupo de las transformaciones de los elementos que no alteran las relaciones estructurales. Puede esperar obtener una visión profunda de la constitución de $\Sigma$ de esta manera. Después se puede empezar a investigar las configuraciones simétricas de los elementos, es decir, las configuraciones que son invariantes bajo un cierto subgrupo del grupo de todos los automorfismos; y puede ser aconsejable, antes de buscar tales configuraciones, estudiar los subgrupos mismos, por ejemplo, el subgrupo de los automorfismos que dejan fijo un elemento, o dejan fijos dos elementos distintos, e investigar qué subgrupos discontinuos o finitos existen, etcétera. subgrupos discontinuos o finitos, etc. En el estudio de los grupos de transformaciones se hace bien en insistir en la mera estructura de tal grupo.

Efectivamente, he encontrado algunas transformaciones de las variables del sistema que mantienen las soluciones, pero no muchas. En particular, no sé cómo construir una solución simétrica del sistema a partir de una dada.

La estructura del sistema es la siguiente. Para cada vértice $i<j$ de $\{1,\dots, n\}=[n]$ y colores $c_i,c_j\in\{1,\dots,d\}=[d]$ tenemos una variable $ij,c_ic_j$ cuyo valor es un número complejo y es el peso de una arista de $i$ a $j$ cuyo punto final $i$ está coloreado por $c_i$ y punto final $j$ está coloreado por $c_j$ . Existen $d^n$ coloración de vértices $c:[n]\to [d]$ . Cada coloración $c$ determina un peso $c(PM)$ de cada mathching perfecto $PM\in\mathcal M$ como $c(PM)=\prod ij,c(i)c(j)$ . La correspondiente a $c$ del sistema es $\sum{PM\in\mathcal M} c(PM)=\delta(c),$ donde $\delta(c)=1$ si $c$ es monocromática, y $\delta(c)=0$ de lo contrario.

En algunos casos especiales podemos decir más. Recordemos que todas las soluciones actualmente conocidas son monocromáticas, es decir, todos sus pesos de borde distintos de cero $ij,c_ic_j $ corresponden a aristas monocromáticas, es decir, para $c_i=c_j$ . Espero que por medio de la teoría de grafos pueda demostrar que si el sistema tiene una solución monocromática entonces $d\le (n-1)(n-2)/2$ que se ajusta a la conjetura para $n=4$ . Pero supongo que este resultado no tiene valor físico, así que no escribí su demostración ni me esforcé en mejorar este límite.

Otro caso especial (pero aún sin resolver) es $n=4$ . En este caso podemos dividir el sistema en el siguiente sentido. Si fijamos valores $ij,c_ic_j$ para todos $i<j\ne 4$ entonces obtenemos a lineal sistema $Ax=b$ para los valores $i4,c_ic_4$ para todos $i<4$ . Es bien sabido que este no tiene solución si $\operatorname{rank} A<\operatorname{rank} A|b$ por lo que tenemos que verificar esta condición para cada elección de valores $ij,c_ic_j$ para todos $i<j\ne 4$ .

Como ayuda visual, presentamos un sistema de $d=2$ . En aras de la simplicidad, nos limitamos al caso monocromático, cuando $c_i=c_j$ para cada $ij,c_ic_j$ que denotaremos por $ij,c$ . Tenemos ${n\choose 2}d=12$ variables

12,1 13,1 14,1 22,1 23,1 24,1 12,2 13,2 14,2 22,2 23,2 24,2

Cuando fijamos valores de $ij,c$ para $j\ne 4$ podemos describir la estructura del sistema $Ax=b$ mediante la siguiente tabla

      14,1 24,1 34,1 14,2 24,2 34,2
1111  23,1 13,1 12,1                1
1122                           12,1 
1212                      13,1      
1221  23,2                          
2112                 23,1           
2121       13,2                     
2211            12,2                
2222                 23,2 13,2 12,2 1

La primera columna enumera las coloraciones de $[n]=[4]$ en $d=2$ colores, determinando la fila respectiva de la matriz $A$ . Existen $d^4=16$ colorantes de $[4]$ en $2$ colores, pero la condición de monocromaticidad implica que todas las filas correspondientes a coloraciones que contienen conjuntos monocromáticos de tamaño impar son cero, por lo que omitimos estas filas. Todas las entradas no enumeradas de la tabla son ceros. La última columna corresponde al vector $b$ .

Así, por ejemplo, las tres primeras ecuaciones del sistema $Ax=b$ son:

$23,1\cdot 14,1+13,1\cdot 24,1+12,1\cdot 34,1=1$

$12,1\cdot 34,2 =0$

$13,1\cdot 24,2 =0$ .