STRUCTURED CODES of GRAPHS

Noga Alon, Anna Gujgiczer, János Körner, Aleksa Milojević, Gábor Simonyi

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)379-403
Number of pages25
JournalSIAM Journal on Discrete Mathematics
Volume37
Issue number1
DOIs
StatePublished - 2023

All Science Journal Classification (ASJC) codes

  • General Mathematics

Keywords

  • extremal problems
  • induced subgraphs
  • perfect 1-factorization
  • the regularity lemma

Fingerprint

Dive into the research topics of 'STRUCTURED CODES of GRAPHS'. Together they form a unique fingerprint.

Cite this