The inducibility of small oriented graphs

Publication date: 21 November 2011

Abstract: We use Razborov's flag algebra method to show an asymptotic upper bound for the maximal induced density

i (v e c P_{3})

of the orgraph

v e c P_{3}

in an arbitrary orgraph. A conjecture of Thomass'e states that

i (v e c P_{3}) = 2 / 5

. The hitherto best known upper bound

i (v e c P_{3}) l e q 12 / 25

was given by Bondy. We can show that

i (v e c P_{3}) l e q 0.4446

. Further, we consider such a maximal density for some other small orgraphs. With easy arguments one can see that

i (v e c C_{3}) = 1 / 4

,

i (v e c K_{2} c u p v e c E_{1}) = 3 / 4

and

2 / 21 l e q i (v e c C_{4})

. We show that

i (v e c C_{4}) l e q 0.1104

and conjecture that the extremal orgraphs of

v e c P_{3}

and

v e c C_{4}

are the same. Furthermore we show that

6 - 4 s q r t 2 l e q i (v e c K_{1, 2}) l e q 0.4644

.

This page was built for publication: The inducibility of small oriented graphs