An elementary inequality for graph Laplacians

Question

Let $G$ be an arbitrary graph on $n$ vertices and $\mathcal L$ be its Laplacian. I need to show that \begin{equation}\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 \end{equation} 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.

Answer 1

$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)$.

Of course, you can try to get more precise result here, but my point was that the question is a no-brainer for anybody who just recognized once in his life that he has no hope to master the high art of Calculus and confined himself to the low craft of Analysis instead.