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 K-t,K- t in the bipartite complement of G. Let f(n, Delta) be the largest k for which every n x 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 Erdos-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.