An asymptotic solution to the Erd\H{o}s four-edge intersection problem

Abstract

For an $n$-vertex graph $G$ and a permutation $\sigma$ of its vertex set, let $\sigma(G)$ denote the corresponding relabelling of $G$, and put $I_G(\sigma)=|E(G)\cap E(\sigma(G))|$. Let $f(n,k)$ be the minimum number of edges in an $n$-vertex graph for which $I_G(\sigma)\geq k$ for every $\sigma$. In his 1977 formulation of the problem, Erd\H{o}s discussed the small values of $k$ and left the cases $k=4$ and $k=5$ as the next natural open questions. For $k=4$ he asked whether $f(n,4)=2n-4$, with the upper bound witnessed by $K_{2,n-2}$; the neighbouring $k=5$ question was recently settled exactly by Fang and Hou. We prove that every graph $G$ of order $n$ and size at most $2n-10n^{2/3}-7$ has a relabelling with at most three common edges. Consequently, \[ 2n-10n^{2/3}-7<f(n,4)\leq 2n-4, \] and hence \[ f(n,4)=2n-o(n). \] Thus we resolve Erd\H{o}s's four-edge intersection problem asymptotically, confirming his proposed value up to a sublinear error term. For comparison, for all sufficiently large $n$, Fang and Hou's result guarantees at most four common edges for graphs with at most $2n-3$ edges, whereas reducing the edge bound by only $10n^{2/3}+4=o(n)$ already allows us to guarantee at most three common edges.