2022/08/13 by Maria Axenovich, Axenovich, Maria, József Balogh +5
Computer Science · Mathematics · #Advanced Graph Theory Research #Limits and Structures in Graph Theory #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2208.06626
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) =. \limsupn → ∞ \frac|\e : (n,e) →r (m,f)\|\binomnr . . 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, \binommr). 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.