Timeline for Representation of Subgraph Counts using Polynomial of Adjacency Matrix
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 11, 2019 at 8:11 | comment | added | Minkov | @JoshuaGrochow Thanks a lot for the reference and your answer. | |
| Mar 11, 2019 at 7:53 | comment | added | Joshua Grochow | BTW, although it is clearly not the same question, you might be interested in Ziv, Koytcheff, Middendorf, and Wiggins. | |
| Mar 11, 2019 at 7:51 | answer | added | Joshua Grochow | timeline score: 1 | |
| Mar 11, 2019 at 6:46 | history | edited | Minkov | CC BY-SA 4.0 |
added 48 characters in body
|
| Mar 11, 2019 at 6:45 | comment | added | Minkov | @DavidRoberson I now see where the confusion is. I meant that for any subgraph $S$, we have a fixed set of $\Theta^{(i)}$, which only depends on $S$, no matter what $G$ is. Here I am not interested in the number of possible walks from $u$ to $v$. Instead I am interested in a specific subgraph that takes the form $\{(1,2), (2,3), (3,4), (4,2)\}$ (up to relabeling of the vertices). (In this example, it is a "triangle plus one edge".) Thanks for the clarification. I have revised the question accordingly. | |
| Mar 9, 2019 at 20:37 | comment | added | David Roberson | Sorry I mistook the starting index in the sum, though I think it shouldn't make much difference. If $\Theta^{(1)}$ is any matrix such that $\langle \Theta^{(1)},A\rangle \ne 0$, then one can obtain $\langle \Theta^{(1)},A\rangle = s$ by rescaling. So maybe I am still missing something. You say you are interested in the # of paths, but that you allow repeated vertices. Do you also allow repeated edges? If so, then these are usually called walks and the # of walks of length $k$ from vertex $u$ to $v$ is just $(A^k)_{uv}$. So the total # of walks of length $k$ is the sum of the entries of $A^k$. | |
| Mar 9, 2019 at 7:56 | history | edited | Minkov | CC BY-SA 4.0 |
added 46 characters in body
|
| Mar 9, 2019 at 7:55 | comment | added | Minkov | @DavidRoberson Thanks for pointing out. The choice of $\Theta^{(i)}$ will depend on $S$ and $G$. I am trying to prove the existence of such representation. Here the summation starts from $i = 1$, which should rule out the trivial case. I am trying to connect the moment of graphon [1] with the polynomial of adjacency matrix or the number of paths on the graph. ([1] Moments of Two-Variable Functions and the Uniqueness of Graph Limits Christian Borgs, Jennifer Chayes, Laszlo Lovasz) | |
| Mar 8, 2019 at 11:29 | comment | added | David Roberson | It is not completely clear to me what you are asking. What is the freedom in choosing the $\Theta^{(i)}$? If I am allowed to pick them after knowing both $G$ and $S$, then the statement is trivially true: pick $\Theta^{(0)} = (s/d)I$ and all other $\Theta^{(i)}$ equal to zero. But of course they should depend on $S$, and also on $G$ (since at the very least the $\Theta^{(i)}$ should be $d \times d$ matrices, and $d$ depends on $G$). I assume I am just not understanding something though. Perhaps you could clarify? Out of curiosity, what is this related to? | |
| Mar 7, 2019 at 17:34 | history | edited | Minkov | CC BY-SA 4.0 |
added 5 characters in body
|
| Mar 7, 2019 at 2:21 | history | edited | Minkov | CC BY-SA 4.0 |
added 66 characters in body
|
| Mar 7, 2019 at 1:57 | history | edited | Minkov | CC BY-SA 4.0 |
added 89 characters in body
|
| Mar 7, 2019 at 1:47 | history | asked | Minkov | CC BY-SA 4.0 |