Dicotomia dos espectros de gráficos direcionados

Comparado aos espectros de gráficos não direcionados, que correspondem a matrizes simétricas, o espectro de gráficos direcionados não é muito conhecido:

Sabe-se que um gráfico direcionado possui uma matriz de adjacência cujos valores próprios são binários se for a-cíclico. Isto segue classificando os vértices em componentes fortemente conectados: isso corrige uma enumeração dos vértices modo que o Laplaciano permutado de acordo com essa ordem seja triangular superior com entradas . $G = (V,E)$ $A(G)$ $\{0,1\}$ $G$ $v_1,.., v_n$ $0/1$

Mas o que se sabe se é o outro extremo extremo - isto é, é um gráfico fortemente conectado em vértices - significa que existe um caminho direcionado entre qualquer par de vértices. $G$ $G$ $n$

Geralmente, seria necessário calcular o polinômio característico de e calcular suas raízes. Apesar de ser uma matriz , isso parece uma tarefa assustadora. Em particular, as raízes desse polinômio são em geral números complexos. $A(G)$ $A(G)$ $\{0,1\}$

O teorema de Perron-Frobenius implica que pelo menos o autovalor superior é real e simples, mas não revela informações sobre o restante dos autovalores.

No entanto, e se estivermos interessados apenas em limites muito fracos da seguinte forma:

$\textbf{Conjecture: Dichotomy of eigenvalues}$ : Seja um gráfico direcionado em vértices. Então, todos os autovalores de são reais ou existe pelo menos um autovalor tal que . $G$ $n$ $A_G$ $\lambda$ $im(\lambda)\geq 1/poly(n)$

Esses limites seguem trivialmente a partir de teoremas conhecidos? Como alternativa, um gráfico direcionado pode ter um valor próprio com um componente imaginário exponencialmente pequeno?

graph-theory graph-algorithms linear-algebra spectral-graph-theory Lior Eldar
fonte

Um gráfico essencialmente não direcionado, ou seja, cada aresta aparece nas duas direções, terá um Laplaciano simétrico e todos os autovalores serão reais. Por que isso não é um contra-exemplo para a sua conjectura? Também o que você chama de "fortemente regular" para mim parece "fortemente conectado". Existe alguma diferença?

Sasho Nikolov 05/10

Desculpe - corrigido o erro de digitação na conjectura. O gráfico fortemente regular não é direcionado - existe um PATH direcionado entre cada dois vértices, não um EDGE direcionado.

Lior Eldar 5/10

Eu não entendo sua explicação. Uma aresta não é um caminho de comprimento 1? Por que um gráfico que contém todas as arestas nas duas direções é fortemente regular? Você precisa que o gráfico não tenha ciclos de comprimento 2?

Sasho Nikolov

Ah - entendi - corrigi a conjectura para refletir seu exemplo. Quero considerar apenas gráficos direcionados fortemente conectados que não são essencialmente "não direcionados". Obrigado.

Lior Eldar 10/10

Um gráfico direcionado pode ter um autovalor com um componente imaginário exponencialmente pequeno? Tenho certeza que sim. No entanto, isso não exclui a existência de outro valor próprio com componente imaginário polinomialmente pequeno, portanto não vejo como ele se relaciona com a conjectura. Tem certeza de que não misturou os quantificadores existencial e universal?

Emil Jerabek

Respostas:

A resposta para “alternativamente, um gráfico direcionado pode ter um autovalor com um componente imaginário exponencialmente pequeno” é SIM (embora eu não entenda o que é “alternativo” nessa afirmação, pois de modo algum refuta a conjectura).

$f\in\mathbb Z[x]$ $G$ $O(\deg(f)+\|f\|_1)$ $f$ tão prontamente encontrado quanto eu esperava, então decidi escrever como uma resposta adequada para o registro.

