expected number of overlapping edges from k cycles in a graph - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T01:48:12Z http://mathoverflow.net/feeds/question/82501 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/82501/expected-number-of-overlapping-edges-from-k-cycles-in-a-graph expected number of overlapping edges from k cycles in a graph dan 2011-12-02T18:37:33Z 2012-10-01T17:22:00Z <p>Consider a minimally connected graph (i.e., a spanning tree) on $n$ nodes, $\mathcal{T}=(\mathcal{V},\mathcal{E}_{\tau})$,</p> <p>and its complement $\overline{\mathcal{T}}=(\mathcal{V},\overline{\mathcal{E}}_{\tau})$.</p> <p>That is, $\mathcal{T} \cup \overline{\mathcal{T}} = K_n$, the complete graph on $n$ nodes.</p> <p>Consider an edge $e_i \in \overline{\mathcal{E}}_{\tau}$. Then when this edge is added to the spanning tree $\mathcal{T}$, it forms a cycle. Denote the length of this cycle as $l(e_i)$, and let $c(e_i)\subseteq \mathcal{E}_{\tau}$ be the set of edges in $\mathcal{T}$ that the cycle uses.</p> <p>I would like to determine the probability that two edges $e_i,e_j \in \overline{\mathcal{E}}_{\tau}$ when added to $\mathcal{T}$ form cycles that share $k$ edges;i.e., $|c(e_i) \cap c(e_j)|=k$.</p> <p>More generally, what is the probability that $|\cap_{i=1}^p c(e_i)|=k$ for $e_i \in \overline{\mathcal{E}}_{\tau}$.</p> <p>I hope the statement of this problem is clear. </p> <p>I have begun thinking about this, but have been stuck. Here is what I have.</p> <p>Let $E(\mathcal{T})$ and $E(\overline{\mathcal{T}})$ be the incidence matrix of $\mathcal{T}$ and $\overline{\mathcal{T}}$ respectively. Then $$T = \left(E(\mathcal{T})^TE(\mathcal{T}) \right)^{-1} E(\mathcal{T})^TE(\overline{\mathcal{T}})$$ is a matrix such that its $i$th column describes which edges in $\mathcal{T}$ are used to create a cycle with the edge $e_i \in \overline{\mathcal{E}}_{\tau}$.</p> <p>The matrix $TT^T$ then gives information about how many times edges $i$ and $j$ are used in the same cycle. That is $[TT^T]_{ij}$ is an integer number that says how many times $e_i,e_j \in \mathcal{E}_{\tau}$ are used in the same cycle. </p> <p>Also, the element $[T^TT]_{ii}$ is the length of the cycle formed from<br> $e_i \in \overline{\mathcal{E}}_{\tau}$, </p> <p>and $[T^TT]_{ij}$ is the number of edges two cycles share (with a plus/minus sign in there).</p> <p>Furthermore, there are a total of $(n/2)(n-1)-(n-1)$ possible cycles to form.</p> <p>I am not very good at combinatorics and am having problems putting the pieces together. Thanks in advance!</p> http://mathoverflow.net/questions/82501/expected-number-of-overlapping-edges-from-k-cycles-in-a-graph/82601#82601 Answer by Daniel Mansfield for expected number of overlapping edges from k cycles in a graph Daniel Mansfield 2011-12-04T07:31:50Z 2011-12-04T07:31:50Z <p><em>disclaimer: Please cast a careful eye over the definition of $L(k)$. I hope you can salvage enough from this to answer your question.</em></p> <p>Let $\mathcal P$ be the set of all paths in $\mathcal T$, and define $f: \mathcal P \mapsto \overline{\mathcal{E}_T}$ as the map </p> <p>$$f((v_0,\ldots,v_{k-1}) ) = (v_0,v_{k-1})$$</p> <p>Choose any path $p \in \mathcal P$ of length $k$. Let $C(p)$ be the set of all paths in $\mathcal T$ containing $p$. Choose two elements $a,b \in C(p)$ there are edges $f(a),f(b)$ such that </p> <p>$$|c(f(a)) \cap c(f(b))| \geq k$$</p> <p>Conversely, note that if $|c(e_i) \cap c(e_j)| \geq k$ then both $c(e_i)$ and $c(e_j)$ share a common path in $\mathcal T$ of length not less than $k$. </p> <p>Hence the number of edges which share a path of length $\geq k$ is</p> <p>$$L(k) = \sum_{p \in \mathcal P, |p| = k-1} C^{|C(p)|}_2$$</p> <p>To calculate the expected number of edges that are shared, observe that $k$ must be strictly less than the length of the longest path $l$ (Lukasz provided some examples). So $L(n-1) = \cdots = L(l) = 0$. Calculate $L(l-1), L(l-2), \ldots L(1)$. Then the expected shared number of edges is</p> <p>$$\sum_{k=1}^{l-1} k * \frac{L(k) - L(k+1)}{(n/2)(n-1) - (n-1)}$$</p> http://mathoverflow.net/questions/82501/expected-number-of-overlapping-edges-from-k-cycles-in-a-graph/82649#82649 Answer by Łukasz Grabowski for expected number of overlapping edges from k cycles in a graph Łukasz Grabowski 2011-12-04T21:04:41Z 2011-12-04T21:04:41Z <p>For simplicity of notation assume that the tree is $3$-regular (apart from the boundary) and that in your question we assume that we are interested only in those pairs of edges whose ends are all different. </p> <p>Let $a$ and $b$ be two vertices in $\mathcal T$, not in the boundary. Let $p$ be the path joining them. Taking $p$ out leaves $4$ connected components. Denote $\mathcal T_a^1, \mathcal T_a^2$ the connected comopnents which touch the vertex $a$ and similarly for $b$. Then the number of pairs of edges such that their cycles intersect each other precisely in $p$ is $$F(p):=(|\mathcal T_a^1|\cdot |\mathcal T_b^1|\cdot|\mathcal T_a^2|\cdot |\mathcal T_b^2|)^2,$$ because either [the first edge has ends in $\mathcal T_a^1$ and $\mathcal T_b^1$ and the second edge has ends in $\mathcal T_a^2$ and $\mathcal T_b^2$] or [the first edge has ends in $\mathcal T_a^1$ and $\mathcal T_b^2$ and the second edge has ends in $\mathcal T_a^2$ and $\mathcal T_b^1$].</p> <p>So to get the probability that the intersection is of length exactly $k$, you need to sum-up $F(p)$ over all paths $p$ of length $k$ which don't touch the boundary, and divide it by the number of all pairs of edges which is $\frac{1}{8}\cdot n(n-1)(n-2)(n-3)$ (because we assume the edges have disjoint ends.)</p>