expected number of overlapping edges from k cycles in a graph - MathOverflow

expected number of overlapping edges from k cycles in a graph

2011-12-02T18:37:33Z

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!

Answer by Daniel Mansfield for expected number of overlapping edges from k cycles in a graph

2011-12-04T07:31:50Z

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

Answer by Łukasz Grabowski for expected number of overlapping edges from k cycles in a graph

2011-12-04T21:04:41Z

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