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)→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 σr(m,f)=lim supn→∞|{e:(n,e)→r(m,f)}|(nr). 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≥3 apart from the trivial ones (m,0) and (m,(mr)). 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
Cookie SettingseScholarship uses cookies to ensure you have the best experience on our website. You can manage which cookies you want us to use.Our Privacy Statement includes more details on the cookies we use and how we protect your privacy.