Dicotomía de los espectros de gráficos dirigidos.

8

En comparación con los espectros de gráficos no dirigidos, que corresponden a matrices simétricas, los espectros de gráficos dirigidos no son muy conocidos:

Se sabe que un gráfico dirigido G=(V,E) tiene una matriz de adyacencia A(G) cuyos valores propios son binarios {0,1} si G es a-cíclico. Esto se sigue por la clasificación de los vértices en componentes fuertemente conectados: Esto fija una enumeración de los vértices v1,..,vn tal que el acuerdo Laplaciano permutada a este ordenamiento es triangular superior con 0/1 entradas.

Pero lo que se sabe si G es el otro extremo, es decir, G es un gráfico fuertemente conectado en n vértices, lo que significa que hay un camino dirigido entre cualquier par de vértices.

Generalmente, uno necesitaría calcular el polinomio característico de A(G) y calcular sus raíces. A pesar de que A(G) es una matriz {0,1} , esto parece una tarea desalentadora. En particular, las raíces de este polinomio son en general números complejos.

El teorema de Perron-Frobenius implica que al menos el valor propio superior es real y simple, pero no revela información sobre el resto de los valores propios.

Sin embargo, ¿qué pasa si solo nos interesan los límites muy débiles de la siguiente forma:

Conjecture: Dichotomy of eigenvalues : SeaG un gráfico dirigido sobren vértices. Entonces, o bien todos los valores propios deAG son reales, o existe al menos un valor propioλ tal queim(λ)1/poly(n) .

¿Estos límites siguen trivialmente de los teoremas conocidos? Alternativamente, ¿puede un gráfico dirigido tener un valor propio con un componente imaginario exponencialmente pequeño?

Lior Eldar
fuente
1
Un gráfico que es esencialmente no dirigido, es decir, cada borde aparece en ambas direcciones, tendrá un Laplaciano simétrico y todos los valores propios serán reales. ¿Por qué no es eso un contraejemplo a su conjetura? También lo que usted llama "fuertemente regular" para mí parece "fuertemente conectado". ¿Hay una diferencia?
Sasho Nikolov el
Lo sentimos, reparó el error tipográfico en la conjetura. El gráfico fuertemente regular no está desviado: hay una RUTA dirigida entre cada dos vértices, no un BORDE dirigido.
Lior Eldar
No entiendo tu explicación. ¿No es un borde un camino de longitud 1? ¿Por qué un gráfico que contiene todos los bordes en ambas direcciones no es muy regular? ¿Requiere que el gráfico no tenga ciclos de longitud 2?
Sasho Nikolov
Ah, ya veo, he corregido la conjetura para reflejar su ejemplo. Quiero considerar solo gráficos dirigidos fuertemente conectados que no son esencialmente "no dirigidos". Gracias.
Lior Eldar
1
¿Puede una gráfica dirigida tener un valor propio con un componente imaginario exponencialmente pequeño? Estoy bastante seguro de que puede. Sin embargo, esto no excluye la existencia de otro valor propio con un componente imaginario polinomialmente pequeño, por lo que no veo cómo se relaciona con la conjetura. ¿Está seguro de que no mezcló los cuantificadores existenciales y universales?
Emil Jeřábek

Respuestas:

6

La respuesta a "alternativamente, puede una gráfica dirigida tener un valor propio con un componente imaginario exponencialmente pequeño" es SÍ (aunque no entiendo qué es "alternativa" acerca de esta declaración, ya que de ninguna manera refuta la conjetura).

fZ[x]GO(deg(f)+f1)f tan fácilmente como esperaba, así que decidí escribirlo como una respuesta adecuada para el registro.

Schönhage [1] enumera varios ejemplos de polinomios con separación de raíces exponencialmente pequeña, en particular la familia de polinomios atribuidos a Mignotte [ 2] (que no puedo verificar ya que no tengo acceso a él en este momento). Ahora, estos polinomios tienen cada uno un par de raíces reales cerca de en una distancia , mientras que necesitamos un par de raíces complejas . Sin embargo, esto se logra fácilmente modificando ligeramente el polinomio: sea Claramente, este polinomio no tiene raíz real positiva (y tampoco tiene raíz real negativa si

xn2(cx1)2(n3,c2)
1/c<2/c1+n/2
f(x)=xn+(2x1)2=xn+4x24x+1.
nincluso). Además, es fácil demostrar que todavía tiene un par de raíces (necesariamente no reales) en una distancia exponencialmente pequeña a ; Si no estropeé el cálculo, estas raíces son aproximadamente Ahora, se puede escribir como el determinante de, por ejemplo, la matriz y por lo tanto como el polinomio característico de la matriz de adyacencia del gráfico dirigido ponderado en vértices1/2
z±=12±i21n2+O(n2n).
f(x)n×n
(x1x1x1x1144x)
G0n{0,,n1}ii+11i=0,,n2 ; de peso ; de peso ; y de peso . Los valores propios de son, por lo tanto, exactamente las raíces de , incluyendo .n101n114n124G0fz±

