Semidefinite approximations for bicliques and biindependent pairs
Monique Laurent  1, 2, *@  , Sven Polak  1, *@  , Luis Felipe Vargas  1, *@  
1 : Centrum Wiskunde & Informatica
2 : Tilburg University
* : Corresponding author

A (bipartite) biindependent pair in a bipartite graph $G=(V_1 \cup V_2, E)$ is a pair $(A,B)$, where $A\subseteq V_1$, $B\subseteq V_2$ and the union $A\cup B$ is independent in $G$. We study the parameters $g(G)$ and $h(G)$, defined, respectively, as the maximum product $|A||B|$ and the maximum ratio $\frac{|A||B|}{|A|+|B|}$, over all such biindependent pairs $(A,B)$ in $G$. We define semidefinite programming upper bounds on $g(G)$ and $h(G)$. We show they are quadratic variations of Lovász's theta number, and we show links among them and with a parameter by Haemers. We formulate closed-form eigenvalue bounds, coinciding with the semidefinite bounds for edge-transitive graphs. 



  • Poster
Online user: 1 Privacy
Loading...