10
$\begingroup$

Let $G$ be a simple graph with $n$ vertices and $\lambda$ be the largest eigenvalue of its Laplacian operator $L=D-A$. I have some evidence for the following conjecture:

Conjecture: If G has diameter $\delta>3$ then $\lambda\leq n-1$.

I need a proof or a counterexample for this conjecture. Does there exist a good general upper-bound for $\lambda$ in terms of $\delta$ which includes the above conjecture (if it is true)?

$\endgroup$
  • $\begingroup$ What are $D$ and $A$? $\endgroup$ – Ilya Bogdanov Nov 21 '18 at 10:50
  • 1
    $\begingroup$ @IlyaBogdanov: It seems that $A$ is the adjacent matrix of $G$ and $D$ is a diagonal matrix whose diagonal entries are degrees of the vertices of $G$. $\endgroup$ – Mahdi Nov 21 '18 at 11:29
  • $\begingroup$ For any graph, the largest eigenvalue of the Laplacian sastisfies $\lambda \leq 2$ (see e.g. Lemma 1.7 (v) in math.ucsd.edu/~fan/research/cb/ch1.pdf). So $\lambda \leq n-1$ for $n\geq 3$. Since the remaining cases have diameter at most $1$, doesn't that prove the conjecture? $\endgroup$ – Arnaud Nov 21 '18 at 11:40
  • 3
    $\begingroup$ @Arnaud: $\lambda \le 2$ for the eigenvalues of the normalized Laplacian $I - D^{-1/2}AD^{-1/2}$. $\endgroup$ – Ivan Izmestiev Nov 21 '18 at 11:48
  • $\begingroup$ @IvanIzmestiev: Thanks, I had the feeling that something was amiss. $\endgroup$ – Arnaud Nov 21 '18 at 11:54
4
$\begingroup$

I have not been able to conclude, but I think the following is a good start. (EDIT: the proof should be complete now)