Finalmente, los valores propios de se incluyen entre los valores propios del gráfico dirigido no ponderado en vértices con bordes e para ; y para ; , ; y , , , paraG0G12n+6

0+,0,,(n2)+,(n2),(n1)+0,,(n1)+3,(n1)0,,(n1)3
i+(i+1)+i(i+1)i=0,,n3(n2)+(n1)+j(n2)(n1)jj=0,,3(n1)+00(n1)00+(n1)+j1+(n1)+j2(n1)j1j=0,...,3(n1)j2+j=0,,3 .

Referencias

[1] A. Schönhage, Ejemplos de separación de raíces polinomiales , Journal of Symbolic Computation 41 (2006), no. 10, págs. 1080-1090, doi: 10.1016 / j.jsc.2006.06.003 .

[2] M. Mignotte, Algunos límites útiles , en: Buchberger, Collins, Loos (eds.), Computer Algebra: Symbolic and Algebraic Computation, 2nd ed., Springer-Verlag, 1983, pp. 259–263, doi: 10.1007 / 978-3-7091-7551-4_16 .

Emil Jeřábek
fuente
Además, está fuertemente conectado si es importante. G1
Emil Jeřábek
Gracias. Esto es muy informativo. Aunque esto no es estrictamente un gráfico dirigido, sino más bien un gráfico ponderado con pesos arbitrarios. Entonces responde una generalización de lo anterior, ¿correcto? Seguramente es fácil producir gráficos con valores propios arbitrariamente pequeños si permite pesos arbitrarios (por ejemplo, un solo vértice con un bucle de 2 ^ {- n} peso), pero la conjetura intenta capturar si puede obtener valores propios exponencialmente pequeños incluso con {0,1} elementos. Aún así, creo que mostrar esto con pesos O (1) califica como progreso.
Lior Eldar
Te perdiste el punto. no es un gráfico ponderado. Es un gráfico dirigido perfectamente normal. G1
Emil Jeřábek
¿Cuál es la forma más fácil de asegurarse de que el espectro de esté contenido en el de ? G 0G1G0
Lior Eldar
No creo que sea razonablemente posible. El polinomio característico siempre tiene raíces con multiplicidad, por lo que, en circunstancias normales, agrandar el gráfico crea nuevos valores propios. No puedo imaginar una transformación que conserve el valor propio de los gráficos ponderados a los no ponderados que dejaría el mismo número de vértices o haría que el char poly del nuevo gráfico sea una potencia del char poly original. n
Emil Jeřábek
1

Siento que los límites dependerán en gran medida de la estructura de conectividad particular del gráfico.

Un ejemplo sería un ciclo de una sola vía de longitud . Con el orden correcto, no es difícil ver que , por lo que los valores propios son todos los raíces-ésima de la unidad, es decir, con yendo de a .A ( G ) N - I = 0 N e 2 π i n / N n 0 N - 1NA(G)NI=0Ne2πin/Nn0N1

Incluso para , tiene garantizados algunos valores propios puramente imaginarios y .i - iNii

Ahora, por otro lado, fui a Wolframalpha y conecté el gráfico completo de tamaño 4, luego eliminé un solo borde. El gráfico resultante tiene valores propios puramente reales (a pesar de no tener una matriz de adyacencia simétrica; sí, eso puede suceder). Lo que me dice que no hay una declaración general.

Lagerbaer
fuente
Gracias. Este es un ejemplo importante. En realidad, parece que incluso un gráfico no simétrico mucho más escaso en 4 vértices tiene un espectro real: considere los vértices v1, v2, v3, v4: tienen bordes bidireccionales entre vi y v_ {i + 1} para y un solo borde dirigido de a . Tal vez sea el caso de que si tiene una subgrafía cuyo gráfico dirigido inducido es esencialmente no dirigido, en el contexto de valores propios puede "contraer" esa subgrafía. De todos modos, he modificado la conjetura para contener este ejemplo. v 4 v 1i{1,2,3}v4v1
Lior Eldar