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?

  • 2
    $\begingroup$ 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. $\endgroup$
    – Boris Bukh
    Sep 9, 2013 at 21:01
  • $\begingroup$ @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? $\endgroup$
    – alezok
    Sep 10, 2013 at 12:26


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.