# An elementary inequality for graph Laplacians

Let $G$ be an arbitrary graph on $n$ vertices and $\mathcal L$ be its Laplacian. I need to show that $$\tag{*} \langle \mathcal Lx,\mathcal L(|x|^{p-2}x)\rangle_{\mathbb R^n}\ge 0\qquad \hbox{for all }x\in \mathbb R^n$$ and small $p\in (2,\infty)$ (my guess is that $p\approx 3$ will do), where $|x|^{p-2}x$ is the coordinatewise product (a Hadamard product, if you wish). This looks like a very simple expression, but I was unable to prove it analytically (= by methods of Calculus 1), even in the case of a graph consisting of a single edge.

(Additional information: I can prove by abstract nonsense that $(*)$ holds for all $p\in (1,\infty)$ if and only if $G$ is a complete graph; but after playing a bit with maple I can say that counterexamples seem to be extremely rare (for the path graph on 3 vertices and the vector $x=(\frac{7}{4}\pm\epsilon,1,-1)$, $(*)$ fails for all $p\ge 6$ and very small $\epsilon$, though).)

Any help is appreciated.

Update: as pointed out in the comments, the case of a one-edge-graph is actually trivial.

• For a graph with one edge this means just that $|x|^{p-2}x$ is an increasing function, no? Dec 4, 2017 at 7:20
• Well, for a graph with one edge the inequality is $(x-y)(|x|^{p-2}x-|y|^{p-2}y)\ge 0$ for all $x,y\in \mathbb R$, so yes, you're right, I was overlooking this and all I am claiming is that $|x|^{p-2}x$ is an increasing function. So that's proved. But this does not carry over to the general case, as my example shows. Dec 4, 2017 at 8:16
• May small $p$ depend on our graph? Dec 4, 2017 at 15:08
• Yes, it may well. As I said, I can prove that the infimal $p$ for which $(*)$ fails blows up if and only if $G$ is complete. Dec 4, 2017 at 19:50
• Obviously, if you take the star with the center of large degree $d$, the inequality can be violated for all $p>p(d)\to 2$ as $d\to\infty$ (only the center really matters because the Laplacian there is of size $d$ while everywhere else it is of size $1$ and $d$ ones lose to one $d^2$). So there is no way you can get a universal notion of "smallness", i.e., $\approx 3$ is too optimistic. Let's see if $2<p<p(G)$ with some $p(G)>2$ is a feasible range. Dec 5, 2017 at 5:20

$2<p<p(G)$ with $p(G)>2$ is, indeed, possible. Moreover, it is Analysis 1. Calculus 1 is an extremely difficult subject, never try to learn it yourself or to explain it to your students. It is way above a normal person's head! (It is second in difficulty only to Business Calculus, which is just beyond the comprehension of any human being). Analysis 1, on the other hand, can be explained to a 10-year old.
Let's normalize somehow. Since Laplacian is related to the gradient squared, assume that $\sum_{x\sim y}|f(x)-f(y)|^2=1$. Then the oscillation of $f$ is bounded by some $C(G)$. We also have our beautiful relation $\sum_x (f(x)-F)\mathcal Lf(x)=\sum_{x\sim y}|f(x)-f(y)|^2=1$ for any $F\in\mathbb R$ (or $-1$ depending on what you subtract from what in the definition of $\mathcal L$). Subtracting the median, we get $|f-F|\le C(G)$, so, by Cauchy-Schwarz, $\sigma(f)=\sum_x(\mathcal Lf(x))^2\ge c(G)$. Now, assume that the median $F$ of $f$ is in some moderate range $[-A,A]$. Then we have $y|y|^\alpha\to y$ uniformly on $[-A-C(G),A+C(G)]$ as $\alpha=p-2\to 0+$ and your expression tends to $\sigma(f)\ge c(G)$ uniformly over $f$ with values in that range. So for each $A$, you are fine with $\alpha<\alpha_0(A,G)\in(0,1)$. It remains to investigate what happens if $F$ is huge. Then your function can be written as $F+g$, $|g|\le C(G)\ll F$, so (assuming that $F>0$, the other case is similar) $$|f(x)|^\alpha f(x)-|f(y)|^\alpha f(y)=F^{1+\alpha}(1+g(x)/F)^{1+\alpha}-(1+g(y)/F)^{1+\alpha}\\ =F^{1+\alpha}[(1+\alpha)(g(x)-g(y))/F+O(|g(x)-g(y)|(|g(x)|+|g(y)|)/F^2) =(1+\alpha)F^\alpha(g(x)-g(y))+O(|g(x)-g(y)|(|g(x)|+|g(y)|)/F^{1-\alpha})$$ This means that $F^{-\alpha}(\mathcal L|f|^\alpha f)(x)$ uniformly tends to $(1+\alpha)\mathcal Lf(x)$ as $F\to\infty$, so the expression you are interested in is asymptotic to $(1+\alpha)F^\alpha \sigma(f)$ for large $F$ with any $\alpha\in(0,1)$, say. Thus there exists $A$ such that for all $|F|>A$ you have positivity in the range $0<\alpha<1$. Take this $A$ and put $p(G)=2+\alpha(A,G)$.
• Thank you very much. You are very right about the advantages of Analysis (and all the more so of Russian Analysis) over Calculus. That said, when I was estimating $p\approx 3$ I was actually being pessimistic: what you've just proved is that the exponential matrix generated by (minus) the discrete bi-Laplacian is always contractive wrt $p$-norm, and the set of such $p$'s can get arbitrarily large, which is in my eyes says that a certain ODE is well-behaved. Dec 5, 2017 at 10:36
• @DelioMugnolo You are welcome! As to Calculus vs Analysis, when you are at the board in the classroom you are the only one to choose which one to teach (if you are above the level when students' squeaks can damage your position in any way). As to quoting, just cite MO. There are instructions somewhere (I have never learned where exactly) on the MO web page about how to do it most properly, but I guess that if you just use your common sense, that will work too. As to "large range of $p$", yes, it can get large, but it can get small as well. Depends on the graph structure. Dec 5, 2017 at 15:02
• @DelioMugnolo Not really. Anything from $\min$ to $\max$ will work nicely. It was just the first "m"-word that came to my head. That's it :-) Dec 6, 2017 at 0:23