13
$\begingroup$

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?

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ I don't understand the question. By path of order $4,$ do you mean a path $v_1, v_2, v_3, v_4?$ By order $n,$ I assume "with $n$ vertices"? How does a subset induce a path, since paths are order dependent? If you mean all possible orderings of the four elements, a subset can induce 24 path (or 12, if you don't care about the direction). Note further that if $G$ is the complete graph, then by the above, every such subset DOES induce 24 (or 12) paths. So what do you mean? $\endgroup$
    – Igor Rivin
    Commented Mar 12, 2012 at 1:36
  • 2
    $\begingroup$ I interpret the question as follows: take all the 4-subsets of vertices and count as a hit each of those for which the induced graph on those 4 vertices is isomorphic to a 4-path. The complete graph has a count of 0 because every 4-subset of the vertices induces a complete graph, not a 4-path. $\endgroup$
    – Gordon Royle
    Commented Mar 12, 2012 at 2:25
  • $\begingroup$ Yes, by induced subgraph I mean the usual - you include all the edges in the original graph involving the four vertices. For a complete graph you get a count of zero. One can do better. By a path, I mean what is usually meant by a path in Graph Theory. For example, if G is the cycle of order 5, then all 5 induced subgraphs of order 4 are paths. But the maximum fraction that can induce $P_4$ in a graph of order $n$ is clearly a non-increasing function of $n$ (if $n \ge 4$, and it's bounded below, so there should be a limit. I would like to know the limit. $\endgroup$
    – user22090
    Commented Mar 12, 2012 at 2:47
  • $\begingroup$ There are results of Alon (tinyurl.com/nogapaper) and of Bollobas and Sarkar (myweb.facstaff.wwu.edu/sarkara/four.ps) on maximizing the number of copies of P_4 over graphs with a fixed number of edges. Not posting as an answer since the word "induced", and fixing the number of edges rather than of vertices, makes a pretty big difference. As a historical curiosity, this seems to be Noga Alon's first paper, according to the publication list on his web site. $\endgroup$
    – Louigi Addario-Berry
    Commented Mar 12, 2012 at 14:09

1 Answer 1

Reset to default
12
$\begingroup$

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:

$$\frac{960}{4877}\binom{n}{4}\sim 0.19684\binom{n}{4}.$$

An upper bound is referred to in the paper ``The Inducibility of Graphs on Four Vertices" by James Hirst. It is

$$\sim 0.2064 \left( \binom{n}{4} + o(n^4)\right).$$

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, except for the $4$ vertex path.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks. I was not aware of this paper. Also, it appears that an upper bound of 156/495 can be achieved using current day computers by simply checking all graphs of order 12. $\endgroup$
    – user22090
    Commented Mar 13, 2012 at 0:15

You must log in to answer this question.