<p>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.) </p>

<p>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)$.  </p>

<p>If $|i-j|$ is less then the girth, then the probability of an edge between $i$ and $j$ is just zero. If $j&gt; 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)}$.</p>

CC BY-SA 3.0
2014-08-11T19:38:51.880Z
Actually it seems that I am using only that the graph has girth $\Omega(\log n)$ and that every vertex has degree at least 3, and the expansion is not really coming into the argument
Luca Trevisan
CC BY-SA 3.0
2014-08-11T19:36:50.730Z
2014-08-11T19:36:50.730Z
Luca Trevisan
<p>Let's say that a graph family $\mathcal{F}$ has <em>long induced paths</em> if there is a constant $\epsilon &gt; 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.</p>

<ul>
<li>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 <a href="http://www.sciencedirect.com/science/article/pii/009589569290021O">Suen's article</a>.</li>
<li>Unique-neighbor expander graphs (as defined by <a href="http://www.cs.princeton.edu/~zdvir/expanders/Alon-Capalbo-Unique.pdf">Alon and Copalbo</a>) have large induced <em>trees</em>. In fact, any maximal induced tree is large in such graphs.</li>
</ul>

<p>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.</p>

<graph-theory><expanders>
Existence of long induced paths in expander graphs
Bart Jansen
# Existence of long induced paths in expander graphs

(Asked by: username_0 on 2014-08-07)

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](http://www.sciencedirect.com/science/article/pii/009589569290021O).
* Unique-neighbor expander graphs (as defined by [Alon and Copalbo](http://www.cs.princeton.edu/~zdvir/expanders/Alon-Capalbo-Unique.pdf)) 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.

**Tags:** graph-theory, expanders

---

## 1 answers

### Answer by username_1 on 2014-08-11. Score: 11 | Accepted answer

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)}$.

> **Comments:**
> **username_1**: Actually it seems that I am using only that the graph has girth $\Omega(\log n)$ and that every vertex has degree at least 3, and the expansion is not really coming into the argument  

---

