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) =\left. \limsup\limits_{n \to \infty} \frac{|\{e : (n,e) \to_r (m,f)\}|}{\binom{n}{r}} \right. .\] 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\geq 3\) apart from the trivial ones \((m, 0)\) and \((m, \binom{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