Chengrui Fang

On the Erd\H{o}s Five-Edge Intersection Problem

For an $n$-vertex graph $G$ and a permutation $\pi$ of its vertex set, let \[ I_G(\pi)=|E(G)\cap E(G_{\pi})|,\qquad \mu(G)=\min_{\pi} I_G(\pi), \] where $G_{\pi}$ is the copy of $G$ obtained by relabelling every vertex $x\in V(G)$ as $\pi(x)$. Let $f(n,k)$ be the minimum number of edges in an $n$-vertex graph $G$ satis...