Timeline for Number of spanning forests in a graph
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 18, 2011 at 9:50 | comment | added | Gil Kalai | Dear Aaron, thanks, it is a very nice proof. (I remembered that you presented us the proof but did not remember the proof itself. When was it?) | |
| Jul 18, 2011 at 5:40 | comment | added | Aaron Meyerowitz | @Gil OK, I put it in. Private note: Maybe you heard it from me. I was in a graph theory course with Micha Perles at the time and presented it in his seminar. We did look in Moon's book. Certainly no part of the result was new, but the proof is cute. It is not the prettiest, that honor goes to Joyal's, and not the ugliest, but it is mine. (to misleadingly quote Doron Zeilberger) | |
| Jul 18, 2011 at 5:11 | history | edited | Aaron Meyerowitz | CC BY-SA 3.0 |
added 933 characters in body
|
| Jul 15, 2011 at 11:46 | comment | added | Gil Kalai | Dear Aaron, please include the easy inductive proof that you discovered. The statement itself (regarding the number of trees containing a fixed forest was probably known well before (I heard about it as an undergraduate) I would look at J W Moon's book.For example, it can be proved using the formula of labelled trees with prescribed degree sequences (which itself is easily proved by induction.) There is a beautiful proof by Pitman regarding Cayley's formula that uses counting labelled rooted forests. | |
| Jun 1, 2011 at 18:08 | history | edited | Aaron Meyerowitz | CC BY-SA 3.0 |
added 211 characters in body
|
| Jun 1, 2011 at 18:01 | comment | added | Aaron Meyerowitz | For my matrix any minor (with the correct sign chosen) gives $16+8(e_{1 2}+e_{1 3}+e_{2 3}+e_{3 4})+3( e_{1 2}e_{1 3}+e_{1 2}e_{2 3}+e_{1 3}e_{3 4}+e_{2 3}e_{3 4}) +4e_{1 2}e_{3 4}$ $+e_{1 2}e_{1 3}e_{3 4}+e_{1 2}e_{2 3}e_{3 4}+e_{1 3}e_{2 3}e_{3 4}$ | |
| Jun 1, 2011 at 17:51 | comment | added | Aaron Meyerowitz | But the 1,1 minor gives $\lambda_{2 2}\lambda_{3 3}\lambda_{4 4}$ $+e_{1 2}\lambda_{3 3}\lambda_{4 4}+e_{1 3}\lambda_{2 2}\lambda_{4 4}+e_{2 3}(\lambda_{2 2}+\lambda_{3 3})\lambda_{4 4}+e_{3 4}\lambda_{2 2}(\lambda_{3 3}+\lambda_{4 4})$ $+e_{1 2}e_{1 3}\lambda_{4 4}+e_{1 2}e_{2 3}\lambda_{4 4}+e_{1 3}e_{2 3}\lambda_{4 4}+e_{1 3}e_{3 4}\lambda_{2 2}+e_{2 3}e_{3 4}(\lambda_{2 2}+\lambda_{4 4}) +e_{1 2}e_{3 4}(\lambda_{3 3}+\lambda_{4 4})$ $+e_{1 2}e_{1 3}e_{3 4}+e_{1 2}e_{2 3}e_{3 4}+e_{1 3}e_{2 3}e_{3 4}$ which looks better. | |
| Jun 1, 2011 at 17:11 | comment | added | Aaron Meyerowitz | @Aleks I should have said $n-1$ where I said $n$, I'll correct it. When I try the graph with 4 vertices and edges 12,13,23 and 34 then your matrix with the $1,3$ minor gives $e_{1 3}\lambda_{2 2}\lambda_{4 4}+e_{1 2}e_{1 3}\lambda_{4 4}+e_{1 2}e_{2 3}\lambda_{4 4}+e_{1 3}e_{3 4}\lambda_{2 2}+e_{1 3}e_{2 3}\lambda_{4 4}+e_{1 2}e_{1 3}e_{3 4}+e_{1 2}e_{2 3}e_{3 4}+e_{1 3}e_{2 3}e_{3 4}$ so it misses the 0 edge forest, 3 of the $1$ edge spanning forests and one of the $2$ edge spanning forests. | |
| Jun 1, 2011 at 17:01 | comment | added | Aaron Meyerowitz | @Aleks I assume the referee said "100 proofs is enough!, I don't want to see another proof." In my humble opinion it is a short simple complete self contained proof. | |
| Jun 1, 2011 at 6:44 | comment | added | Aleks Vlasev | Luckily it seems that for small cases like $K_5$ and $K_6$, those extra terms either have a negative sign or they are non-linear in the edge variables or they do not have the correct number of edge variables, so I can just get rid of them. What is left is precisely what I needed. I tried the same with $n + \sum_j e_{i,j}$ and the situation is very similar. However, if I use my above definition for $A_{i,i}$ and $A_{i,j}=−e_{i,j}$, the determinant gives me precisely what I needed! My questions are, is my approach correct? Why did you have $−1−e_{i,j}$ instead of just $-e_{i,j}$? | |
| Jun 1, 2011 at 6:18 | comment | added | Aleks Vlasev | I meant $A_{i,j} =−1−e_{i,j}$ when $i \neq j$. The problems I am working on involve only graphs that are connected, have no loops, no multiedges. When I take the determinant of this matrix along the lines of what David suggested and pick off a given coefficient, say $[\lambda_1 \lambda_2 \lambda_3]$, I expect to get monomials that correspond to spanning forests that keep vertices 1,2 and 3 in different components but it seems like I get more that what I wanted. | |
| Jun 1, 2011 at 6:14 | comment | added | Aleks Vlasev | Thank you for your answer Aaron! That's a fascinating story. I just don't understand the part about the referees report. Did the referee not like the proof? As for the question at hand, I tried out what you wrote in combination with what David wrote. The matrix I used is the following $A_{i,j} = \lambda_i + \sum_{k=1,k\neq i}^n e_{i,k}$ when $i = j$ and $A_{i,j} = - 1 - e_{i,j} when $i \neq j$. | |
| Jun 1, 2011 at 3:02 | history | answered | Aaron Meyerowitz | CC BY-SA 3.0 |