Exchange properties of finite set-systems

Description of video

Date: 9/23/21
Speaker :Pálvölgyi Dömötör

Keywords

    In a recent breakthrough, Adiprasito, Avvakumov, and Karasev
    constructed a triangulation of the n-dimensional real projective space
    with a subexponential number of vertices. They reduced the problem to
    finding a set-system satisfying certain properties. Denoting by f(n) the
    smallest cardinality of such a family, they proved that
    f(n)<2O(nlogn), and they asked for a nontrivial lower bound.
    We show that 2(1.42+o(1))nf(n)2(1+o(1))2nlogn for such families.

    We also study a variant of the above problem, where we prove that the
    size of the smallest family satisfying a slightly stronger condition
    lies between Ω(nlogn) and O(nloglogn/logn).
    It remains an interesting open problem to reduce this gap.

    To warm-up, you can solve this problem:
    https://www.komal.hu/feladat?a=feladat&f=A797

    Joint work with Peter Frankl and Janos Pach.

    Downloads