What question did this study set out to answer?

The central aim is to determine the maximum size of a family of graphs where the differences between any two are isomorphic.

June 28, 2026Open Access

Difference-isomorphic graph families

Key Points

The central aim is to determine the maximum size of a family of graphs where the differences between any two are isomorphic.
Developed a mathematical framework to analyze the graph differences.
Characterized extremal constructions of graph families that meet the criteria.
Demonstrated that the maximum size is exactly $2^{\frac{1}{2} \left( \binom{n}{2} - \lfloor \frac{n}{2} \rfloor \right)}$.
Established corresponding results for $r$-uniform hypergraphs.

Abstract

Many well-studied problems in extremal combinatorics deal with the maximum possible size of a family of objects in which every pair of objects satisfies a given restriction. One problem of this type was recently raised by Alon, Gujgiczer, Körner, Milojević and Simonyi. They asked to determine the maximum size of a family G of graphs on n, such that for every two G₁, G₂ G, the graphs G₁ G₂ and G₂ G₁ are isomorphic. We completely resolve this problem by showing that this maximum is exactly 2^1{2 (n2 - n2) } and characterizing all the extremal constructions. We also prove an analogous result for r-uniform hypergraphs.

KI fragen

Bookmark

View Full Paper