A bipartite version of the Erdős $-$ McKay conjecture

Abstract

An old conjecture of Erdős and McKay states that if all homogeneous sets in an $n$-vertex graph are of order $O(\log n)$ then the graph contains induced subgraphs of each size from $\{0,1,\dots ,\Omega (n^2)\}$. We prove a bipartite analogue of the conjecture: if all balanced homogeneous sets in an $n\times n$ bipartite graph are of order $O(\log n)$ then the graph contains induced subgraphs of each size from $\{0,1,\dots ,\Omega (n^2)\}$.

17 pages, to appear in CPC