Graph-codes

Noga Alon

doi:10.1016/j.ejc.2023.103880

Graph-codes

Noga Alon

Mathematics

Research output: Contribution to journal › Article › peer-review

7 Scopus citations

Abstract

The symmetric difference of two graphs G₁,G₂ on the same set of vertices [n]={1,2,…,n} is the graph on [n] whose set of edges are all edges that belong to exactly one of the two graphs G₁,G₂. Let H be a fixed graph with an even (positive) number of edges, and let D_H(n) denote the maximum possible cardinality of a family of graphs on [n] containing no two members whose symmetric difference is a copy of H. Is it true that [Formula presented] for any such H? We discuss this problem, compute the value of D_H(n) up to a constant factor for stars and matchings, and discuss several variants of the problem including ones that have been considered in earlier work.

Original language	English (US)
Article number	103880
Journal	European Journal of Combinatorics
Volume	116
DOIs	https://doi.org/10.1016/j.ejc.2023.103880
State	Published - Feb 2024

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.ejc.2023.103880

Cite this

@article{8797159891764a02a536e945bf7f1208,

title = "Graph-codes",

abstract = "The symmetric difference of two graphs G1,G2 on the same set of vertices [n]=\{1,2,…,n\} is the graph on [n] whose set of edges are all edges that belong to exactly one of the two graphs G1,G2. Let H be a fixed graph with an even (positive) number of edges, and let DH(n) denote the maximum possible cardinality of a family of graphs on [n] containing no two members whose symmetric difference is a copy of H. Is it true that [Formula presented] for any such H? We discuss this problem, compute the value of DH(n) up to a constant factor for stars and matchings, and discuss several variants of the problem including ones that have been considered in earlier work.",

author = "Noga Alon",

note = "Publisher Copyright: {\textcopyright} 2023",

year = "2024",

month = feb,

doi = "10.1016/j.ejc.2023.103880",

language = "English (US)",

volume = "116",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press",

}

TY - JOUR

T1 - Graph-codes

AU - Alon, Noga

PY - 2024/2

Y1 - 2024/2

N2 - The symmetric difference of two graphs G1,G2 on the same set of vertices [n]={1,2,…,n} is the graph on [n] whose set of edges are all edges that belong to exactly one of the two graphs G1,G2. Let H be a fixed graph with an even (positive) number of edges, and let DH(n) denote the maximum possible cardinality of a family of graphs on [n] containing no two members whose symmetric difference is a copy of H. Is it true that [Formula presented] for any such H? We discuss this problem, compute the value of DH(n) up to a constant factor for stars and matchings, and discuss several variants of the problem including ones that have been considered in earlier work.

AB - The symmetric difference of two graphs G1,G2 on the same set of vertices [n]={1,2,…,n} is the graph on [n] whose set of edges are all edges that belong to exactly one of the two graphs G1,G2. Let H be a fixed graph with an even (positive) number of edges, and let DH(n) denote the maximum possible cardinality of a family of graphs on [n] containing no two members whose symmetric difference is a copy of H. Is it true that [Formula presented] for any such H? We discuss this problem, compute the value of DH(n) up to a constant factor for stars and matchings, and discuss several variants of the problem including ones that have been considered in earlier work.

UR - https://www.scopus.com/pages/publications/85176957923

UR - https://www.scopus.com/pages/publications/85176957923#tab=citedBy

U2 - 10.1016/j.ejc.2023.103880

DO - 10.1016/j.ejc.2023.103880

M3 - Article

AN - SCOPUS:85176957923

SN - 0195-6698

VL - 116

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

M1 - 103880

ER -

Graph-codes

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this