Large disjoint subgraphs with the same order and size

For a graph GG let f(G)f(G) be the largest integer kk such that there are two vertex-disjoint subgraphs of GG, each with kk vertices, and that induce the same   number of edges. Clearly f(G)≤⌊n/2⌋f(G)≤⌊n/2⌋ but this is not always achievable.Our main result is that for any fixed α>0α>0, if GG has nn vertices and at most n2−αn2−α edges, then f(G)=n/2−o(n)f(G)=n/2−o(n), which is asymptotically optimal. The proof also yields a polynomial time randomized algorithm.More generally, let tt be a fixed nonnegative integer and let HH be a fixed graph. Let fH(G,t)fH(G,t) be the largest integer kk such that there are two kk-vertex subgraphs of GG having at most tt vertices in common, that induce the same   number of copies of HH. We prove that if HH has rr vertices then fH(G,t)=Ω(n1−(2r−1)/(2r+2t+1))fH(G,t)=Ω(n1−(2r−1)/(2r+2t+1)). In particular, there are two subgraphs of the same order Ω(n1/2+1/(8r−2))Ω(n1/2+1/(8r−2)) that induce the same number of copies of HH and that have no copy of HH in common.