Generalized Erdős-Rogers problems for hypergraphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910903339843584 |
|---|---|
| author | He, Xiaoyu Nie, Jiaxi |
| author_facet | He, Xiaoyu Nie, Jiaxi |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_03138 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Generalized Erdős-Rogers problems for hypergraphs He, Xiaoyu Nie, Jiaxi Combinatorics 05C65, 05D10 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. |
| title | Generalized Erdős-Rogers problems for hypergraphs |
| topic | Combinatorics 05C65, 05D10 |
| url | https://arxiv.org/abs/2504.03138 |