TransWikia.com

Condition on ratio related to bipartite graph

Mathematics Asked by Chao on December 15, 2021

I know that for a bipartite graph, the adjacency matrix can be written as
begin{align}
A =
begin{pmatrix}
0_{rr} & B \ B^T & 0_{ss}
end{pmatrix}.
end{align}

Let $M_{-}$ be the signed incidence matrix and let $C$ be the matrix defined as
begin{align}
C =
begin{pmatrix}
0_{rr} & B \ 0_{rs} & 0_{ss}
end{pmatrix}.
end{align}

I’m interested to find, under which conditions on the graph, the ratio
begin{align}
kappa = frac{sigma_{max}(C)}{tilde{sigma}_{min}(M_{-})}
end{align}

is very small, (i.e. almost zero)? where $sigma_{max}(C)$ is the maximum singular value of the matrix $C$ and $tilde{sigma}_{min}(M_{-})$ is is the minimum non-zero singular value of $M_{-}$.

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP