TY - JOUR
T1 - Unavoidable order-size pairs in hypergraphs — positive forcing density
AU - Axenovich, Maria
AU - Balogh, József
AU - Clemen, Felix Christian
AU - Weber, Lea
N1 - Publisher Copyright:
© The authors.
PY - 2023
Y1 - 2023
N2 - 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 (Formula presented). 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.
AB - 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 (Formula presented). 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.
KW - Induced hypergraphs
KW - forcing density
UR - http://www.scopus.com/inward/record.url?scp=85180671091&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85180671091&partnerID=8YFLogxK
U2 - 10.5070/C63362798
DO - 10.5070/C63362798
M3 - Article
AN - SCOPUS:85180671091
SN - 2766-1334
VL - 3
JO - Combinatorial Theory
JF - Combinatorial Theory
IS - 3
M1 - 15
ER -