BIPARTITE INDEPENDENCE NUMBER IN GRAPHS WITH BOUNDED MAXIMUM DEGREE.

We consider a natural, yet seemingly not much studied, extremal problem in bipartite graphs. A bi-hole of size t in a bipartite graph G with a fixed bipartition is an independent set with exactly t vertices in each part; in other words, it is a copy of Kt,t in the bipartite complement of G. Let f(n, Delta) be the largest k for which every n times n bipartite graph with maximum degree Delta in one of the parts has a bi-hole of size k. Determining f(n, Delta) is thus the bipartite analogue of finding the largest independent set in graphs with a given number of vertices and bounded maximum degree. It has connections to the bipartite version of the Erd Hos--Hajnal conjecture, bipartite Ramsey numbers, and the Zarankiewicz problem. Our main result determines the asymptotic behavior of f(n, Delta). More precisely, we show that for large but fixed Delta and n sufficiently large, f(n, Delta) = Theta (log Delta Delta n). We further address more specific regimes of Delta, especially when Delta is a small fixed constant. In particular, we determine f(n, 2) exactly and obtain bounds for f(n, 3), though determining the precise value of f(n, 3) is still open. [ABSTRACT FROM AUTHOR]