Because the diameter is at least $4$, there exist $x,y$ with $d(x,y)\geq4$. In particular for all $z$ , $d(x,z)+d(y,z)\geq4$ We recall that $$ \lambda=\frac{1}{2}\max_{\sum|u(i)|^{2}=1}\sum_{i\sim j}(u(i)-u(j))^{2} $$ and therefore is monotone increasing in the edges. To consider the maximum of $\lambda$, it is enough to study the maximal graphs $G=(V,E)$ with $d(x,y)=4$. We can then suppose that for all $z$: $d(x,z)+d(y,z)=4$. (Indeed if for example $d(x,z)\geq3$ (resp. $d(y,z)$) let $z'$ such that $d(x,z')=2$, we can add the edges $(z,y)$ and $(z,z')$ to our graph).

Let us call $$ A=\text{\{}z:d(x,z)=1\text{\}} $$

$$ B=\text{\{}z:d(x,z)=2\text{\}} $$

$$ C=\text{\{}z:d(x,z)=3\text{\}} $$ Because of the maximality of $G,$ we have $$ V=A\cup B\cup C\cup\text{\{}x,y\text{\}} $$ $$ E=\text{\{}(x,z):z\in A\text{\}}\cup\text{\{}(z_{1},z_{2}):z_{1},z_{2}\in A\cup B\text{\}}\cup\text{\{}(z_{1},z_{2}):z_{1},z_{2}\in B\cup C\text{\}}\cup\text{\{}(y,z):z\in C\text{\}}. $$

Let us now consider the following orthonormal family : $1_{\text{\{}x\text{\}}},1_{\text{\{}y\text{\}}},u_{A}=\frac{1_{A}}{\sqrt{|A|}},u_{B}=\frac{1_{B}}{\sqrt{|B|}},u_{C}=\frac{1_{C}}{\sqrt{|C|}}$. We have

$$ \begin{cases} L(1_{\text{\{}x\text{\}}})=|A|1_{\text{\{}x\text{\}}}-1_{A}\\ L(1_{A})=-|A|1_{\text{\{}x\text{\}}}-|A|1_{B}+(1+|B|)1_{A}\\ L(1_{B})=-|B|1_{A}-|B|1_{C}+(|A|+|C|)1_{B}\\ L(1_{C})=-|C|1_{\text{\{}y\text{\}}}-|C|1_{B}+(1+|B|)1_{C}\\ L(1_{\text{\{}y\text{\}}})=|C|1_{\text{\{}y\text{\}}}-1_{C}. \end{cases} $$

This gives in the family $(1_{\text{\{}x\text{\}}},u_{A},u_{B},u_{C},1_{\text{\{}y\text{\}}})$ the following matrix

$$ M=\begin{pmatrix}|A| & -\sqrt{|A|} & & 0 & 0\\ -\sqrt{|A|} & |B|+1 & -\sqrt{|A||B|} & & 0\\ & -\sqrt{|A||B|} & |A|+|C| & -\sqrt{|B||C|}\\ 0 & & -\sqrt{|B||C|} & |B|+1 & -\sqrt{|C|}\\ 0 & 0 & & -\sqrt{|C|} & |C| \end{pmatrix} $$ Actually we can write $L$ as the block matrix $$ L=\begin{pmatrix}M & 0\\ 0 & L' \end{pmatrix} $$ EDIT (2) :We note $p$ the orthonormal projector on $(1_{\text{\{}x\text{\}}},u_{A},u_{B},u_{C},1_{\text{\{}y\text{\}}}) )^\perp$ and with a small abuse on notation we denote $L'=pLp$. Let $a\in A$ then $L(1_{a})=-1_{x}-1_{B}-1_{A}+(|A|+|B|)1_{a}$. We have $p(1_{a})=1_{a}-\frac{1}{\sqrt{A}}u_{A}$ and therefore $pLp(1_{a})=(|A|+|B|)(1_{a}-\frac{1}{\sqrt{A}}u_{A})$. Similar for $b\in B$ and $c\in C$. Finally we have for any $v$ $$ \langle v, pLp v\rangle=(|A|+|B|)\big(\sum_{a\in A} |v(a)|^2-\frac{1}{|A|} (\sum_{a\in A} v(a) )^2\big)+(|A|+|B|+|C|-1)\big(\sum_{b\in B} |v(b)|^2-\frac{1}{|B|} (\sum_{b\in B} v(b) )^2\big)+(|B|+|C|)\big(\sum_{c\in C} |v(c)|^2-\frac{1}{|C|} (\sum_{c\in C} v(c) )^2\big) $$ which is smaller than $(|A|+|B|+|C|-1)\|v\|^2$

So we only have to deal with $M$. The problem can be state as follow :Do we have $\|M\|\leq|A|+|B|+|C|+1$?

Here is where I get stuck. It should be possible to do a complete analysis of $M$ and calculate explicitely the largest eigenvalue but it seems a bit tedious. We can also make some numerical simulations : no counter example appear for $|A|+|B|+|C|\leq 100$

EDIT (end of the proof)

To finish the proof, we show that

$$ |A|+|B|+|C|+1-M=\begin{pmatrix}|B|+|C|+1 & \sqrt{|A|} & 0 & 0 & 0\\ \sqrt{|A|} & |A|+|C| & \sqrt{|A||B|} & 0 & 0\\ 0 & \sqrt{|A||B|} & |B|+1 & \sqrt{|B||C|} & 0\\ 0 & 0 & \sqrt{|B||C|} & |A|+|C| & \sqrt{|C|}\\ 0 & 0 & 0 & \sqrt{|C|} & |A|+|B|+1 \end{pmatrix} $$

is a positive matrix, computing all its minors determinants. Computations gives (notation :$|A|=a,|B|=b,|C|=c$):

$$ m_{1}=b+c+1 $$

$$ m_{2}=ab+ac+bc+c^{2}+c $$ $$ m_{3}=ac+b^{2}c+bc^{2}+2bc+c^{2}+c $$

$$ m_{4}=a^{2}c+2abc+2ac^{2}+ac+bc^{2}+c^{3}+c^{2} $$ $$ m_{5}=a^{3}c+3a^{2}bc+2a^{2}c^{2}+2a^{2}c+2ab^{2}c+3abc^{2}+3abc+ac^{3}+2ac^{2}+ac $$ and they are all positive.

$\endgroup$
  • 2
    $\begingroup$ Just apply the Schur test with the test vector $[|A|,(|B|+1)\sqrt{|A|},(|A|+|C|)\sqrt{|B|}, (|B|+1)\sqrt{|C|}, |C|]^T$ to check the desired bound. $\endgroup$ – fedja Nov 22 '18 at 20:56
  • 2
    $\begingroup$ Could you please give the detailed proof for the estimate on the eigenvalues of $L'$? I don't understand the usage of max- min principle here. $\endgroup$ – Mostafa Nov 23 '18 at 19:37

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.