4
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ For a graph with one edge this means just that $|x|^{p-2}x$ is an increasing function, no? $\endgroup$ Dec 4, 2017 at 7:20
  • $\begingroup$ 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. $\endgroup$ Dec 4, 2017 at 8:16
  • $\begingroup$ May small $p$ depend on our graph? $\endgroup$ Dec 4, 2017 at 15:08
  • $\begingroup$ 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. $\endgroup$ Dec 4, 2017 at 19:50
  • $\begingroup$ 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. $\endgroup$
    – fedja
    Dec 5, 2017 at 5:20

1 Answer 1

2
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ 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. $\endgroup$ Dec 5, 2017 at 10:36
  • $\begingroup$ Actually, I'd like to quote this proof in a paper. Is there any specific way you'd like to be mentioned? Feel free to send me a private mail if you wish, my home page is in my profile. $\endgroup$ Dec 5, 2017 at 14:10
  • $\begingroup$ @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. $\endgroup$
    – fedja
    Dec 5, 2017 at 15:02
  • $\begingroup$ By the way: is there a special reason you use the median instead of the mean value? $\endgroup$ Dec 5, 2017 at 22:53
  • $\begingroup$ @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 :-) $\endgroup$
    – fedja
    Dec 6, 2017 at 0:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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