pith. sign in

arxiv: 1111.4813 · v2 · pith:KXQLTDCRnew · submitted 2011-11-21 · 🧮 math.CO

The inducibility of small oriented graphs

classification 🧮 math.CO
keywords boundconjecturedensitymaximalorgraphorgraphssmallupper
0
0 comments X
read the original 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\'e states that $i(\vec P_3)=2/5$. The hitherto best known upper bound $i(\vec P_3)\leq12/25$ was given by Bondy. We can show that $i(\vec P_3)\leq 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\leq i(\vec C_4)$. We show that $i(\vec C_4)\leq 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}\leq i(\vec K_{1,2})\leq 0.4644$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.