Graph-codes

DOI10.1016/J.EJC.2023.103880MaRDI QIDQ6189687zbMATH OpenFDO

Authors Noga Alon

Publication date 5 February 2024

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2301.13305

zbMATH Keywords

\(\mathcal H\)-codesymmetric difference of two graphs

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Extremal problems in graph theory (05C35) Structural characterization of families of graphs (05C75) Graph operations (line graphs, products, etc.) (05C76) Special sequences and polynomials (11B83)

Abstract: The symmetric difference of two graphs $G_1,G_2$ on the same set of vertices $[n]=1,2,ldots,n$ is the graph on $[n]$ whose set of edges are all edges that belong to exactly one of the two graphs $G_1,G_2$. 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 $D_H(n)=o(2^{nchoose2})$ 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.

Recommendations

• Phase transitions of structured codes of graphs
• Structured Codes of Graphs
• Connectivity graph-codes
• scientific article; zbMATH DE number 437471

Cites work

• \(K_4\)-intersecting families of graphs
• Edge-coloring cliques with three colors on all 4-cliques
• Forbidding just one intersection
• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• scientific article; zbMATH DE number 3233758 (Why is no real title available?)
• Intersection theorems with geometric consequences
• On difference sets of sequences of integers. III
• Structured Codes of Graphs
• The Erdős-Gyárfás problem on generalized Ramsey numbers
• Triangle-intersecting families of graphs

Cited in

(10)

• Phase transitions of structured codes of graphs
• Connectivity graph-codes
• Three applications of coverings to difference patterns
• A variant of the Erdős-Gyárfás problem for K₈
• The probability that a random graph is even-decomposable
• Odd-Ramsey numbers of complete bipartite graphs
• Upper bounds for linear graph codes
• Even-degeneracy of a random graph
• Unions of intervals in codes based on powers of sets
• Difference-isomorphic graph families

This page was built for publication: Graph-codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6189687)