The Graph-codes

Summary: In this paper, 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 a prescribed condition. The problem is completely solved 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 explore local conditions that can be certified by looking at only a subset of the vertex set. Various variants are considered and the paper concludes with a collection of open problems.

Summary: Ellis, Filmus, and Friedgut proved a conjecture and proposed new conjectures regarding triangle-intersecting families and certain cross-intersecting and Kt-intersecting families. They also established a stability result.