Improved bounds on chain saturation

Description of video

Date: 11/30/23
Speaker :Martin Ryan

Keywords

    Let sat(n,k) denote the minimum size of a family in
    the Boolean lattice of dimension n with the property that there is
    no chain with k+1 elements but the addition of one more element to
    the family produces such a chain. It is well known that for n
    sufficiently large, sat(n,k) is the same value, which we
    denote sat(k).

    For k6, the best known bounds are

    2k/21sat(k,n)2(10.023)k,


    due to Gerbner, Keszegh, Lemons, Palmer, P\'alv\"olgyi, and Patk\'os
    and to Morrison, Noel and Scott (based on a construction by Gerbner,
    et al.), respectively.

    We improve both bounds to

    2(k3)/2+(1/2)log2(k1)sat(k,n)2(10.049)k.


    The upper bound works for k7 and the lower bound for k483.

    This is joint work with Nick Veldt, Iowa State University.

     

    Downloads