Timeline for How to prove that for the real stable characteristic polynomial $P=\Phi_T$ of a tree $T$, $P_iP_j-PP_{ij}=(\Phi_{T-[v_i,v_j]})^2$?
Current License: CC BY-SA 4.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 8, 2020 at 19:25 | vote | accept | Chua KS | ||
| Jun 13, 2020 at 19:03 | comment | added | Chua KS | It seems that it is more interesting to use this result in reverse to give a polynomial time algorithm to find the unique path between two given vertices in a tree. If you have a say 300 vertices tree, it may not be easy to find the path between $v_i$ and $v_j$ but we can evaluate $D_{ij}$ using Gauss elimination. If we then remove all vertices from the tree corresponding to the variables that remain in $D_{ij}$, one get the unique path. | |
| Jun 11, 2020 at 22:05 | comment | added | Abdelmalek Abdesselam | I would need more details of the definition of dependence on labelling and intrinsic to understand your comment. If you use my formula for a general simple graph what you get for $\pm D_{\{i\},\{j\}}$ looks pretty intrinsic to me. You have a sum over subforests one component of which must connect $i$ and $j$ (hence the unique path in the tree case). The contribution of such a forest is a product over the other components of sum over vertices $s$ in that component of $x_s$ minus the degree of vertex $s$ in the original graph $G$. This, assuming your definition of $A$ has zeros on the diagonal. | |
| Jun 11, 2020 at 21:20 | comment | added | Chua KS | It's not possible to read off the square root from the graph as it depends on choice of labeling . The tree square root is intrinsic which is the original question, | |
| Jun 11, 2020 at 20:40 | history | edited | Abdelmalek Abdesselam | CC BY-SA 4.0 |
added 1 character in body
|
| Jun 11, 2020 at 16:44 | comment | added | Abdelmalek Abdesselam | I don't have time to do the computation in detail now, but I think using Thm 1 from my paper, this should give $D_{\{i\},\{j\}}=(-1)^{i+j}\Phi_{T-[v_jv_j]}$. | |
| Jun 11, 2020 at 16:42 | vote | accept | Chua KS | ||
| Jun 19, 2020 at 17:41 | |||||
| Jun 11, 2020 at 16:41 | comment | added | Chua KS | Yes. I discover the tree relation first by numerical computation. The graph case look more strange but is actually easier. I can deduce it now from your $D_{ij}$. Thanks. | |
| Jun 11, 2020 at 16:33 | comment | added | Abdelmalek Abdesselam | I updated my answer so you can find how to relate $D$ and $\Phi$. | |
| Jun 11, 2020 at 16:30 | history | edited | Abdelmalek Abdesselam | CC BY-SA 4.0 |
added 430 characters in body
|
| Jun 11, 2020 at 16:07 | comment | added | Abdelmalek Abdesselam | I did not address that. I found the square root for general graphs. Where did you get that the square root for trees is $\Phi_{T-[v_i,v_j]}$? In general, on MO you should give some context and references. | |
| Jun 11, 2020 at 16:04 | comment | added | Chua KS | Why is $D_{\{i\},\{j\}}=\Phi_{T-[v_i,v_j]}$ ? | |
| Jun 11, 2020 at 15:58 | comment | added | Abdelmalek Abdesselam | did you find a mistake in what I wrote? | |
| Jun 11, 2020 at 15:56 | comment | added | Chua KS | I don't quite understand. For $\Phi_{T-[v_i,v_j]}$, one has to delete all vertices on the unique path between $v_i$ and $v_j$ but your $D_{\{i\},\{j\}}$ only delete one row and one column. Also how does your argument use the fact that $T$ is a tree. It is not true if $T$ is not a tree. | |
| Jun 11, 2020 at 15:29 | history | answered | Abdelmalek Abdesselam | CC BY-SA 4.0 |