Find large "induced" bipartite graph in a dense graph?

Question

Do there exist constants $d>0$, $0<c<1$, $\delta>0$ so that for all large $n$, there exists a graph $H$ satisfying $$e_H\ge dn^2,$$ and then no matter how we remove some edges from $H$ to get an $n$-vertex subgraph $G$, whenever $G$ has minimum degree at least $cn$, there are two disjoint vertex-subsets $A,B$ of $G$ with $|A|,|B|\ge\delta n$ and $$e_G(A,B)=e_H(A,B)\ge \tilde{d}n^2,$$ where $\tilde{d}>0$ may depend on $d$?

In words, for any large $n$, is there a dense $n$-vertex graph $H$ so that for any subgraph $G$ of $H$ with high minimum degree, we can find two large disjoint vertex-subsets of $G$ so that the edges of $G$ between these two sets are same as those of $H$, and they are dense?

I try to start with $H=K_n$. Then we only need to show $K_n$ has a subgraph $G$ so that there are two linear size vertex-subsets, the edges of $G$ between them are same as those of $K_n$.

Answer 1

The answer is no (if I understood your question correctly this time).

Fix $H$ and take $G$ to be a random subgraph of $H$, where you keep each edge with probability $p$, for some constant $p>0$. For fixed sets $A$ and $B$ with at least $\tilde{\delta}n^2$ edges of $H$ between them, the number of edges of $H\setminus G$ between $A$ and $B$ is at least $\tilde{\delta}n^2(1-p)$ in average, and is highly concentrated around its mean (it follows from the Chernoff bound that it is zero with probability at most $\exp(-\Omega(n^2))$). Since there are at most $\exp(O(n))$ such pairs $A,B$, it follows from the union bound that with non-zero probability, for any such sets $A$ and $B$, there is at least one edge of $H\setminus G$ between $A$ and $B$. So you will never have $e_G(A,B)=e_H(A,B)$ in this case.