The graph complement conjecture for minimum symmetric rank
For a finite simple graph $G$ on the vertex set $\{1, \dots, n\}$, $n \ge 1$, let $\mathcal S(G)$ be the set of real symmetric $n \times n$ matrices $A$ such that, for $i \ne j$, $a_{ij} \ne 0$ exactly when $\{i, j\}$ is an edge of $G$, the diagonal being unrestricted, and let $\operatorname{mr}(G)$ be the least rank of a matrix in $\mathcal S(G)$. Let $G^c$ be the complement of $G$. Paths on $n \ge 4$ vertices attain the bound below. Barioli, Barrett, Fallat, Hall, Hogben and van der Holst proved it for all graphs on at most $10$ vertices, and Barioli, Fallat, Gupta and Li proved $\operatorname{mr}(G) + \operatorname{mr}(G^c) < (1 + 1/\sqrt{2})\,n + 1$ for $n \ge 4$. The stronger bound with the least rank of a positive semidefinite matrix in $\mathcal S(G)$ in place of $\operatorname{mr}$ is known for trees, unicyclic graphs, chordal graphs and partial $3$-trees, among others (see Jansrang and Narayan).
Problem. Is $\operatorname{mr}(G) + \operatorname{mr}(G^c) \le n + 2$ for every $n \ge 1$ and every graph $G$ on $n$ vertices?
Source: Grew out of the question how large mr(G) + mr(Gᶜ) can be, posed at the 2006 AIM workshop on spectra of families of matrices described by graphs (workshop report, Question 0.16); as this bound, Barioli, Barrett, Fallat, Hall, Hogben and van der Holst (2012), Conjecture 1.1.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- CO — Combinatorics
- Secondary
- NA, SP
- Keywords
- graph complements, inverse eigenvalue problems, minimum rank, OpenProblemsInNLA
- Literature checked
- Oct. 7, 2026 by clemens-admin
References
@misc{aim2006,
author = {Brualdi, Richard and Hogben, Leslie and Shader, Bryan},
title = {Spectra of families of matrices described by graphs, digraphs, and sign patterns},
howpublished = {Workshop report, American Institute of Mathematics, Palo Alto, October 23--27, 2006},
year = {2006},
url = {https://aimath.org/pastworkshops/matrixspectrumrep.pdf},
note = {Question 0.16},
}
@article{barioli2012,
author = {Barioli, Francesco and Barrett, Wayne and Fallat, Shaun M. and Hall, H. Tracy and Hogben, Leslie and van der Holst, Hein},
title = {On the graph complement conjecture for minimum rank},
journal = {Linear Algebra Appl.},
volume = {436},
number = {12},
year = {2012},
pages = {4373--4391},
doi = {10.1016/j.laa.2010.12.024},
}
@article{barioli2026,
author = {Barioli, Francesco and Fallat, Shaun M. and Gupta, Himanshu and Li, Zhongshan},
title = {The weak version of the graph complement conjecture and partial results for the delta conjecture},
journal = {Discrete Math.},
volume = {349},
number = {3},
year = {2026},
pages = {114861},
doi = {10.1016/j.disc.2025.114861},
eprint = {2505.24577},
archivePrefix = {arXiv},
}
@article{jansrang2021,
author = {Jansrang, Monsikarn and Narayan, Sivaram K.},
title = {Graph complement conjecture for classes of shadow graphs},
journal = {Oper. Matrices},
volume = {15},
number = {2},
year = {2021},
pages = {589--614},
doi = {10.7153/oam-2021-15-40},
}
@misc{openproblemsinnla-sp10,
author = {Townsend, Alex},
title = {{SP-10}: The graph complement conjecture for minimum symmetric rank},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/eigenvalues-and-inverse-problems/SP-10/README.md},
note = {Read at commit 7336302, 2026-10-06},
}
Resolution claims
The graph complement conjecture asks whether $\operatorname{mr}(G)+\operatorname{mr}(\overline G)\le n+2$ for every graph on $n$ vertices. Take a bipartite graph whose vertices on one side have degree at most $d$. Vectors $(1,t_i,\dots,t_i^d)$ at distinct positive nodes and the coefficient vectors of padded neighbourhood polynomials give a faithful nonzero Gram representation of its complement in dimension $d+1$. Complements of partial 2-trees have …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-09 | Open → Partially resolved | The registry's curators | A bipartite degree-four theorem and an exact duality obstruction v1 recorded from OpenProblemsInNLA @ eb7c9d6, SP-10/manuscript.pdf. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00158, "The graph complement conjecture for minimum symmetric rank", clopen.solutions.