Skip to main content
Notice removed Draw attention by CommunityBot
Bounty Ended with Luca Trevisan's answer chosen by CommunityBot
Notice added Draw attention by Bart Jansen
Bounty Started worth 50 reputation by Bart Jansen
Tweeted twitter.com/#!/StackCSTheory/status/497461188570411009
added 3 characters in body
Source Link
Bart Jansen
  • 5.3k
  • 22
  • 39

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 longlarge induced pathstrees. In fact, any maximal induced pathtree is longlarge 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.

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 long induced paths. In fact, any maximal induced path is long 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.

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.

Source Link
Bart Jansen
  • 5.3k
  • 22
  • 39

Existence of long induced paths in expander graphs

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 long induced paths. In fact, any maximal induced path is long 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.