# Equalizing Geometric means of Graph Cycles

Consider a strongly connected directed graph $G$. I have been stuck on the following question: can you assign real numbers in $[0,1]$ to each edge of $G$ so that the geometric mean of all cycles are equal? Also, I would like all outgoing edges to sum to 1.

For example, $p=\varphi^{-2}$ is a solution for the graph shown below, where $\varphi$ is the Golden ratio.

The geometric means for the two cycles are $(p\cdot1)^{1/2}=\varphi^{-1}$ and $(1-p)=(1-\varphi^{-2})=\varphi^{-1}$. The appearance of the Golden ratio here can be explained by observing the relation to sequences with no consecutive 1's (the number of such sequences of length $n$ is approximately $\varphi^n$).

Even though the number of constraints is much larger than the number of variables, I have not been able to construct a counterexample and I also don't know of a simple/direct proof of existence (I am aware of a purported indirect proof that exploits the ergodicity of the Markov chain - I would like to generalize this). I came across this question in my study of Markov chains. I have tried many numerical examples, and such a solution always exists (and is unique in my experience).

Any ideas, hints or references would be greatly appreciated!

• Both Math.SE and mathoverflow have a policy about cross-posting (you can perhaps post the link from Math.SE). Nov 25, 2015 at 20:26
• @Aravind Should I just include the link in the above question?
– sai
Nov 25, 2015 at 20:27
• I guess so, you could state that you did not find an answer on Math.SE. Nov 25, 2015 at 20:27

I am not 100% sure I am not misusing the Perron-Frobenius Theorem, but I think that it justifies all the assumptions I am going to make in the following. The final construction itself is very simple.

Let $V$ denote the vertex set of the underlying graph and let $A$ be the adjacency matrix, that is $A_{v,w} = 1$ if $v \to w$ and otherwise $A_{v,w} = 0$. This matrix is non-negative and irreducible, because the graph was strongly connected. Hence there is a positive eigenvalue $\lambda$ together with a right-eigenvector $c$ all of whose entries are positive. Moreover, for every $v \in V$ we have $(Ac)_v = \lambda c_v$, that is: $$\sum_{w \colon v \to w} c_w = \lambda c_v.$$ So in particular (as all entries are positive) we have that for every directed edge $v \to w$, the value $p(v \to w) := \frac{c_w}{\lambda c_v}$ is well-defined and lies in the interval $(0, 1]$.

With this definition, we have for every vertex $v \in V$ $$\sum_{w \colon v\to w} p(v \to w) = \frac{1}{\lambda c_v}(Ac)_v = 1.$$ Along every directed cycle, all the terms $\frac{c_v}{c_w}$ cancel out, and the accumulating power of $\lambda^{-1}$ is taken care of by definition of the geometric mean; hence every cycle has geometric mean $\lambda^{-1}$.

• Yes, thank you! I was playing around with the spectrum of the adjacency matrix before, but could not tease this out.
– sai
Nov 26, 2015 at 23:23
• As a combinatorial aside, since the above assignment of edge probabilities makes the probability of every sequence $(X_1,\ldots,X_n)$ approximately $\lambda^{-n}$, the number of sequences that satisfy the graph constraints must grow as $\lambda^n$ (up to constant factors).
– sai
Nov 26, 2015 at 23:25
• I'm sorry, I don't quite follow - what kind of sequences do you mean and which "graph constraints"? Nov 27, 2015 at 8:53
• Sorry, that was not clear. I am thinking of a random walker on the graph. The sequence is given by the sequence of locations of the random walker, which has constraints placed on it by the graph.
– sai
Nov 27, 2015 at 23:28