Finding a large $\epsilon$-regular subset of a graph The density of a set $S\subseteq G$ is defined as $d(S)=e(S)/\binom{|S|}{2}$ (where $e(S)$ is the number of edges of $G$ contained in $S$). We say that a subset $S\subseteq V(G)$ is $\epsilon$-regular if for any subset $A\subseteq S$ satisfying $|A|\geq \epsilon|S|$ we have $|d(S)- d(A)|\leq \epsilon$. Fox and Conlon asked how large an $\epsilon$-regular subset must each graph have [1]. Let $m_{\epsilon}(n)$ be the largest $m$ for which every $n$-vertex graph contains an $\epsilon$-regular set on at least $m_{\epsilon}(n)$ vertices. It is easy to see that $m_{\epsilon}(n)$ is an increasing function in $n$. Indeed by Ramsey's Theorem every sufficiently large graph has a large complete or independent subgraph, and every complete graph or independent set is $\epsilon$-regular for every $\epsilon> 0$. Fox and Conlon showed proved the following.
lemma. [Fox and Conlon {[1]} ] For each $0 < \epsilon < 1/2$, let $\delta = 2^{-\epsilon^{-(10/\epsilon)^4}}.$ Every graph $G$ on $n$ vertices contains an $\epsilon$-regular subset $S$ with $|S| \geq \delta n$. It is possible to construct $n$-vertex graphs which have no $\epsilon$-regular subsets of size $\epsilon^{c\epsilon^{-1}}n$ (for example by generalising a construction of Peng, Rödl, and Ruciński [2]). Therefore we have that $m_{\epsilon}(n)= \delta(\epsilon) n$ for some function $\delta(\epsilon)$ .
problem. Improve on the bounds $\epsilon^{c\epsilon^{-1}} \leq \delta(\epsilon) \leq 2^{-\epsilon^{-(10/\epsilon)^4}}$. There is a bipartite version of this which was solved by Peng, Rödl, and Ruciński. Here, given a bipartite graph with parts $X$ and $Y$, one looks for an $\epsilon$-regular pair $(X_1,Y_1)$ with $X_1\subseteq X$, $Y_1\subseteq Y$, and for all $A\subseteq X_1$, $B\subseteq Y_1$ satisfying $|A|\geq \epsilon|X_1|$, $|B|\geq \epsilon|Y_1|$ we have $|d(A,B)- d(X,Y)|\leq \epsilon$.
Theorem. [Peng, Rödl, and Ruciński {[2]}] For each $0 < \epsilon < 1/2$, let $\delta = 2^{-\epsilon^{-2}}.$ Every bipartite graph $G$ on $n$ vertices in each part contains an $\epsilon$-regular pair $(A,B)$ with $|A|,|B| \geq \delta n$. \subsection{References} [1] D. Conlon and J. Fox, Bounds for graph regularity and removal lemmas. \emph{Geom. Funct. Anal.}, 22 (2012) 1191-1256. \label{Conlon} \ [2] Y. Peng, V. Rödl and A. Ruciński. Holes in graphs. \emph{Electron. J. Combin.}, 9 (2002). \label{Peng}