Erdős four-edge intersection problem

For an $n$ -vertex graph $G$ and a permutation $\sigma$ of its vertex set, define $I_G(\sigma)=|E(G)\cap E(\sigma(G))|$ , and let $f(n,4)$ be the minimum possible value of $|E(G)|$ over all $n$ -vertex graphs satisfying $I_G(\sigma)\ge 4$ for every permutation $\sigma$ . The problem asks whether, for all sufficiently large integers $n$ , $f(n,4)=2n-4$ .

Progress summary

Partially solved

A new paper gets very close to the predicted answer, but the exact answer is still unknown.

Erdős’s four-edge intersection problem seeks the exact value of $f(n,4)$ , conjectured to be $2n-4$ .

August 2026 asymptotic resolution

Peter Keevash and Benny Sudakov proved $2n-10n^{2/3}-7<f(n,4)\le 2n-4$ , reducing the gap to a sublinear error. The conjectured exact formula remains open.

Current status (as of August 2026): The problem has an asymptotic solution, but the exact formula $f(n,4)=2n-4$ remains unproved.

Sources

arxiv.org

Sources & referencesView supporting material

Primary source

arXiv

Additional references

An asymptotic solution to the Erdős four-edge intersection problem — arXiv — Peter Keevash, Benny Sudakov

extremal-combinatorics graph-theory

2 days ago

No solutions have been posted yet.