Combinatorial Theory

Erdős, Füredi, Rothschild and Sós initiated a study of classes of graphs that forbid every induced subgraph on a given number $m$ of vertices and number $f$ of edges. Extending their notation to $r$-graphs, we write $(n,e){\to }_r(m,f)$ if every $r$-graph $G$ on $n$ vertices with $e$ edges has an induced subgraph on $m$ vertices and $f$ edges. The forcing density of a pair $(m,f)$ is $${\sigma }_r(m,f)=\underset{n\to \mathrm{\infty }}{lim sup}\frac{|\{e:(n,e){\to }_r(m,f)\}|}{(\genfrac{}{}{0ex}{}{n}{r})}.$$ In the graph setting it is known that there are infinitely many pairs $(m,f)$ with positive forcing density. Weber asked if there is a pair of positive forcing density for $r\ge 3$ apart from the trivial ones $(m,0)$ and $(m,(\genfrac{}{}{0ex}{}{m}{r}))$. Answering her question, we show that $(6,10)$ is such a pair for $r=3$ and conjecture that it is the unique such pair. Further, we find necessary conditions for a pair to have positive forcing density, supporting this conjecture.

Mathematics Subject Classifications: 05C35, 05C65

Keywords: Induced hypergraphs, forcing density