1
$\begingroup$

Question

Let $G=\left(V,E\right)$ be a directed graph such that all $v\in V$ have outdegree exactly 1. Let $\alpha \in \left[ 0,1\right)$. Denote by $P\left(v\right)$ the set of all paths ending at vertex $v$.

Does $\sum_{p\in P\left( v\right)}{\alpha^{\left|p\right|}}$ converge for all $D,\alpha$ and for any $v\in V$? If not, what can we say about $\alpha$s for which this series converges?

Observations so far

Firstly, $P\left(v\right)$ is infinite iff $v$ participates in a cycle in $G$, so it suffices to examine only such $v$'s, though I'm not sure if that helps.

To simplify the series, we can notice that $$\sum_{p\in P\left( v\right)}{\alpha^{\left|p\right|}} = \sum_{n=1}^{\infty}{\left| P\left(v\right)\cap V^n \right|\alpha^n}$$ so if $\left| P\left(v\right)\cap V^n \right|$ grows slow enough (or is even bounded) the series will indeed converge, or in other words we wish to prove some notion of sparsity of $P\left(v\right)$ in $V^\ast$. For this, we need to make some combinatorial observation about the number of possible paths given that the outdegree is exactly one, which is where I am stuck (if the claim is indeed true).

Motivation

I am reading a paper about voting in social networks and am trying to determine whether the voting score in a transitive proxy voting system with exponential damping is necessarily finite, as defined in section 3.1. This is not explicitly stated in the paper.

$\endgroup$
0
$\begingroup$

For $u,v \in V$, define $u \sim v$ if there is a cycle containing both $u$ and $v$. Then $G/\sim$ is a directed graph without cycles. There can be only a finite number of paths in such a graph. Let $m(v) = \left|P_{G/\sim}([v])\right|$ be the number of paths that end in $[v]$.

Now consider a path $p \in P(v)$, where $v$ is part of a cycle $C$. $p = p_1 + p_2$, where $p_1$ is the part of $p$ that leads up to $C$, ending in the first node of $p$ which lies in $C$, $p_2$ starts at the same node and consists of the rest of $p$, and $+$ is the obvious joining.

$p_1$ cannot visit any other cycle, since once it visited one, it could never escape. Therefore $p_1$ translates directly to a path in $G/\sim$. Hence there are at most $m(v)$ choices for $p_1$.

Since $p_2$ is a path in $C$ and ends in $v$, for each natural number $n$, there is a unique $p_2$ with $|p_2| = n$.

Thus for each natural number $n$, there is only one possible choice for $|p_2| = n$, and at most $m(v)$ possible choices for $p_1$. So there are most $m(v)$ choices for $p$, with $n = |p_2| \le |p|$ and therefore $\alpha^{|p|} \le \alpha^n$. Hence $$\sum_{p \in P(v)} \alpha^{|p|} \le \sum_{n=0}^\infty m(v)\alpha^n = m(v) \sum_{n=0}^\infty \alpha^n = \frac {m(v)}{1-\alpha} < \infty$$

$\endgroup$
4
  • $\begingroup$ Just to be sure, $G / \sim$ is the condensation of $G$? If $v$ has a loop, wouldn't that loop also appear in $G / \sim$ making it cyclic? Although this is not a problem since in such case $v$ is a sink so the number of paths of length $n$ leading to it is constant for large enough $n$. $\endgroup$ – 8l2s Nov 29 '17 at 12:59
  • $\begingroup$ Also, what do you mean by "there are at most $m\left( v\right)$ choices for $p_1$? When $p$ is fixed, then so is $p_1$. Similarly, what do you mean by "there is a unique $p_2$ with $\left| p_2 \right| = n$"? $\endgroup$ – 8l2s Nov 29 '17 at 12:59
  • $\begingroup$ $G/\sim$ is the graph $G$ modulo the equivalence relation $~$. $[v]$ is the set of all nodes equivalent to $v$ in $G$, which is a single node in $G/\sim$. If $u \sim v$, then any edge $u \to v$ is dropped. If $u \nsim v$, then an edge $(u \to v)$ in $G$ becomes an edge $[u]\to [v]$ in $G/\sim$. If $v$ is in a cycle, then $[v]$ is the entire cycle (the nodes). Otherwise $[v] = \{v\}$. So modding by $\sim$ converts all cycles to single nodes. And as there is no way to leave a cycle, cycles become sinks in $G/\sim$. $\endgroup$ – Paul Sinclair Nov 29 '17 at 17:53
  • 1
    $\begingroup$ I am trying to convey that any $p$ is composed of $p_1$ leading up to $C$ and $p_2$ within $C$. The idea is then to use the $p_1$ and $p_2$ components to classify all the possible $p$. And you can check it yourself: For any natural number $n$, there is exactly one path in $C$ ending in $v$ and having length $n$. Since any path leading up to $C$ corresponds 1-1 to a path ending in $[v]$ in $G/\sim$, there are at most $m(v)$ possible paths leading up to $C$. $\endgroup$ – Paul Sinclair Nov 29 '17 at 18:02

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.