Timeline for Induced Paths of Order 4
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 13, 2012 at 0:12 | vote | accept | CommunityBot | ||
| Mar 12, 2012 at 20:47 | answer | added | Sergey Norin | timeline score: 12 | |
| Mar 12, 2012 at 14:09 | comment | added | Louigi Addario-Berry | 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. | |
| Mar 12, 2012 at 13:33 | history | edited | Boris Bukh | CC BY-SA 3.0 |
Fixed typesetting
|
| Mar 12, 2012 at 2:47 | comment | added | user22090 | 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. | |
| Mar 12, 2012 at 2:25 | comment | added | Gordon Royle | 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. | |
| Mar 12, 2012 at 1:36 | comment | added | Igor Rivin | 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? | |
| Mar 12, 2012 at 0:32 | history | asked | user22090 | CC BY-SA 3.0 |