Existence of long induced paths in expander graphs

Question

Let's say that a graph family $\mathcal{F}$ has long induced paths if there is a constant $\epsilon > 0$ such that every graph $G$ in $\mathcal{F}$ contains an induced path on $|V(G)|^{\epsilon}$ vertices. I am interested in properties of graph families that ensure the existence of long induced paths. In particular, I am currently wondering whether constant-degree expanders have long induced paths. Here is what I know.

• Random graphs with constant average degree (in the Erdős–Rényi model) have long (even linear-size) induced paths with high probability; see for example Suen's article.
• Unique-neighbor expander graphs (as defined by Alon and Copalbo) have large induced trees. In fact, any maximal induced tree is large in such graphs.

Given these two facts I would expect that contant-degree expanders have long induced paths. However, I was unable to find any concrete results. Any insights are much appreciated.

Answer 1

The answer should be positive if your bounded-degree graph has both the property of having constant expansion and $\Omega( \log n)$ girth. The argument would be: start at a vertex, then for $n^\epsilon$ steps take a walk in which each step is chosen at random among those that don't take us back to where we were the step before. (So if the graph is $d$-regular we have $d-1$ random choices at each step.)

Now I claim that, for every $i$ and $j$, if I look at steps $i$ and $j$ of the walk, the probability that there is an edge between the vertex at step $i$ and the vertex at step $j$ is $n^{-\Omega(1)}$. Then, if $\epsilon$ is chosen sufficiently small, a union bound will show that the walk will induce a path with probability $1-o(1)$.

If $|i-j|$ is less then the girth, then the probability of an edge between $i$ and $j$ is just zero. If $j> i+ \Omega(\log n)$, then the expansion of the graph should be enough to argue that the existence of the edge $(i,j)$ happens with probability $n^{-\Omega(1)}$. This is because, for a fixed start vertex $v$, the distribution of the walk after a number of steps equal to the girth is uniform over a set of size $n^{\Omega(1)}$, and so has collision probability $n^{-\Omega(1)}$; every subsequent step should only decrease the collision probability (this is true for an actual random walk, but it should also be true for this non-backtracking walk), and so the collision probability, and hence the min-entropy, of the distribution stays $n^{-\Omega(1)}$, and the probability of hitting one of the $O(1)$ neighbors of $v$ is also $n^{-\Omega(1)}$.