# Find large “induced” bipartite graph in a dense graph?

Do there exist constants $$d>0$$, $$0, $$\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$$.

• This question is very hard to follow as written. This is how I took what you written. So you want to know if there is a dense graph $H$ that satisfies the following: Let $G$ be any subgraph of $H$ with high minimum degree, then there are two disjoint subsets $A$ and $B$ of $VG)$ such that the number of edges between $A$ and $B$ in $G$ is large. Am I correct? – Mike Mar 12 '19 at 19:53
• Yes, but also with requirement that the edges between $A$ and $B$ in $G$ are same as those of $H$. – Connor Mar 12 '19 at 19:56
• OK but I didn't get that from the way you worded your question originally. You really ought to consider editting it. – Mike Mar 12 '19 at 20:00
• It reflects on $e_G(A,B)=e_H(A,B)$. – Connor Mar 13 '19 at 0:02
• If you place each vertex of $G$ in $A$ or $B$ independently at random then $A$ and $B$ are linear in $n$ and the number of edges of $G$ (or $H$) between $A$ and $B$ is at least $cn^2/4$ in expectation. – Louis Esperet Mar 13 '19 at 17:26

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.