Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2303.10400 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911779821453312 |
|---|---|
| author | Jiang, Suyun Liu, Hong Salia, Nika |
| author_facet | Jiang, Suyun Liu, Hong Salia, Nika |
| contents | The Erdős-Sós conjecture states that the maximum number of edges in an $n$-vertex graph without a given $k$-vertex tree is at most $\frac {n(k-2)}{2}$. Despite significant interest, the conjecture remains unsolved. Recently, Caro, Patkós, and Tuza considered this problem for host graphs that are connected. Settling a problem posed by them, for a $k$-vertex tree $T$, we construct $n$-vertex connected graphs that are $T$-free with at least $(1/4-o_k(1))nk$ edges, showing that the additional connectivity condition can reduce the maximum size by at most a factor of 2. Furthermore, we show that this is optimal: there is a family of $k$-vertex brooms $T$ such that the maximum size of an $n$-vertex connected $T$-free graph is at most $(1/4+o_k(1))nk$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_10400 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | How connectivity affects the extremal number of trees Jiang, Suyun Liu, Hong Salia, Nika Combinatorics 05C05, 05C35 The Erdős-Sós conjecture states that the maximum number of edges in an $n$-vertex graph without a given $k$-vertex tree is at most $\frac {n(k-2)}{2}$. Despite significant interest, the conjecture remains unsolved. Recently, Caro, Patkós, and Tuza considered this problem for host graphs that are connected. Settling a problem posed by them, for a $k$-vertex tree $T$, we construct $n$-vertex connected graphs that are $T$-free with at least $(1/4-o_k(1))nk$ edges, showing that the additional connectivity condition can reduce the maximum size by at most a factor of 2. Furthermore, we show that this is optimal: there is a family of $k$-vertex brooms $T$ such that the maximum size of an $n$-vertex connected $T$-free graph is at most $(1/4+o_k(1))nk$. |
| title | How connectivity affects the extremal number of trees |
| topic | Combinatorics 05C05, 05C35 |
| url | https://arxiv.org/abs/2303.10400 |