Difference-isomorphic graph families

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 - n/2) and characterizing all the extremal constructions. We also prove an analogous result for r-uniform hypergraphs.