Turán \(H\)-densities for 3-graphs

Victor Falgas-Ravry¹ ; Emil R. Vaughan²

¹Institutionen för matematik och matematisk statistik, Umeå Universitet
²School of Electronic Engineering and Computer Science, Queen Mary University of London

The electronic journal of combinatorics, Tome 19 (2012) no. 3

Résumé

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}\mathrm{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$.

Détail

DOI : 10.37236/2733

Classification : 05C20, 05C42, 05C35, 05C65
Mots-clés : Turán problems, extremal hypergraph theory, flag algebras