Terikat pada nilai eigen yang lebih kecil dari matriks adjacency grafik

Apakah ada batasan (non-sepele) yang diketahui (sifatnya kombinatorial, berdasarkan pada sifat komputable waktu-pol dari suatu grafik) pada yang ketiga, hingga nilai eigen terkecil dari matriks adjacency (tidak berbobot)? Misalnya kita tahu bahwa nilai eigen terbesar mengakui batasan berikut Apa saja rasa di atas untuk , ? (Mengingat bahwa ini bisa negatif, (lebih rendah) yang mungkin tampak lebih menarik.)

maks (\sqrt{d_{maks}}, d_{ave}) \leq λ_{maks} = λ_{1} \leq d_{maks}

$\max(\sqrt{d_{\max}}, d_{\text{ave}})\le \lambda_{\max}=\lambda_1 \le d_{\max}$

λ_{i}

$\lambda_i$

i \geq 3

$i\ge 3$

| λ_{i} |

$|\lambda_i|$

graph-theory co.combinatorics spectral-graph-theory Dimitris
sumber

Jawaban:

Anda mungkin menyukai makalah terbaru ini: http://arxiv.org/abs/1211.0589v1

Makalah ini menunjukkan, misalnya, bahwa " untuk graf berhingga mana saja dengan simpul dan semua , nilai eigen terbesar ke- $n$ $k ≥ 2$ $k$ " dari Laplacian grafik, yaitu , " paling banyak ", di mana adalah matriks kedekatan dan terikat pada derajat. $L=I-A/d$ $1−\Omega(\frac{k^3}{n^3})$ $A$ $d$

Martin Schwarz
sumber