Description
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