Timeline for Maps between graphs defined through laplacian operations
Current License: CC BY-SA 3.0
28 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 7, 2017 at 11:06 | comment | added | Jake | This has now evolved somewhat (and I realise at this point that my terminology and approach in this question needed some improvement). For anyone interested, the inverse operation has some implications to topological systems in physics. We have published our work in Physical Review B and are fortunate enough for it to be an Editor's Suggestion and a featured article in APS Physics. Link: journals.aps.org/prb/abstract/10.1103/PhysRevB.95.165109 | |
| S Sep 29, 2015 at 12:50 | history | bounty ended | CommunityBot | ||
| S Sep 29, 2015 at 12:50 | history | notice removed | CommunityBot | ||
| Sep 23, 2015 at 16:15 | comment | added | Jake | Re: confusion over polynomials definition - I made a typo in the summation, which I have now fixed. Each $i$th term of course has the matrix raised to the power $i $ | |
| Sep 23, 2015 at 16:14 | history | edited | Jake | CC BY-SA 3.0 |
added 2 characters in body
|
| Sep 23, 2015 at 13:48 | comment | added | Jake | (As a "practical" example in my specific setting: those same rules apply on a honeycomb tight binding lattice but the 2nd nearest edges are described with $C^2-3C^0$. Setting $x=0$ and choosing some $y,z$, one gets the nearest-and-next-nearest energy spectrum of the honeycomb purely by analysis of the nearest-neighbour only system. The eigenstates are of course identical.) | |
| Sep 23, 2015 at 13:41 | comment | added | Jake | In my case, negative edges are indeed allowed. Consider a simple cycle graph $C$ with vertex weight 0 and edge weight 1. $C^2$ would have vertex weights 2 and edges of weight 1 between "2nd nearest neighbours". $C^0$ would have no edges, and vertices with unit weight. Under the same rules as matrix addition, $C^2 - 2C^0$ would have such edges but vertices of weight 0. You can describe a graph with some vertex weight, nearest-edges and next-nearest edges with $C' = xC^0 + yC + z(C^2 - 2C^0)$. The corresponding eigenspectrum $eig(L(C')) = \{x + yE + z(E^2 - 2) | E \in eig(L(C))\}$. | |
| Sep 23, 2015 at 13:30 | comment | added | Paul Siegel | Also, your question might be a bit easier to answer for the random walk matrix $W = D^{-1}A$. My intuition is that $W^k$ corresponds to a graph whose edges correspond to $k$-step paths in the original graph. But I have no idea what, say, $W^2 + W$ would mean (probably not much). | |
| Sep 23, 2015 at 13:25 | comment | added | Paul Siegel | If the weights of the graph are nonnegative then the Laplacian really is positive definite (by the same proof as in the unweighted case). Also, $0$ is always an eigenvalue, so you will have to consider polynomials with no constant term (and cosine is out). To answer your question properly, you will need to first have an answer to the question "What sets of real numbers can be the spectrum of a graph Laplacian?" I don't know the answer to this question, or even whether or not the answer is known. | |
| Sep 23, 2015 at 12:54 | comment | added | Jake | I'm sorry about my terminology. I mean the eigenspecrum of $L(G)$ in both cases. Take some real polynomial A. I express the polynomial $G' = A(G)$ as a graph obeying $L(G') \equiv A(L(G))$. I use polynomials as an example because a polynomial of a symmetric matrix is, too, symmetric, and $[L(G'), L(G)] = 0$ necessarily holds. In some sense, we could (?) say $[G,G']=0$. My question doesn't specifically relate to which transformations apply, but to whether it would be correct to express manipulations of graphs in this way? Also, if anyone is familiar with this being used in previous research? | |
| Sep 23, 2015 at 12:34 | comment | added | D. Kelleher | In your example, what is the polynomial of a graph? Also, is the eigenspectrum of $G$ different from the spectrum of $L(G)$? Is the question "which transformations of matrices induce a transformation on graphs"? In which case would you need the transformation on ANY Graph Laplacian to be a Laplacian of a different graph? | |
| Sep 23, 2015 at 12:17 | comment | added | Jake | As far as I'm aware, the positive semidefinite nature does not apply on weighted graphs. For example, unless im mistaken, a tight binding Hamiltonian is, effectively, a laplacian. | |
| Sep 23, 2015 at 12:12 | comment | added | Carlo Beenakker | don't you need to restrict yourself to functions that preserve the positive semi-definiteness of the Laplacian matrix? I would think that would exclude the sines and cosines you mention. | |
| Sep 23, 2015 at 12:12 | comment | added | Jake | Hi @suvrit. I have now rewritten the question in a much more concise manner. I hope this clears anything up. | |
| Sep 23, 2015 at 11:49 | history | edited | Jake | CC BY-SA 3.0 |
Complete rewrite. My initial version was far too long.
|
| S Sep 21, 2015 at 11:07 | history | bounty started | Jake | ||
| S Sep 21, 2015 at 11:07 | history | notice added | Jake | Draw attention | |
| Sep 21, 2015 at 1:12 | comment | added | Jake | Multiplication of two different graphs on the "same" vertices is trickier. As two different symmetric matrices do not generally multiply to another symmetric matrix, the resulting matrix would describe, perhaps, a multigraph. That gets hairy. However, it is perfectly valid to add two graphs through the laplacians, and (A + B)^n would be valid. Thus, whilst L (A)L(B) and L(B)L(A) do not generally describe a graph, the sum of the two must for the n=2 case to hold. | |
| Sep 21, 2015 at 0:47 | comment | added | Jake | Indeed, my confidence with the terminology is lacking, so I felt the need to explain. A bit too much maybe! The multiplication of a graph with itself results in a graph whose laplacian is the square of the original graph's laplacian. The entire algebra is defined through the laplacian - however, the focus is on the features that emerge in the graph in which the resulting laplacian represents. I have provided an example of how polynomials in a basic graph can describe more complicated structures, and that the spectrum of the resulting structures is thus polynomial in the original spectrum. | |
| Sep 21, 2015 at 0:34 | comment | added | Suvrit | Thanks for working on the question. I think that once it gets expressed with more concision that may help. Is one of the questions: "Let $A$ be the following algebra on graph Laplacians.... Has this algebra been previously studied?" (but how is multiplication defined?) | |
| Sep 21, 2015 at 0:12 | comment | added | Jake | Note the interesting result in this is that the laplacian of the original chain has a set of eigenvalues - the polynomials of the nth neighbour graphs have an eigenspectrum corresponding to their polynomial over the original spectrum. | |
| Sep 20, 2015 at 19:43 | comment | added | Jake | Edit: Added an animation showing a cycle graph under "nth nearest neighbour" polynomials. The first of these polynomials are: $M^0$, $M^1$, $M^2 - 2M^0$, $M^3 - 3M$, $M^4 - 4M^2 + 2M^0$. Higher polynomials were calculated with a simple recursion algorithm, which works by eliminating lower order polynomials according to the binomial expansion. | |
| Sep 20, 2015 at 19:40 | history | edited | Jake | CC BY-SA 3.0 |
Added an animation to show the "nth nearest" polynomials in action.
|
| Sep 19, 2015 at 14:39 | comment | added | Jake | I hope the question is more user-friendly now. I have summarised my question at the top, and sectioned it out a little. | |
| Sep 19, 2015 at 14:38 | history | edited | Jake | CC BY-SA 3.0 |
Structural improvements and a "short version" of the question for clarity.
|
| Sep 19, 2015 at 14:25 | comment | added | Jake | Thank you, in retrospect it is rather messy. I did highlight the main point in bold, but I think this question is in need of a rewrite. Stay tuned! | |
| Sep 19, 2015 at 14:00 | comment | added | Suvrit | If you would highlight the precise question using markdown syntax, that would make this post more user friendly. | |
| Sep 19, 2015 at 1:52 | history | asked | Jake | CC BY-SA 3.0 |