Dichotomie der Spektren gerichteter Graphen

Im Vergleich zu Spektren ungerichteter Graphen, die symmetrischen Matrizen entsprechen, sind die Spektren gerichteter Graphen nicht sehr bekannt:

Es ist bekannt, dass ein gerichteter Graph $G = (V,E)$ eine Adjazenzmatrix $A(G)$ deren Eigenwerte binär $\{0,1\}$ wenn $G$ a-zyklisch ist. Dies folgt durch Sortieren der Scheitelpunkte in stark verbundene Komponenten: Dadurch wird eine Aufzählung der Scheitelpunkte $v_1,.., v_n$ , so dass das permutierte Laplace gemäß dieser Anordnung der obere Dreieck mit ist $0/1$ - Einträge.

Was aber bekannt ist, wenn $G$ das andere extreme Ende ist - dh $G$ ist ein stark verbundener Graph auf $n$ Eckpunkten -, was bedeutet, dass zwischen jedem Eckpunktpaar ein gerichteter Pfad besteht.

Im Allgemeinen müsste man das charakteristische Polynom von $A(G)$ berechnen und seine Wurzeln berechnen. Obwohl $A(G)$ eine $\{0,1\}$ -Matrix ist, scheint dies eine entmutigende Aufgabe zu sein. Insbesondere liegen die Wurzeln dieses Polynoms in allgemein komplexen Zahlen.

Das Perron-Frobenius-Theorem impliziert, dass zumindest der obere Eigenwert real und einfach ist, aber keine Informationen über den Rest der Eigenwerte preisgibt.

Was ist jedoch, wenn wir nur an sehr schwachen Grenzen der folgenden Form interessiert sind:

: Sei G ein gerichteter Graph auf n Eckpunkten. Dann sind entweder alle Eigenwerte von A G reell oder es existiert mindestens ein Eigenwert λ, so dass i m ( λ ) ≥ 1 / p o l y ( n ) ist .$\textbf{Conjecture: Dichotomy of eigenvalues}$$G$$n$$A_G$$\lambda$$im(\lambda)\geq 1/poly(n)$

Folgen solche Grenzen trivial aus bekannten Theoremen? Kann ein gerichteter Graph alternativ einen Eigenwert mit einer exponentiell kleinen imaginären Komponente haben?

Die Antwort auf „Alternativ kann ein gerichteter Graph einen Eigenwert mit einer exponentiell kleinen imaginären Komponente haben“ lautet JA (obwohl ich nicht verstehe, was an dieser Aussage „alternativ“ ist, da sie die Vermutung in keiner Weise widerlegt).

Wie ich bereits in einem Kommentar geschrieben habe, ist es nicht sehr schwierig zu zeigen, dass, wenn ein monisches Polynom ist, ein gerichteter Graph G auf O ( deg ( f ) + ‖ f ‖ 1 ) Eckpunkten existiert deren Eigenwerte alle Wurzeln von f umfassen . Dies impliziert die obige modulo-Aussage, dass solche Polynome Wurzeln mit exponentiell kleinem Imaginärteil haben können, was ich in der Literatur zur minimalen Wurzeltrennung als leicht zu finden angenommen habe. Mir wurde jedoch klar, dass solche Grenzen tatsächlich nicht vorhanden sind$f\in\mathbb Z[x]$$G$$O(\deg(f)+\|f\|_1)$$f$ so leicht zu finden, wie ich es erwartet hatte, also beschloss ich, es als richtige Antwort für die Aufzeichnung zu schreiben.

Schönhage [1] listet einige Beispiele für Polynome mit exponentiell geringem Wurzelabstand auf, insbesondere die Familie der Polynome wird Mignotte [2] zugeschrieben (was ich nicht überprüfen kann, da ich momentan keinen Zugriff darauf habe). Diese Polynome haben nun jeweils ein PaarreellerWurzeln in der Nähe von 1 / c in einem Abstand < 2 / c 1 + n / 2 , während wir ein PaarkomplexerWurzelnbenötigen. Dies kann jedoch leicht erreicht werden, indem das Polynom leicht modifiziert wird: sei f ( x ) = x n + ) 2 = x

