Complete bipartite subgraph problem

Question

$A,B$ are the sides of a bipartite graph with $\frac{|A| \cdot |B|}{k}$ edges, where $k$ is an integer. Prove that there are $A' \subset A$ and $B' \subset B$ such that $|A'| \geq |A|/k, |B'| \geq |B|/2^{|A|}$ and the subgraph formed by $A', B'$ is a complete bipartite graph.

The problem can be solved if one proves that $\sum_{b \in B} {\deg(b) \choose a/k} > b$, which could be proved by Jensen, but unfortunately the function $f(x) = {x \choose t}$ is not always convex.

Answer 1

Consider $$d =\frac{|A| \cdot |B|}{k}/(A+B)$$ to be the ratio of the number of edges in $G$. Delete all vertices in A of degree at most $\frac{d|B|}{2}$ and let $A'$ be the remaining subset of $A$. we left with at least $d|A||B| − d|A||B|/2 = d|A||B|/2$ remaining edges from $A'$ to $B$. notice that each vertex in $A'$ is in at most $|B'|$ edges, $$|B'| ≥ d|A||B|/2|A| = d|B|/2.$$ and the rest of the proof follows from here.