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.

up vote 10 down vote accepted
+50

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

  • 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 – Luca Trevisan Aug 11 '14 at 19:38

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.