Structured Codes of Graphs
| Autor: | Alon, Noga, Gujgiczer, Anna, Körner, János, Milojević, Aleksa, Simonyi, Gábor |
|---|---|
| Rok vydání: | 2022 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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. Comment: The paper is significantly revised: there are more authors, more results, in particular, some of the open problems of the earlier version are solved, and even the title has been changed. 29 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|