$$x^n-2(cx-1)^2\qquad(n\ge3,c\ge2)$$ $1/c$$<2/c^{1+n/2}$ Dieses Polynom hat eindeutig keine positive reelle Wurzel (und auch keine negative reelle Wurzel, wenn n gerade ist). Darüber hinaus ist es leicht zu zeigendass es nach wie vor ein Paar von (nicht notwendigerweise real) Wurzeln in exponentiell kleinem Abstand hatum 1 / 2 ; Wenn ich die Berechnung nicht durcheinander gebracht habe, sind diese Wurzeln ungefähr z ± = $$f(x)=x^n\mathbin{\color{red}+}(2x-1)^2=x^n+4x^2-4x+1.$$ $n$$1/2$ Nun kannf(x)als Determinante von zB dern×n-Matrix geschrieben werden $$z_\pm=\frac12\pm i2^{-1-\frac n2}+O(n2^{-n}).$$ $f(x)$$n\times n$ und daher als charakteristisches Polynom der Adjazenzmatrix des gewichteten gerichteten GraphenG0aufnEckpunkten{0,…,n-1}mit Kanteni $$\begin{pmatrix} x&-1\\ &x&-1\\ &&x&-1\\ &&&\ddots\\ &&&&x&-1\\ 1&-4&4&&&x \end{pmatrix}$$ $G_0$$n$$\{0,\dots,n-1\}$ von Gewicht 1 für i = 0 , … , n - 2 ; n - 1 → 0 des Gewichts - 1 ; $i\to i+1$$1$$i=0,\dots,n-2$$n-1\to0$$-1$$n-1\to1$von Gewicht ; und n - 1 → 2 des Gewichts - 4 . Die Eigenwerte von G 0 sind also genau die Wurzeln von f , einschließlich z ± .$4$$n-1\to2$$-4$$G_0$$f$$z_\pm$

Schließlich sind die Eigenwerte von unter den Eigenwerten des ungewichteten gerichteten Graphen G 1 auf 2 n + 6 Eckpunkten 0 + , 0 - , … , ( n - 2 ) + , ( n $G_0$$G_1$$2n+6$ + mit Kanteni+→(i+1)+undfüri=0,…,n-3; (n-2)+→(n-1)

$$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)_+$, ( n - 1 ) j -$i_-\to(i+1)_-$$i=0,\dots,n-3$$(n-2)_+\to(n-1)_+^j$und für j = 0 , … , 3 ; ( n - 1 ) 0 + → 0 - , ( n - 1 ) 0 - → 0 + ; und ( n - 1 ) j + → 1 + , ( n $(n-2)_-\to(n-1)_-^j$$j=0,\dots,3$$(n-1)_+^0\to0_-$$(n-1)_-^0\to0_+$$(n-1)_+^j\to1_+$$(n-1)_+^j\to2_-$ , ( n - 1 ) j - → 2 + für j = 0 , … , 3 .$(n-1)_-^j\to1_-$$(n-1)_-^j\to2_+$$j=0,\dots,3$

Verweise:

[1] A. Schönhage, Beispiele für Polynomwurzeltrennung, Journal of Symbolic Computation 41 (2006), Nr. 10, S. 1080–1090, doi: 10.1016 / j.jsc.2006.06.003 .

[2] M. Mignotte, Einige nützliche Grenzen , in: Buchberger, Collins, Loos (Hrsg.), Computer Algebra: Symbolic and Algebraic Computation, 2. Auflage, Springer-Verlag, 1983, S. 259–263, doi: 10.1007 / 978-3-7091-7551-4_16 .

Ich habe das Gefühl, dass die Grenzen sehr stark von der jeweiligen Konnektivitätsstruktur des Diagramms abhängen.

$N$$A(G)^N - I = 0$$N$$e^{2\pi i n/N}$$n$$0$$N-1$

$N$$i$$-i$

Auf der anderen Seite ging ich zu Wolframalpha, steckte das komplette Diagramm der Größe 4 ein und entfernte dann eine einzelne Kante. Der resultierende Graph hat rein reale Eigenwerte (obwohl keine symmetrische Adjazenzmatrix vorhanden ist; ja, das kann passieren). Was mir sagt, dass es keine allgemeine Aussage gibt.