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 solve the problem completely 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. Several variants are considered and the paper ends with a collection of open problems.Keywordsextremal problemsperfect 1-factorizationinduced subgraphsthe regularity lemmaMSC codes05C3505C5105C7094B25