Vários exemplos de polinômios com separação radicular exponencialmente pequena são listados por Schönhage [1], em particular a família de polinômios atribuída a Mignotte [ 2] (que não posso verificar porque não tenho acesso a ele no momento). Agora, esses polinômios têm um par de raízes reais próximo de na distância , enquanto que precisamos de um par de raízes complexas . No entanto, isso é facilmente conseguido modificando um pouco o polinômio: seja Claramente, esse polinômio não tem raiz real positiva (e nenhuma raiz real negativa, se

x^{n} - 2 (c x - 1)^{2} (n \geq 3, c \geq 2)

$x^n-2(cx-1)^2\qquad(n\ge3,c\ge2)$

1 / c

$1/c$

< 2 / c^{1 + n / 2}

$<2/c^{1+n/2}$

f (x) = x^{n} + (2 x - 1)^{2} = x^{n} + 4 x^{2} - 4 x + 1.

$f(x)=x^n\mathbin{\color{red}+}(2x-1)^2=x^n+4x^2-4x+1.$

n

$n$ é par). Além disso, é fácil mostrar que ele ainda tem um par de raízes (necessariamente não reais) em distância exponencialmente pequena a ; se eu não estraguei o cálculo, essas raízes são aproximadamente Agora, pode ser escrito como o determinante, por exemplo, da matriz e, portanto, como o polinômio característico da matriz de adjacência do gráfico direcionado ponderado em vértices

1 / 2

$1/2$

z_{\pm} = \frac{1}{2} \pm i 2^{- 1 - \frac{n}{2}} + O (n 2^{- n}) .

$z_\pm=\frac12\pm i2^{-1-\frac n2}+O(n2^{-n}).$

f (x)

$f(x)$

n \times n

$n\times n$

(\begin{matrix} x & - 1 \\ x & - 1 \\ x & - 1 \\ ⋱ \\ x & - 1 \\ 1 & - 4 & 4 & x \end{matrix})

$\begin{pmatrix} x&-1\\ &x&-1\\ &&x&-1\\ &&&\ddots\\ &&&&x&-1\\ 1&-4&4&&&x \end{pmatrix}$

G_{0}

$G_0$

n

$n$

{0, \dots, n - 1}

$\{0,\dots,n-1\}$

i \to i + 1

$i\to i+1$

1

$1$

i = 0, \dots, n - 2

$i=0,\dots,n-2$ ; de peso ; de peso ; e de peso . Os autovalores de são, portanto, exatamente as raízes de , incluindo .

n - 1 \to 0

$n-1\to0$

- 1

$-1$

n - 1 \to 1

$n-1\to1$

4

$4$

n - 1 \to 2

$n-1\to2$

- 4

$-4$

G_{0}

$G_0$

f

$f$

z_{\pm}

$z_\pm$

Finalmente, os autovalores de são incluídos entre os autovalores do gráfico direcionado não ponderado nos vértices com arestas e para ; e para ; , ; e , , , para $G_0$ $G_1$ $2n+6$

0_{+}, 0_{-}, \dots, (n - 2)_{+}, (n - 2)_{-}, (n - 1)_{+}^{0}, \dots, (n - 1)_{+}^{3}, (n - 1)_{-}^{0}, \dots, (n - 1)_{-}^{3}

$0_+,0_-,\dots,(n-2)_+,(n-2)_-,(n-1)_+^0,\dots,(n-1)_+^3,(n-1)_-^0,\dots,(n-1)_-^3$

i_{+} \to (i + 1)_{+}

$i_+\to(i+1)_+$

i_{-} \to (i + 1)_{-}

$i_-\to(i+1)_-$

i = 0, \dots, n - 3

$i=0,\dots,n-3$

(n - 2)_{+} \to (n - 1)_{+}^{j}

$(n-2)_+\to(n-1)_+^j$

(n - 2)_{-} \to (n - 1)_{-}^{j}

$(n-2)_-\to(n-1)_-^j$

j = 0, \dots, 3

$j=0,\dots,3$

(n - 1)_{+}^{0} \to 0_{-}

$(n-1)_+^0\to0_-$

(n - 1)_{-}^{0} \to 0_{+}

$(n-1)_-^0\to0_+$

(n - 1)_{+}^{j} \to 1_{+}

