On the maximum $F$-free induced subgraphs in $K_t$-free graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916448015745024 |
|---|---|
| author | Balogh, József Chen, Ce Luo, Haoran |
| author_facet | Balogh, József Chen, Ce Luo, Haoran |
| contents | For graphs $F$ and $H$, let $f_{F,H}(n)$ be the minimum possible size of a maximum $F$-free induced subgraph in an $n$-vertex $H$-free graph. This notion generalizes the Ramsey function and the Erdős--Rogers function. Establishing a container lemma for the $F$-free subgraphs, we give a general upper bound on $f_{F,H}(n)$, assuming the existence of certain locally dense $H$-free graphs. In particular, we prove that for every graph $F$ with $\mathrm{ex}(m,F) = O(m^{1+α})$, where $α\in [0,1/2)$, we have
\[
f_{F, K_3}(n) = O\left(n^{\frac{1}{2-α}}\left(\log n\right)^{\frac{3}{2-
α}}\right)
\quad
\textrm{and}
\quad
f_{F, K_4}(n) = O\left(n^{\frac{1}{3-2α}}\left(\log n\right)^{\frac{6}{3-2α}}\right).
\] For the cases where $F$ is a complete multipartite graph, letting $s = \sum_{i=1}^r s_i$, we prove that
\[
f_{K_{s_1,\ldots,s_r}, K_{r+2}}(n) = O \left( n^{\frac{2s -3}{4s -5}} (\log n)^{3} \right).
\]
We also make an observation which improves the bounds of $\mathrm{ex}(G(n,p),C_4)$ by a polylogarithmic factor. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_13780 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the maximum $F$-free induced subgraphs in $K_t$-free graphs Balogh, József Chen, Ce Luo, Haoran Combinatorics 05D10 05C55 05C35 05C80 For graphs $F$ and $H$, let $f_{F,H}(n)$ be the minimum possible size of a maximum $F$-free induced subgraph in an $n$-vertex $H$-free graph. This notion generalizes the Ramsey function and the Erdős--Rogers function. Establishing a container lemma for the $F$-free subgraphs, we give a general upper bound on $f_{F,H}(n)$, assuming the existence of certain locally dense $H$-free graphs. In particular, we prove that for every graph $F$ with $\mathrm{ex}(m,F) = O(m^{1+α})$, where $α\in [0,1/2)$, we have \[ f_{F, K_3}(n) = O\left(n^{\frac{1}{2-α}}\left(\log n\right)^{\frac{3}{2- α}}\right) \quad \textrm{and} \quad f_{F, K_4}(n) = O\left(n^{\frac{1}{3-2α}}\left(\log n\right)^{\frac{6}{3-2α}}\right). \] For the cases where $F$ is a complete multipartite graph, letting $s = \sum_{i=1}^r s_i$, we prove that \[ f_{K_{s_1,\ldots,s_r}, K_{r+2}}(n) = O \left( n^{\frac{2s -3}{4s -5}} (\log n)^{3} \right). \] We also make an observation which improves the bounds of $\mathrm{ex}(G(n,p),C_4)$ by a polylogarithmic factor. |
| title | On the maximum $F$-free induced subgraphs in $K_t$-free graphs |
| topic | Combinatorics 05D10 05C55 05C35 05C80 |
| url | https://arxiv.org/abs/2406.13780 |