pith. sign in

arxiv: 2504.03138 · v1 · pith:SBVMFNMCnew · submitted 2025-04-04 · 🧮 math.CO

Generalized ErdH{o}s-Rogers problems for hypergraphs

classification 🧮 math.CO
keywords subgraphblowupfreehypergraphsiteratedwhenboundscase
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.