On the Erdős Five-Edge Intersection Problem
For an $n$-vertex graph $G$ and a permutation $π$ of its vertex set, let \[ I_G(π)=|E(G)\cap E(G_π)|,\qquad μ(G)=\min_π I_G(π), \] where $G_π$ is the copy of $G$ obtained by relabelling every vertex $x\in V(G)$ as $π(x)$. Let $f(n,k)$ be the minimum number of edges in an $n$-vertex graph $G$ satisfying $μ(G)\ge k$. Erdős recorded a construction of Mullin showing $f(n,5)\le 2n-2$ and asked whether equality holds for sufficiently large $n$. We prove that it does: \[ f(n,5)=2n-2 \] for all sufficiently large $n$. The proof strategy is a core--buffer--completion framework: it moves the few…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.13071
curl -X POST /api/v1/records/arxiv/2608.13071/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.13071/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'