Question | Population Algorithms by Petar Maymounkov

L1 bounds for Laplacians – No Comments

Under Computer Science, Graph spectra, Question, Spontaneous

Spectral Graph theory has various methods of bounding the Laplacian eigenvalues of a graph G (say by embedding another graph H into G and computing the congestion). Usually we look at the ordered eigenvalues $0=\lambda_1<\lambda_2\le \cdots \le \lambda_n$ , and usually we simplify things a little by assuming a bounded-degree graph, which gives us $\lambda_n\le D_{\max}=O(1)$ for free, where $D_{\max}$ is the maximum vertex degree. So really, it is mostly just interesting to bound $\lambda_2$ from below. When this is done, it is very often used as $\|L^{-1}x\|_2 \le \lambda_2^{-1} \|x\|_2$ (when bounding energy of electrical flows in G) or as $\|(I-L)^kx\|_2\le (1-\lambda_2)^k \|x\|_2$ (when bounding mixing times of random walks on G).

We are interested in a new type of Laplacian bounds. It turns out that L1 bounds of the sort $\min_{x\bot\vi,\|x\|_1=1}\|Lx\|_1\ge \eta$ relate directly to how good electrical flow is when used for oblivious routing on G. Note that it is required here that $x\bot\vi$ since $\vi$ is the kernel of the Laplacian of any connected graph. This sort of bound is atypical in two ways. First, it is an L1 bound, and second, it is a lower-bound.

It is trivial to see that $\|L_{K_n}x\|_1=n$ where $L_{K_n}$ is the Laplacian of the n-clique. What we are after is proving that

$\|L_H x\|_1\ge (\log n)^{-1}$ where H is an expander and $\|x\|_1=1$ and $x\bot\vi$ .

This statement holds true in experiments with random bounded-degree expanders, and in particular it has natural interpretations in terms of electrical flow (which I am going to omit here). One can even give a pseudo-proof of this fact by simply observing that $L_H \approx L_{K_n} / n\log n$ .

I am curious if someone has come across similar types of inequalities and/or has an interesting proof idea.

Note that the above conjecture was recently proven and its proof will soon appear in a publication. I will post a link to it here when this happens. At this stage will be happy to hear of applications of this (now) theorem if you come across any.

Positive semidefinite operators and norm polytopes – 5

Under FA: Functional Analysis, Question

I’ve been obsessing over the following conjecture. And to be honest I haven’t been able to find any counterexamples, nor make any significant progress towards proving it. So, here goes:

If $A,B$ are positive semidefinite and $A\preccurlyeq B$ , then $\|A\|_{1\rightarrow 1} \le \|B\|_{1\rightarrow 1}$ .

In fact, it seems that if this is true for the $\|\cdot\|_{1\rightarrow 1}$ -norm, it probably is true for all norms of the form $\|\cdot\|_{p\rightarrow p}$ . Any ideas or references would be greatly appreciated.