Leírás
Abstract:
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 two.
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$.
Joint work with Suyun Jiang and Hong Liu.
Zoom link: https://zoom.us/j/2961946869