{"id":"arxiv/2608.17727","url":"https://arxiv.org/abs/2608.17727","tags":["math.CO"],"score":0,"title":"An asymptotic solution to 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 his 1977 formulation of the problem, Erdő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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-18","reactions":{}}