Complete Bipartite Subgraph of Dense Bipartite Subgraph Q1: Consider a $2^n$ by $2^n$ bipartite graph with at least $(1-\epsilon)2^{2n}$ edges. For any $\epsilon > 0$ and $n$ large enough, is it always possible to find a $2^{(1-f(\epsilon))n}$ by $2^{(1-f(\epsilon))n}$ complete bipartite subgraph, where $\underset{\epsilon\rightarrow0^+}{lim}f(\epsilon)=0$?
 A: No. The correct bound for the largest guaranteed balanced complete bipartite subgraph is $\Theta_{\epsilon}(n)$, where the implied constant depending on $\epsilon$ tends to infinity  as $\epsilon \to 0$, so it is only logarithmic in the total number of vertices. 
For the upper bound, consider the random bipartite graph with parts of order $2^n$ where each edge appears with probability $1-\epsilon/2$. By Chernoff's inequality, with high probability, this graph will have at least a $1-\epsilon$ fraction of the pairs as edges, and a simple union bound over all possible $K_{t,t}$ with $t=g(\epsilon)n$ for an appropriate choice of $g(\epsilon)$ shows that this also will be $K_{t,t}$-free with high probability. This is essentially the same argument as given by Erdos in his classical lower bound on Ramsey numbers from 1947. 
For the lower bound, suppose we are trying to show that there is a $K_{t,t}$. Then count the number of pairs $(v,T)$ consisting of one vertex from the first part and a set $T$ of $t$ vertices from the second part which are all neighbors of $v$. The number of such pairs is $\sum_{v}{\textrm{deg}(v) \choose t}$. One can lower bound this using the number of edges of the graph and Jensen's inequality. On the other hand, if there is no $K_{t,t}$ each $T$ is in at most $t$ pairs and hence the number of such pairs is at most $(t-1){2^n \choose t}$. One gets a contradiction to there being no $K_{t,t}$ if $t$ is too small.
