Self-similarity of graphs

An old problem raised independently by Jacobson and Sch"onheim asks to determine the maximum $s$ for which every graph with $m$ edges contains a pair of edge-disjoint isomorphic subgraphs with $s$ edges. In this paper we determine this maximum up to a constant factor. We show that every $m$-edge graph contains a pair of edge-disjoint isomorphic subgraphs with at least $c (m\log m)^{2/3}$edgesforsomeabsoluteconstant$c$, and find graphs where this estimate is off only by a multiplicative constant. Our results improve bounds of Erd\H{o}s, Pach, and Pyber from 1987.