{"id":"arxiv/2608.25153","url":"https://arxiv.org/abs/2608.25153","tags":["math.CO"],"score":0,"title":"The Erdős four-edge intersection problem","domain":"math.CO","source":"arxiv","authors":["Andrzej Żak"],"reviews":0,"subject":"math.CO","summary":"For an $n$-vertex graph $G$ and a permutation $σ$ of its vertex set, let $σ(G)$ denote the corresponding relabelling of $G$, and put \\[ I_G(σ)=|E(G)\\cap E(σ(G))|. \\] Let $f(n,k)$ be the minimum number of edges in an $n$-vertex graph for which $I_G(σ)\\geq k$ for every $σ$. In 1977 Erdős asked whether $f(n,4)=2n-4$, observing that $K_{2,n-2}$ gives the upper bound. We prove that, for all sufficiently large $n$, \\[ f(n,4)=2n-4. \\] Equivalently, every sufficiently large $n$-vertex graph with at most $2n-5$ edges has a relabelling with at most three common edges. Our proof is inspired by the…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-25","reactions":{}}