Dikotomi dari spektrum grafik berarah

Dibandingkan dengan spektrum grafik tidak berarah, yang sesuai dengan matriks simetris, spektrum grafik berarah tidak terlalu dikenal:

Diketahui bahwa graf berarah $G = (V,E)$ memiliki matriks adjacency $A(G)$ yang nilai eigennya adalah biner $\{0,1\}$ jika $G$ adalah a-siklik. Ini mengikuti dengan menyortir simpul ke dalam komponen terhubung kuat: perbaikan ini penghitungan simpul $v_1,.., v_n$ sehingga menurut Laplacian permutasi untuk memesan ini atas-segitiga dengan $0/1$ entri.

Tetapi apa yang diketahui jika $G$ adalah ujung ekstrem lainnya - yaitu $G$ adalah grafik yang sangat terhubung pada $n$ simpul - artinya ada jalur terarah di antara setiap pasangan simpul.

Secara umum, seseorang perlu menghitung polinomial karakteristik $A(G)$ dan menghitung akarnya. Meskipun $A(G)$ menjadi matriks $\{0,1\}$ ini sepertinya tugas yang menakutkan. Secara khusus, akar polinomial ini dalam bilangan kompleks umum.

Teorema Perron-Frobenius menyiratkan bahwa setidaknya nilai eigen teratas adalah nyata dan sederhana, tetapi tidak mengungkapkan informasi tentang sisa nilai eigen.

Namun, bagaimana jika kami hanya tertarik pada batas yang sangat lemah dari bentuk berikut:

$\textbf{Conjecture: Dichotomy of eigenvalues}$ : Misalkan $G$ adalah grafik berarah pada $n$ simpul. Maka baik semua nilai eigen dari $A_G$ adalah nyata, atau terdapat setidaknya satu nilai eigen $\lambda$ sehingga $im(\lambda)\geq 1/poly(n)$ .

Apakah batas-batas tersebut mengikuti sepele dari teorema yang dikenal? Atau, dapatkah grafik yang diarahkan memiliki nilai eigen dengan komponen imajiner yang kecil secara eksponensial?

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

Grafik yang pada dasarnya tidak diarahkan, yaitu setiap sisi muncul di kedua arah, akan memiliki Laplacian simetris dan semua nilai eigen akan menjadi nyata. Mengapa itu bukan contoh tandingan terhadap dugaan Anda? Juga apa yang Anda sebut "sangat teratur" bagi saya sepertinya "sangat terhubung". Apakah ada perbedaan?

Sasho Nikolov

Maaf - memperbaiki kesalahan ketik pada dugaan. Grafik yang sangat teratur tidak terarah - ada PATH terarah antara setiap dua simpul, bukan EDGE terarah.

Lior Eldar

Saya tidak mendapatkan penjelasan Anda. Bukankah tepi jalur panjang 1? Mengapa grafik yang berisi setiap sisi di kedua arah sangat tidak teratur? Apakah Anda memerlukan grafik untuk tidak memiliki siklus panjang 2?

Sasho Nikolov

Ah - Begitu - saya sudah mengoreksi dugaan untuk mencerminkan contoh Anda. Saya ingin mempertimbangkan hanya grafik yang diarahkan sangat terhubung yang pada dasarnya tidak "tidak diarahkan". Terima kasih.

Lior Eldar

Bisakah grafik yang diarahkan memiliki nilai eigen dengan komponen imajiner yang kecil secara eksponensial? Saya cukup yakin itu bisa. Namun, ini tidak menghalangi keberadaan nilai eigen lain dengan komponen imajiner polinomi kecil, jadi saya tidak melihat bagaimana ini berhubungan dengan dugaan. Apakah Anda yakin tidak mencampuradukkan penjumlahan eksistensial dan universal?

Emil Jeřábek

Jawaban:

Jawaban untuk "sebagai alternatif, dapatkah grafik yang diarahkan memiliki nilai eigen dengan komponen imajiner yang kecil secara eksponensial" adalah YA (meskipun saya tidak mengerti apa yang "alternatif" tentang pernyataan ini, karena tidak dengan cara apa pun membantah dugaan).

$f\in\mathbb Z[x]$ $G$ $O(\deg(f)+\|f\|_1)$ $f$ seperti yang mudah ditemukan seperti yang saya harapkan, jadi saya memutuskan untuk menuliskannya sebagai jawaban yang tepat untuk catatan itu.

