The Impact of connectivity constraint on the extremal number of trees

Description of video

Date: 5/11/23
Speaker :Salia Nika


    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 n(k2)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/4ok(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+ok(1))nk.

    Joint work with Suyun Jiang and Hong Liu.