most recent 30 from http://mathoverflow.net 2013-06-20T01:59:48Z http://mathoverflow.net/feeds/question/90953 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/90953/induced-paths-of-order-4 geoffreyexoo 2012-03-12T00:32:21Z 2012-03-12T20:47:16Z

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

http://mathoverflow.net/questions/90953/induced-paths-of-order-4/91019#91019 Sergey Norin 2012-03-12T20:47:16Z 2012-03-12T20:47:16Z

<p>The question appears to be difficult. The best lower bound that I am aware of is still the one provided by the question author in 1986:</p> <p>$$\frac{960}{4877}\binom{n}{4}\sim 0.19684\binom{n}{4}.$$</p> <p>An upper bound is referred to in the paper ``<a href="http://arxiv.org/abs/1109.1592" rel="nofollow">The Inducibility of Graphs on Four Vertices</a>" by James Hirst. It is </p> <p>$$\sim 0.2064 \left( \binom{n}{4} + o(n^4)\right).$$</p> <p>The bound is obtained via semi-definite programming using the flag algebra technique. This method was introduced by Razborov in 2007 and it can be used to automatically produce upper bounds on asymptotic number of induced configurations in graphs and hypergraphs. These bounds are occasionally tight. In particular, James Hirst in the paper linked above deduces asymptotically tight upper bounds on the number of induced subgraphs on $4$ vertices of any fixed type, <em>except</em> for the $4$ vertex path.</p>