Turán H-densities for 3-graphs

is the limit [pi_{H}(mathcal{F})= lim_{n ightarrow infty}ex_{H}(n, mathcal{F})/�inom{n}{h}. ] This generalises the notions of emph{Tur'an density} (when

H

is an

r

-edge), and emph{inducibility} (when

m a t h c a l F

is empty). Although problems of this kind have received some attention, very few results are known. We use Razborov's semi-definite method to investigate Tur'an

H

-densities for 3-graphs. In particular, we show that [pi_{K_4^-}(K_4) = 16/27,] with Tur'an's construction being optimal. We prove a result in a similar flavour for

K_{5}

and make a general conjecture on the value of

p i_{K_{t}^{-}} (K_{t})

. We also establish that [pi_{4.2}(emptyset)=3/4,] where 4.2 denotes the 3-graph on 4 vertices with exactly 2 edges. The lower bound in this case comes from a random geometric construction strikingly different from previous known extremal examples in 3-graph theory. We give a number of other results and conjectures for 3-graphs, and in addition consider the inducibility of certain directed graphs. Let

v e c S_{k}

be the emph{out-star} on

k

vertices; i.e{.} the star on

k

vertices with all

k - 1

edges oriented away from the centre. We show that [pi_{vec{S}_3}(emptyset)=2sqrt3-3,] with an iterated blow-up construction being extremal. This is related to a conjecture of Mubayi and R"odl on the Tur'an density of the 3-graph

C_{5}

. We also determine

p i_{v e c S_{k}} (e m p t y s e t)

when

k = 4

, and conjecture its value for general

k

.

Review text

Summary: Given an \(r\)-graph \(H\) on \(h\) vertices, and a family \(\mathcal{F}\) of forbidden subgraphs, we define \(\mathrm{ex}_{H}(n, \mathcal{F})\) to be the maximum number of induced copies of \(H\) in an \(\mathcal{F}\)-free \(r\)-graph on \(n\) vertices. Then the Turán \(H\)-density of \(\mathcal{F}\) is the limit \[ \pi_{H}(\mathcal{F})= \lim_{n\rightarrow \infty}\text{ex}_{H}(n, \mathcal{F})/\binom{n}{h}. \] This generalises the notions of Turán density (when \(H\) is an \(r\)-edge), and inducibility (when \(\mathcal{F}\) is empty). Although problems of this kind have received some attention, very few results are known.We use Razborov's semi-definite method to investigate Turán \(H\)-densities for 3-graphs. In particular, we show that \(\pi_{K_4^-}(K_4) = 16/27,\) with Turán's construction being optimal. We prove a result in a similar flavour for \(K_5\) and make a general conjecture on the value of \(\pi_{K_t^-}(K_t)\). We also establish that \(\pi_{4.2}(\emptyset)=3/4,\) where \(4.2\) denotes the 3-graph on 4 vertices with exactly 2 edges. The lower bound in this case comes from a random geometric construction strikingly different from previous known extremal examples in 3-graph theory. We give a number of other results and conjectures for 3-graphs, and in addition consider the inducibility of certain directed graphs. Let \(\vec{S}_k\) be the out-star on \(k\) vertices; i.e. the star on \(k\) vertices with all \(k-1\) edges oriented away from the centre. We show that \(\pi_{\vec{S}_3}(\emptyset)=2\sqrt{3}-3,\) with an iterated blow-up construction being extremal. This is related to a conjecture of Mubayi and Rödl on the Turán density of the 3-graph \(C_5\). We also determine \(\pi_{\vec{S}_k}(\emptyset)\) when \(k=4,5\), and conjecture its value for general \(k\).

Recommendations

Cited in

(21)

This page was built for publication: Turán \(H\)-densities for 3-graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q456381)