Structured Codes of Graphs

Alon, Noga and Gujgiczer, Anna and Körner, János and Milojević, Aleksa and Simonyi, Gábor (2023) Structured Codes of Graphs. SIAM JOURNAL ON DISCRETE MATHEMATICS, 37 (1). pp. 379-403. ISSN 0895-4801

Preview

Text 22m1487989.pdf Available under License Creative Commons Attribution. Download (590kB) | Preview

Abstract

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.

Actions (login required)

Edit Item