2
$\begingroup$

Let $L$ be the Laplacian matrix of a simple, connected graph, and $\mathcal{P}_j$ the projector into the vertex $v_j$, represented by the appropriate canonical basis vector $(0,...,1,...,0)^T$. Given the positive real parameters $t$ and $\lambda$, consider the functions $$P_j(n,t,\lambda)=v_j^T e^{-it(\lambda L-\mathcal{P}_j)}s, $$ where $s=\frac{1}{\sqrt{n}}(1,...,1)^T$ is the normalized uniform vector.

My objective is to show that the condition $P_i=P_j$ implies the degrees of the two vertices $v_i$ and $v_j$ are the same. Does anyone have any tips on how to accomplish this?

Improve this question
$\endgroup$
2
  • $\begingroup$ (1) Using $t$ for transpose and for time is not a good idea. (2) What’s coordination number? $\endgroup$
    – Chris Godsil
    Commented Sep 5, 2020 at 14:31
  • $\begingroup$ @ChrisGodsil You are not wrong, I edited the post. I believe the more familiar English term for coordination number is degree of a vertex, so I changed that as well. $\endgroup$
    – Ugly Duckling
    Commented Sep 5, 2020 at 16:25

1 Answer 1

Reset to default
3
$\begingroup$

I'll take $\lambda=1$ and use $E_j$ for $\mathcal{P}_j$. The $k$-th time derivative of $e^{-it(L-E_j)}s$ at $t=0$ is \[ (-i(L-E_j))^k s. \] Now $(L-E_j)s = -v_j$ (because $Ls=0$) and, noting that $E_j=v_jv_j^T$, we have \[ (L-E_j)^2s = -(L-E_j)v_j = -Lv_j +v_j. \] Therefore \[ v_j^T(L-E_j)^2s = -v_j^T Lv_j + 1 = - L_{j,j} + 1. \] Since $L_{j,j}$ is the degree of vertex $j$, it follows that if $P_i=P_j$, then $i$ and $j$ have the same degree.

[I am curious as to where this problem is coming from?]

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thank you very much, Chris. Your answer is pretty close to what I was building up to: the big difference is that I was trying to calculate directly $(L-E_j)^k$ (I got stuck there and even asked another question here). I missed the idea of taking the time derivative! [I am an undergraduate physicist doing some research in quantum computation theory, the problem comes from there :)] $\endgroup$
    – Ugly Duckling
    Commented Sep 6, 2020 at 12:02
  • $\begingroup$ I'm thinking of a more general version of the problem. Right now we have found a necessary condition for $P_i=P_j$, but I have reasons to conjecture that $P_i=P_j$ if and only if there exists $\sigma\in\text{Aut}(G)$ such that $\sigma(v_i)=v_j$ (which of course implies the two vertices have the same degree). I'm open to ideas for a proof... but of course not a complete answer! $\endgroup$
    – Ugly Duckling
    Commented Sep 6, 2020 at 15:22
  • $\begingroup$ That will fail. Choose your graph to be strongly regular and asymmetric. $\endgroup$
    – Chris Godsil
    Commented Sep 6, 2020 at 22:55
  • $\begingroup$ That's bad news. I was guided by the path graph, for which $P_i=P_{n-i+1}$, and of course this is consistent with the action of the path-reversing $\sigma$. Also, $P$ is constant over the symmetric cycle graph, and for every non-central vertex of the wheel or star graphs. However I saw that it fails for Frucht graphs, which are $3-$regular but asymmetric, and yet $P$ is constant. Could it actually just be a sufficient, but not necessary condition? $\endgroup$
    – Ugly Duckling
    Commented Sep 7, 2020 at 1:30
  • $\begingroup$ I think the answer is that trivially when there is an automorphism all properties of the vertex, including $P$, are carried over to its image. Then, other properties like (strong) regularity may play a role. I was also thinking of studying the distance matrices of these graphs to see if they have something in common... $\endgroup$
    – Ugly Duckling
    Commented Sep 7, 2020 at 1:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .