Given $G$ as bipartite graph of genus $g(G)$ with number of vertices of each color being $N$ with $A$ as $N\times N$ biadjacency matrix. Denote $\bar{G}$ to bipartite graph of genus $g(\bar{G})$ of $N\times N$ biadjacency matrix $J-A$ with $J$ being a $1$ matrix. Denote $r$ as rank of $N\times N$ biadjacency matrix $A$.

Denote $g=max(g(G)$, $g(\bar{G}))$.

Is $\log r \geq c'(\log \frac{N}g)^{\frac{1}c}$ for some fixed $c,c'>1$?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.