Difference-Isomorphic Graph Families

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 $\mathcal{G}$ of graphs on $[n]$, such that for every two $G_1,G_2\in \mathcal{G}$, the graphs $G_1\setminus G_2$ and $G_2\setminus G_1$ are isomorphic. We completely resolve this problem by showing that this maximum is exactly $2^{\frac{1}{2}\left(\right(\genfrac{}{}{0ex}{}{n}{2})-\lfloor \frac{n}{2}\rfloor )}$ and characterizing all the extremal constructions. We also prove an analogous result for $r$-uniform hypergraphs.