On the minimum semidefinite rank of a simple graph

Matthew Booth, Philip Hackney, Benjamin Harris, Charles R. Johnson, Margaret Lay, Terry D. Lenker, Lon H. Mitchell, Sivaram K. Narayan, Amanda Pascoe, and Brian D. Sutton

Linear Multilinear Algebra 59 (2011), no. 5, 483–506.

The minimum semidefinite rank of a graph is defined to be the minimum rank among all positive semidefinite matrices whose zero/nonzero pattern corresponds to that graph. We recall some known facts and present new results, including results concerning the effects of vertex or edge removal from a graph on minimum semidefinite rank.

home