Timeline for What is the n-th power of the adjacency matrix equal to?
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Oct 18, 2020 at 8:57 | history | suggested | gmvh |
Added top-level tag
|
|
| Oct 18, 2020 at 8:14 | review | Suggested edits | |||
| S Oct 18, 2020 at 8:57 | |||||
| Nov 13, 2015 at 10:53 | answer | added | Mohammed | timeline score: 0 | |
| Sep 11, 2013 at 18:20 | review | Suggested edits | |||
| Sep 11, 2013 at 18:36 | |||||
| Jun 13, 2011 at 14:07 | answer | added | Aaron Meyerowitz | timeline score: 2 | |
| May 16, 2011 at 16:04 | comment | added | Richard Stanley | There is a theory of loop-erased random walks on a graph, where one does a random walk and erases a loop (cycle) as soon as it is created. This gives a model for a random path that is closely connected to random spanning trees. See en.wikipedia.org/wiki/Loop-erased_random_walk. However, this model has little connection with powers of the adjacency matrix. | |
| May 16, 2011 at 9:16 | comment | added | Qiaochu Yuan | @adamo: there isn't a way to directly transfer questions between sites from different generations (math.SE is 2.0). You could repost it, but I think what's been said so far is already pretty good. | |
| May 16, 2011 at 9:05 | answer | added | Mark Meilstrup | timeline score: -1 | |
| May 16, 2011 at 9:02 | comment | added | Johan Wästlund | I'm not sure I understand exactly what is being asked for, but an efficient algorithm counting self-avoiding walks of given length between two given vertices would lead to an efficient algorithm deciding hamiltonicity. Unless P=NP this is harder than matrix multiplication. | |
| May 16, 2011 at 8:42 | history | edited | adamo | CC BY-SA 3.0 |
Added complimentary question
|
| May 16, 2011 at 8:13 | answer | added | P.H. | timeline score: 0 | |
| May 16, 2011 at 8:05 | comment | added | Gerhard Paseman | That's too bad, because the answer is so nice in terms of walks. It is hard to relate to pure paths because of not knowing how to eliminate nicely the cyclic portion of the walk. If you have some more information on the situation, such as n is very small, or the graph has very few cycles, then you might be able to describe such a relation. Without that, the best you can do in general is an upper bound. Gerhard "Ask Me About System Design" Paseman, 2011.05.16 | |
| May 16, 2011 at 8:04 | comment | added | Qiaochu Yuan | It doesn't have a simple interpretation in terms of paths; the adjacency matrix is naturally suited for studying walks. This is not really an appropriate question for MO; you might want to try math.stackexchange.com. | |
| May 16, 2011 at 7:51 | history | asked | adamo | CC BY-SA 3.0 |