Lower bound on the number of walks of length $l$ in a graph

Question

Let $G$ be any connected simple graph, fix some positive integer $l$ and denote by $w_l(v,w)$ the number of walks of length $l$ between vertices $v$ and $w$. I am looking for a lower bound on $\min_{v,w} w_l(v,w)$. In this publication I found that there is a pair $v,w$ such that $w_l(v,w)\geq \dfrac{\bar{d}^l}{n}$ where $\bar{d}$ is the average degree in $G$ and $n$ the number of vertices in $G$. I would like to extend this to a uniform lower bound (which will be worse of course). I am particularly interested in the form of the lower bound $\dfrac{x^l}{n}$ for some $x$ to be determined. A first guess was to replace $\bar{d}$ by the minimal degree $\delta$ but I found counter examples where this was not correct.

Do you have any suggestions or literature references?

EDIT: The existence of such a $x$ is evident, since $x^l\to 0$ continuously as $x\to 0$. And we know that there is a pair $v,w$ such that $w_l(v,w)\geq \dfrac{\bar{d}^l}{n}$ but (by the averaging argument in the paper) we have $\dfrac{\bar{d}^l}{n}> \min_{v,w} w_l(v,w)>0$ as soon as there is more than one degree in $G$. Consequently, the function $f(x) = \dfrac{\bar{x}^l}{n}- \min_{v,w} w_l(v,w)$ satisfies $f(\bar{d})>0$ and $f(0) \leq 0$ and $f$ is continuous. Therefore, we have a $x_0$ such that $f(x_0)=0$. Evidently, deriving $x_0$ from this equation is like a dog chaising its own tail. So we need a $x_0'$ which is a bit smaller than $x_0$ by monotony of $f$ as $x\to 0$. Again, here I am stuck.

EDIT 3: Based on the reponse and comments by Brandon du Preez I decided to put loops on every vertex. Unfortunately, this way, we lose the result from the paper I cited because it uses spectral theoretical tools and especially the fact that the adjacency matrix has trace 0. But, let $\phi'$ be a walk of length $l$ in this new graph $G'$ (with loops) then there is a $k\in\{0,...,l-1\}$ and a walk $\phi$ in $G$ of length $l-k$ such that $\phi$ consists of all "real" steps without taking loops. I, then, only have to arrange the loops between the $l-k$ visited vertices (with multiplicities of course). Therefore, I obtain the formula for the number of walks between $v,w$ in $G'$ as

$$w_l^{G'}(v,w)=\sum_{k=0}^{l-1}\sum_{h_1+...+h_{l-k}=k}\binom{k}{h_1,...,h_{l-k}}w_{l-k}(v,w)$$

Now, I am stuck again. This is obviously greater zero for any connected graph for sufficiently large $l$ but can I get the desired estimate from it? Looks a bit like a multinomial theorem if you replace $w_l(v,w)$ by something of the form $x^l$ but not quite. Do you have any more ideas?

Answer 1

If we want a bound that works for any (presumably connected) graph $G$ and any $l$, then the best we can do is $x = 0$, since bipartite graphs will cause a headache.

To see this, note that any connected bipartite graph $G=(V,E)$ has a unique bipartition $V_1\cup V_2$, in which any walk starting and ending in $V_i$ has even length, and any walk starting in $V_i$ and ending in $V_j$ ($j\neq i$) has odd length. So you can always pick $u$ and $v$ such that $w_l(u,v) = 0$ no matter how large we choose $l$.

If we exclude bipartite graphs, then we still need to pick $l$ carefully (i.e., $l$ must be at least the diameter of $G$), because otherwise we can pick vertices $v$ and $w$ such that $d(v,w) > l$, and then there are no walks between them.

In summary, we need to exclude bipartite graphs and have a bit more information about $l$ for this to be meaningful I think.