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

Available under License Creative Commons Attribution.

Download (590kB) | Preview


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.

Item Type: Article
Uncontrolled Keywords: extremal problems, perfect 1-factorization, induced subgraphs, the regularity lemma
Subjects: Q Science / természettudomány > QA Mathematics / matematika
Depositing User: MTMT SWORD
Date Deposited: 05 Apr 2024 11:01
Last Modified: 05 Apr 2024 11:01

Actions (login required)

Edit Item Edit Item