MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider a balanced bipartite graph $G=(U,V,E)$, i.e., a bipartite graph with $|U|=|V|$. An independent set $I$ of $G$ is balanced if $|I \cap U| = |I \cap V|$.

The bipartite independence number of $G$, usually denote in literature by $i_{BIP}(G)$ or $\alpha_{BIP}(G)$, is the maximum size of a balanced independent set of $G$.

The bipartite independence number is known for the $n$-dimensional hypercube $Q_n$ (see Ramras 2010 and Barber 2012).

Q1) Is there any other graph for which it is known exactly? Is there any non-trivial upper bound on $i_{BIP}(G)$? If we add the hypothesis that $G$ is $k$-regular, do these two answers change?

Q2) In particular, is the bipartite independence number known for the $2m \times 2n$ square grid or for the $2m \times 2n$ toric square grid?

share|cite|improve this question
It is approximately equal to $(2m)(2n)/2$. Indeed, here is a construction that attains this bound: partition the grid into two equally large regions (say subrectangles). In one region take all vertices in the interior that are in $U$. In the other, all vertices in the interior that are in $V$. As for the upper bound, one can prove it by double-counting. – Boris Bukh Sep 9 '13 at 21:01
@Boris: thanks for your comment and ideas. What do you mean exactly by "one can prove it by double-counting"? Would you double-count edges or nodes? – alezok Sep 10 '13 at 12:26

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.