The positive semidefinite Graph Complement Conjecture

Let GG be a graph, and let mr+(G)\operatorname{mr}_+(G) denote the minimum rank among positive semidefinite matrices in the class S(G)\mathcal{S}(G) of real symmetric matrices described by GG. Write GcG^c for the complement of GG and \ordG\ord G for its number of vertices.

Positive semidefinite Graph Complement Conjecture. For any graph GG,

mr+(G)+mr+(Gc)\ordG+2.\operatorname{mr}_+(G)+\operatorname{mr}_+(G^c)\leq \ord G+2.

This strengthens the ordinary Graph Complement Conjecture, and the source notes that the bound is sharp for paths; no general resolution is supplied.

Sources & referencesView supporting material

Primary source

Francesco Barioli, Shaun M. Fallat, Himanshu Gupta and Zhongshan Li, “The Weak Version of the Graph Complement Conjecture and Partial Results for the Delta Conjecture”, arXiv:2505.24577 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.