If the diameter of a bounded degree, directed graph is polynomial in the degree of the graph, is the mixing time also polynomial?

Question

Given a directed graph $G=(V,E)$, with no self-loops, with a vertex that has a maximal out-degree $\le d\in O(\log |V|)$, and with a diameter $\text{diam}(G)\in O(\text{poly }d)$, consider converting the adjacency matrix of $G$ into a lazyish, doubly-stochastic transition matrix, with the following transition probabilities:

• $\forall x\in V,\:p(x,x)=1-\frac{\text{deg} (x)}{d}$
• $\forall (x,y)\in E,\:p(x,y)= \frac{1}{d}$

where $\text{deg} (x)$ is the out-degree of vertex $x$.

We thus have

• $\forall x\in V,\sum p(x,y_i)=1$

We also require

• $\forall y\in V,\sum p(x_i,y)=1$

We are also given that the transition matrix is not periodic.

Can we say that it is always the case that the mixing time $T_{mix}(G)$ of a random walk on $G$ is also polynomial in $d$?

Much as a random walk on a Cayley graph of a group is doubly-stochastic, I'm picturing a Markov chain acting on a rather big, discrete graph that's not a-priori given by a regular graph. However, by adding enough laziness, the Markov chain may be set up so that it's also doubly-stochastic, as a permutation of the state space. If we then bound the diameter of the graph, does that help to bound the mixing time of the graph?

I think Nachmias and Peres show that, in general for an Erdos–Renyi random graph, if the walk were lazy (i.e. $p(x,x)=\frac{1}{2}$ and $p(x,y)=\frac{1}{2\text{ deg}(x)}$), then $T_{mix}(G)$ is of order $\text{diam}(G)^3$.

However, if $G$ wasn't an Erdos-Renyi random graph but merely had bounded degree, there might be some bottlenecks that can't be excluded.

(Forgive me if this obvious, or if my terminology is not correct, or if I have too many errors in my question. I'll delete if there are too many errors.)

Answer 1

If your graph is too close to bipartite, that could greatly increase the mixing time. If you make the walk more lazy, a general upper bound on the order of the mixing time is the diameter times the number of edges. See Chapter 10 in [1]. But the answer to your question is negative. Let $G$ be a random connected graph on $n$ nodes and $n\log(n)$ edges. Connect two copies of $G$ by a path of length $\log(n)$. Then the resulting graph $H$ has maximal degree and diameter of order $\log(n)$ but the mixing time is of order $n\log^2(n)$.

[1] Levin, David A., and Yuval Peres. Markov chains and mixing times. Vol. 107. American Mathematical Soc., 2017.