Generalized Erdős-Rogers problems for hypergraphs

2025/04/04 by He, Xiaoyu, Nie, Jiaxi
#05C65 #05D10 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2504.03138

Abstract

Given r-uniform hypergraphs G and F and an integer n, let f_F,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 f_F,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 f_F,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.

Related

• Induced subgraphs of K_r-free graphs and the Erdős--Rogers problem
• Erdős-Rogers functions for arbitrary pairs of graphs
• On the maximum F-free induced subgraphs in K_t-free graphs
• Hypergraph Erdős--Rogers functions with consecutive clique sizes
• Induced subgraphs with many repeated degrees