$(n-1)_+^j\to1_+$

(n - 1)_{+}^{j} \to 2_{-}

$(n-1)_+^j\to2_-$

(n - 1)_{-}^{j} \to 1_{-}

$(n-1)_-^j\to1_-$

(n - 1)_{-}^{j} \to 2_{+}

$(n-1)_-^j\to2_+$

j = 0, \dots, 3

$j=0,\dots,3$ .

Referências:

[1] A. Schönhage, exemplos de separação polinomial de raízes , Journal of Symbolic Computation 41 (2006), n. 10, pp. 1080-1090, doi: 10.1016 / j.jsc.2006.06.003 .

[2] M. Mignotte, Alguns limites úteis , em: Buchberger, Collins, Loos (eds.), Álgebra de Computadores: Computação Simbólica e Algébrica, 2ª ed., Springer-Verlag, 1983, pp. 259–263, doi: 10.1007 / 978-3-7091-7551-4_16 .

Emil Jeřábek
fonte

Além disso, está fortemente conectado, se for o caso.

G_{1}

$G_1$

Emil Jerabek

Obrigado. Isso é muito informativo. Embora este não seja estritamente um gráfico direcionado, mas um gráfico ponderado com pesos arbitrários. Portanto, responde a uma generalização do exposto, correto? Certamente, é fácil produzir gráficos com autovalores arbitrariamente pequenos se você permitir pesos arbitrários (digamos, um único vértice com um auto-loop de peso 2 ^ {- n}), mas a conjectura tenta capturar se é possível obter autovalores exponencialmente pequenos mesmo com elementos {0,1}. Ainda assim, acho que mostrar isso com O (1) pesos se qualifica como progresso.

Lior Eldar 27/10

Você perdeu o ponto. não é um gráfico ponderado. É um gráfico direcionado perfeitamente normal.

G_{1}

$G_1$

Emil Jerabek

Qual é a maneira mais fácil de garantir que o espectro de esteja contido no de ?

G_{1}

$G_1$

G_{0}

$G_0$

Lior Eldar

Eu não acho que isso seja razoavelmente possível. O polinômio característico sempre tem raízes com multiplicidade; portanto, em circunstâncias normais, aumentar o gráfico cria novos valores próprios. Não consigo imaginar uma transformação de preservação de valores próprios em gráficos não ponderados que deixaria o número de vértices igual ou tornaria o caractere poli do novo gráfico uma potência do caractere original.

n

$n$

Emil Jeřábek 27/10

Sinto que os limites dependerão fortemente da estrutura de conectividade específica do gráfico.

Um exemplo seria um ciclo de um modo de comprimento . Com a ordem correta, não é difícil ver que , então os autovalores são todas as -ésimas raízes da unidade, ou seja, com saindo de a . $N$ $A(G)^N - I = 0$ $N$ $e^{2\pi i n/N}$ $n$ $0$ $N-1$

Para ainda , você está garantido alguns autovalores puramente imaginários e . $N$ $i$ $-i$

Agora, por outro lado, fui para Wolframalpha e liguei o gráfico completo do tamanho 4, depois removi uma única aresta. O gráfico resultante possui autovalores puramente reais (apesar de não ter uma matriz de adjacência simétrica; sim, isso pode acontecer). O que me diz que não há uma declaração geral.

Lagerbaer
fonte

Obrigado. Este é um exemplo importante. Na verdade, parece que mesmo um gráfico não simétrico muito mais esparso em 4 vértices tem um espectro real: considere os vértices v1, v2, v3, v4: tenham arestas bidirecionais entre vi e v_ {i + 1} para e uma única borda direcionada de a . Talvez seja então que, se você tiver um subgráfico cujo gráfico direcionado induzido é essencialmente não direcionado, no contexto de autovalores você poderá "contrair" esse subgráfico. De qualquer forma, modifiquei a conjectura para conter este exemplo.

i \in {1, 2, 3}

$i\in \{1,2,3\}$

v_{4}

$v_4$

v_{1}

$v_1$

Lior Eldar 18/10