This research demonstrates polynomial bounds on induced subgraphs in G-free hypergraphs, suggesting implications for broader graph theory.
Given r-uniform hypergraphs G and F and an integer n, let fF,G(n) be the maximum m such that every n-vertex G-free r-graph has an F-free induced subgraph on m vertices. We show that fF,G(n) is polynomial in n when G is a subgraph of an iterated blowup of F. As a partial converse, we show that if G is not a subgraph of an F-iterated blowup and is $2$-tightly connected, then fF,G(n) is at most polylogarithmic in n. Our bounds generalize previous results of Dudek and Mubayi for the case when F and G are complete.
No takes yet. Share an insight, caveat, or question.
He et al. (2025) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: