Consider a minimally connected graph (i.e., a spanning tree) on $n$ nodes, $\mathcal{T}=(\mathcal{V},\mathcal{E}_{\tau})$,

and its complement $\overline{\mathcal{T}}=(\mathcal{V},\overline{\mathcal{E}}_{\tau})$.

That is, $\mathcal{T} \cup \overline{\mathcal{T}} = K_n$, the complete graph on $n$ nodes.

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.

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$.

More generally, what is the probability that $|\cap_{i=1}^p c(e_i)|=k$ for $e_i \in \overline{\mathcal{E}}_{\tau}$.

I hope the statement of this problem is clear.

I have begun thinking about this, but have been stuck. Here is what I have.

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}$.

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.

Also, the element $[T^TT]_{ii}$ is the length of the cycle formed from
$e_i \in \overline{\mathcal{E}}_{\tau}$,

and $[T^TT]_{ij}$ is the number of edges two cycles share (with a plus/minus sign in there).

Furthermore, there are a total of $(n/2)(n-1)-(n-1)$ possible cycles to form.

I am not very good at combinatorics and am having problems putting the pieces together. Thanks in advance!

  • 2
    $\begingroup$ Simple observation: the answer depends on the choice of the spanning tree. If the spanning tree consists of edges $[1,i]$ for $i=2,3,\ldots, n$ then the probabilities you want to compute are non-zero only for $k=0,1$. If the spanning tree consists of edges $[1,2], [2,3], \ldots, [n-2,n-1]$, then you get non-zero probabilities for all $k<n-1$. So what kind of answer would you like to get? $\endgroup$ – Łukasz Grabowski Dec 2 '11 at 22:46
  • 1
    $\begingroup$ What is your probability space? Are you considering random tree or a fixed tree? Of course the answer depends very much on the tree structure. $\endgroup$ – Brendan McKay Dec 2 '11 at 23:18
  • $\begingroup$ thanks for the replies. I agree, the solution is dependent on the choice of tree. I am wondering, however, how to find these probabilities if the tree is given and known in the problem. Furthermore, the matrix $T$ is also known. Maybe a better question is given the tree, if I select two edges from $\overline{\mathcal{E}_{\tau}}$ (say uniformly at random) , what is the expected number of edges they share. $\endgroup$ – dan Dec 3 '11 at 9:01

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.

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$].

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.)


disclaimer: Please cast a careful eye over the definition of $L(k)$. I hope you can salvage enough from this to answer your question.

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

$$ f((v_0,\ldots,v_{k-1}) ) = (v_0,v_{k-1}) $$

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

$$|c(f(a)) \cap c(f(b))| \geq k$$

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$.

Hence the number of edges which share a path of length $\geq k$ is

$$ L(k) = \sum_{p \in \mathcal P, |p| = k-1} C^{|C(p)|}_2 $$

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

$$ \sum_{k=1}^{l-1} k * \frac{L(k) - L(k+1)}{(n/2)(n-1) - (n-1)}$$

  • $\begingroup$ thanks Daniel...yes, I am not entirely sure about $L(k)$. What is $C_2$? $\endgroup$ – dan Dec 4 '11 at 8:50
  • $\begingroup$ I mean "the number of ways $2$ objects can be chosen from $|C(p)|$". $\endgroup$ – Daniel Mansfield Dec 4 '11 at 23:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.