The inducibility of small oriented graphs

Abstract

We use Razborov's flag algebra method to show an asymptotic upper bound for the maximal induced density $i({\vec{P}}_3)$ of the orgraph ${\vec{P}}_3$ in an arbitrary orgraph. A conjecture of Thomassé states that $i({\vec{P}}_3)=2/5$. The hitherto best known upper bound $i({\vec{P}}_3)\le 12/25$ was given by Bondy. We can show that $i({\vec{P}}_3)\le 0.4446$. Further, we consider such a maximal density for some other small orgraphs. With easy arguments one can see that $i({\vec{C}}_3)=1/4$, $i({\vec{K}}_2\cup {\vec{E}}_1)=3/4$ and $2/21\le i({\vec{C}}_4)$. We show that $i({\vec{C}}_4)\le 0.1104$ and conjecture that the extremal orgraphs of ${\vec{P}}_3$ and ${\vec{C}}_4$ are the same. Furthermore we show that $6-4\sqrt{2}\le i({\vec{K}}_{1,2})\le 0.4644$.

arXiv commentarXiv admin note: substantial text overlap with arXiv:1106.1030. To make this paper self contained the section, where flag-algebras are defined, is very similar to the flag-algebra-defining section in my other paper "On the minimal monochromatic K_4-density". That is why there is an overlap

Cited by in corpus (6)

• Maximum density of an induced 5-cycle is achieved by an iterated blow-up of a 5-cycle
• Minimum number of monotone subsequences of length 4 in permutations
• Rainbow triangles in three-colored graphs
• Polynomial to exponential transition in Ramsey theory
• On the inducibility of small trees
• Inducibility of d-ary trees