Simonyi Gábor: Structured Codes of Graphs

Description of video

Date: 4/21/22
Speaker :Simonyi Gábor


    We investigate the maximum size of graph families on a common
    vertex set of cardinality n such that the symmetric difference of the
    edge sets of any two members of the family satisfies some prescribed
    condition. We determine this maximum size for infinitely many values of
    n when the prescribed condition is connectivity or 2-connectivity,
    Hamiltonicity or the containment of a spanning star. We also investigate
    local conditions that can be certified by looking at only a subset of
    the vertex set. In these cases a capacity-type asymptotic invariant is
    defined and when the condition is to contain a certain subgraph this
    invariant is shown to be a simple function of the chromatic number of
    this required subgraph. This is proven using classical results from
    extremal graph theory.

    Joint work with Noga Alon, Anna Gujgiczer, János Körner and Aleksa