Number of spanning trees which contain a given edge - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T07:55:25Z http://mathoverflow.net/feeds/question/81251 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/81251/number-of-spanning-trees-which-contain-a-given-edge Number of spanning trees which contain a given edge David Harris 2011-11-18T14:28:16Z 2011-11-18T21:36:06Z <p>Suppose I have a connected graph $G$ and a fixed edge $e = \langle u, v \rangle \in G$, and I want to count the number of spanning trees that involve $e$. I really only want to estimate the fraction of spanning trees containing $e$ compared to the total number of spanning trees $G$, that is, I want to find a lower bound $c \leq \kappa(G \backslash e) / \kappa(G)$</p> <p>This lower bound should be in terms of the degrees of vertices $u,v$. Let $c(d,d')$ be the smallest possible value of $\kappa(G \backslash e) / \kappa(G)$ when the vertices have degree $d, d'$. What can one say about $c(d,d')$?</p> <p>For example, if $d = 1$ or $d' = 1$, then $c(d,d') = 1$. (The edge must be part of a spanning tree of $G$.). </p> <p>If $d = 2$, then $c(d,d') \geq 1/2$, as every spanning tree must involve one of the two edges incident on $u$, and the spanning trees using only $e$ are in bijection with the spanning trees using the other edge.</p> <p>If $d = d' = 2$, then $c(d,d') \geq 2/3$; and so on.</p> <p>Is there are general formula for $c(d,d')$?</p> http://mathoverflow.net/questions/81251/number-of-spanning-trees-which-contain-a-given-edge/81277#81277 Answer by Dimitrije Kostic for Number of spanning trees which contain a given edge Dimitrije Kostic 2011-11-18T20:22:24Z 2011-11-18T20:22:24Z <p>First of all, I think it's important to note that the number of spanning trees containing a given edge may depend on the global properties of a graph rather than just local properties like vertex degrees. For instance, if an edge is a cut-edge (also known as a bridge) then every spanning tree will contain it, but the vertex degrees won't necessarily tell you if that's the case.</p> <p>To every graph $G$ we can associate a bivarite polynomial over $\mathbb{Z}$ called the <strong>Tutte polynomial</strong> $T_G(x,y)$. Any standard text on algebraic graph theory (e.g., Norman Biggs' <em>Algebraic Graph Theory</em>; Bela Bollobas' <em>Modern Graph Theory</em>, etc) will contain a treatment of it. The Tutte polynomial encodes a really surprising amount of combinatorial information about a graph, particularly regarding its connectivity and cycle structure. Among other things:</p> <p>(1) $T_G(1,1)$ is equal to the number of spanning trees of $G$ (which is always positive, if $G$ is connected).</p> <p>(2) If $e$ is any edge of $G$, then $T_{G}(x,y) = T_{G\e}(x,y) + T_{G*e}(x,y)$. $G\e$ is, as in your notation, $G$ with $e$ excised and $G*e$ is the graph obtained by merging the two vertices of $e$ together (and keeping any loops that form). With some base conditions, this is often taken as the definition of $T_G$.</p> <p>Notice that $1 - T_{G*e}(1,1)/T_G(1,1) = T_{G-e}(1,1)/T_G(1,1)$. If I understand your problem correctly, you're interested in a choice of $e$ that minimizes the right hand side. So it might be helpful to consider maximizing the quotient on the left hand side, but both seem pretty opaque to me. Also I should warn you that Tutte polynomial computations, as you might expect, are NP-hard in general.</p> <p>Hopefully this is of some use.</p> http://mathoverflow.net/questions/81251/number-of-spanning-trees-which-contain-a-given-edge/81282#81282 Answer by Ori Gurel-Gurevich for Number of spanning trees which contain a given edge Ori Gurel-Gurevich 2011-11-18T21:06:49Z 2011-11-18T21:36:06Z <p>The probability that an edge $e=(u,v)$ is part of a uniform spanning tree is equal to the resistance between $u$ and $v$ when the graph is considered as an electric network (see the <a href="http://mypage.iu.edu/~rdlyons/prbtree/prbtree.html" rel="nofollow">book</a> by Lyons with Peres, section 4.2). The bounds you get (in term of the degrees $d_u,d_v$) are</p> <p>$$\frac{1}{\min(d_u,d_v)} \le R_{eff}(u \leftrightarrow v) \le 1$$</p> <p>when you allow multiple edges, or </p> <p>$$\frac{(d_u-1)+(d_v-1)}{(d_u-1)+(d_v-1)+(d_u-1)(d_v-1)} &lt; R_{eff}(u \leftrightarrow v) \le 1$$</p> <p>when the graph is simple, and these bounds are sharp.</p> http://mathoverflow.net/questions/81251/number-of-spanning-trees-which-contain-a-given-edge/81283#81283 Answer by Gerhard Paseman for Number of spanning trees which contain a given edge Gerhard Paseman 2011-11-18T21:10:55Z 2011-11-18T21:31:18Z <p>The assertion below regarding O(1/n) is in contradiction with another posted answer, so I leave the construction available while I check the assertion.</p> <p>Let M_n be the (graph of the Hasse diagram of the) modular lattice on (n+2) elements. This will have 2n edges. Add two more edges on either side. Call the leaves u and v, and let us add an edge (the problem edge, called e) between u and v. I have a u-v gadget with 2n+3 edges on n+4 vertices, and n-many cycles of length 5. However, u and v have degree 2.</p> <p>Now to the u side of this gadget, add an edge and then dangle whatever favorite nonempty graph off this edge, and choose a disjoint graph to dangle off of v. In this graph, u and v have degree 3. However, any spanning tree that contains e can be modified to one of at least some number of other spanning trees; the analysis is more complicated than I originally imagined, but I think one can use this to show the ratio for this edge is at most O(1/n). So if d and d' are at least 3, I see no useful lower bound for the fraction in terms of the degrees themselves regarding edge e.</p> <p>Gerhard "Ask Me About System Design" Paseman, 2011.11.18</p>