Simonyi Gábor: Structured Codes of Graphs

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
Milojević.