Hyperstability in the Erdős-Sós Conjecture
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914955288117248 |
|---|---|
| author | Pokrovskiy, Alexey |
| author_facet | Pokrovskiy, Alexey |
| contents | A rough structure theorem is proved for graphs $G$ containing no copy of a bounded degree tree $T$: from any such $G$, one can delete $o(|G||T|)$ edges in order to get a subgraph all of whose connected components have a cover of order $3|T|$.
This theorem has the ability to turn questions about sparse $T$-free graphs (about which relatively little is known), into questions about dense $T$-free graphs (for which we have powerful techniques like regularity). There are various applications, the most notable being a proof of the Erdős-Sós Conjecture for large, bounded degree trees. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_15191 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Hyperstability in the Erdős-Sós Conjecture Pokrovskiy, Alexey Combinatorics 05C35, 05C05, 05C75, 68V20 G.2.2 A rough structure theorem is proved for graphs $G$ containing no copy of a bounded degree tree $T$: from any such $G$, one can delete $o(|G||T|)$ edges in order to get a subgraph all of whose connected components have a cover of order $3|T|$. This theorem has the ability to turn questions about sparse $T$-free graphs (about which relatively little is known), into questions about dense $T$-free graphs (for which we have powerful techniques like regularity). There are various applications, the most notable being a proof of the Erdős-Sós Conjecture for large, bounded degree trees. |
| title | Hyperstability in the Erdős-Sós Conjecture |
| topic | Combinatorics 05C35, 05C05, 05C75, 68V20 G.2.2 |
| url | https://arxiv.org/abs/2409.15191 |