2
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 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

0

Reset to default

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.