|
2 | Fixed typesetting | ||
|
In a graph $G=(V,E)$ of order $n$, what fraction of the $binom(n,4)$ \binom{n}{4}$ $4$-subsets of $V$ can induced induce the path of order four? I looked at this question a 30 years ago and was never able to come up with a respectable upper bound. The question has reared it's its head again. The answer appears to be somewhere between $1/4$ and $1/3$, though that upper bound is almost certainly weak. Ideas? |
||||
|
|
1 |
|
||
Induced Paths of Order 4In a graph $G=(V,E)$ of order $n$, what fraction of the $binom(n,4)$ $4$-subsets of $V$ can induced the path of order four? I looked at this question a 30 years ago and was never able to come up with a respectable upper bound. The question has reared it's head again. The answer appears to be somewhere between $1/4$ and $1/3$, though that upper bound is almost certainly weak. Ideas?
|
||||
