Turán \(H\)-densities for 3-graphs (Q456381): Difference between revisions

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\).