Beberapa contoh polinomial dengan pemisahan akar kecil secara eksponensial didaftar oleh Schonhage [1], khususnya keluarga polinomial dikaitkan dengan Mignotte [ 2] (yang saya tidak dapat memverifikasi karena saya tidak memiliki akses ke sana saat ini). Sekarang, polinomial ini memiliki masing-masing sepasang akar nyata dekat dalam jarak , sedangkan kita membutuhkan sepasang akar kompleks . Namun, ini mudah dilakukan dengan memodifikasi polinomial sedikit: misalkan Jelas, polinomial ini tidak memiliki akar real positif (dan tidak ada root real negatif baik jika

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$ bahkan). Selain itu, mudah untuk menunjukkan bahwa ia masih memiliki sepasang (tentu non-real) akar dalam jarak kecil secara eksponensial menjadi ; jika saya tidak mengacaukan perhitungan, akar-akar ini kira-kira Sekarang, dapat ditulis sebagai penentu misalnya matriks dan oleh karena itu sebagai polinomial karakteristik dari matriks kedekatan dari graf berarah tertimbang pada simpul <

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$ ; dari bobot ; dari berat ; dan dari berat . Nilai eigen dari dengan demikian persis merupakan akar dari , termasuk .

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$

Akhirnya, nilai eigen dari termasuk di antara nilai eigen dari grafik diarahkan tanpa bobot pada simpul dengan tepi dan untuk ; dan untuk ; , ; dan , , , untuk $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$ .

Referensi:

[1] A. Schönhage, contoh pemisahan akar polinomial , Journal of Symbolic Computation 41 (2006), no. 10, hlm. 1080–1090, doi: 10.1016 / j.jsc.2006.06.003 .

[2] M. Mignotte, Beberapa batasan yang bermanfaat , dalam: Buchberger, Collins, Loos (eds.), Aljabar Komputer: Komputasi Simbolik dan Aljabar, edisi kedua, Springer-Verlag, 1983, hlm. 259–263, doi: 10.1007 / 978-3-7091-7551-4_16 .

Emil Jeřábek
sumber

Selain itu, sangat terhubung jika penting.

G_{1}

$G_1$

Emil Jeřábek

Terima kasih. Ini sangat informatif. Meskipun ini bukan semata-mata grafik terarah melainkan grafik berbobot dengan bobot yang sewenang-wenang. Jadi itu menjawab generalisasi di atas, benar ?? Tentunya mudah untuk menghasilkan grafik dengan nilai eigen kecil yang sewenang-wenang jika Anda mengizinkan bobot sewenang-wenang (misalnya, satu simpul dengan loop mandiri 2 ^ {- n} berat), tetapi dugaan tersebut mencoba untuk menangkap apakah Anda bisa mendapatkan nilai eigen kecil yang eksponensial bahkan dengan elemen {0,1}. Namun, saya pikir menunjukkan ini dengan O (1) bobot memenuhi syarat sebagai kemajuan.

Lior Eldar

Anda melewatkan intinya. adalah tidak graf berbobot. Ini adalah grafik terarah normal.

G_{1}

$G_1$

Emil Jeřábek

Apa cara termudah untuk memastikan bahwa spektrum terkandung dalam ?

G_{1}

$G_1$

G_{0}

$G_0$

Lior Eldar

Saya pikir itu tidak mungkin. Polinom karakteristik selalu memiliki akar dengan multiplisitas, jadi dalam keadaan normal, memperbesar grafik menciptakan nilai eigen baru. Saya tidak bisa membayangkan transformasi nilai eigen dari grafik berbobot menjadi tak berbobot yang akan membuat jumlah simpul sama, atau membuat char char dari grafik baru menjadi kekuatan dari char char original.

n

$n$

Emil Jeřábek

Saya merasa batas-batasnya akan sangat bergantung pada struktur konektivitas tertentu dari grafik.

Salah satu contoh akan menjadi siklus satu arah panjang . Dengan urutan yang benar, tidak sulit untuk melihat bahwa , sehingga nilai eigen semuanya adalah akar ke- kesatuan, yaitu dengan pergi dari hingga . $N$ $A(G)^N - I = 0$ $N$ $e^{2\pi i n/N}$ $n$ $0$ $N-1$

Untuk bahkan , Anda dijamin beberapa nilai eigen murni imajiner dan . $N$ $i$ $-i$

Sekarang di sisi lain, saya pergi ke Wolframalpha dan terhubung ke grafik lengkap ukuran 4, kemudian menghapus satu tepi. Grafik yang dihasilkan memiliki nilai eigen murni nyata (walaupun tidak memiliki matriks adjacency simetris; ya, itu bisa terjadi). Yang memberitahu saya bahwa tidak ada pernyataan umum.

Lagerbaer
sumber

Terima kasih. Ini adalah contoh penting. Sebenarnya tampaknya bahwa grafik non-simetris yang jauh lebih jarang pada 4 simpul memiliki spektrum nyata: pertimbangkan simpul v1, v2, v3, v4: memiliki tepi berarah dua antara vi dan v_ {i +1} untuk dan satu tepi terarah tunggal dari ke . Mungkin itu adalah kasus bahwa jika Anda memiliki subgraph yang grafik yang diinduksi pada dasarnya tidak diarahkan, maka dalam konteks nilai eigen Anda dapat "mengontrak" subgraph itu. Bagaimanapun, saya telah memodifikasi dugaan untuk mengandung contoh ini.

i \in {1, 2, 3}

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

v_{4}

$v_4$

v_{1}

$v_1$

Lior Eldar