The delta 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 $\delta(G)$ be the minimum degree of $G$. Lovász, Saks and Schrijver's orthogonal representations give a positive semidefinite matrix in $\mathcal S(G)$ whose nullity is at least the vertex connectivity of $G$, which is at most $\delta(G)$ and can be smaller. The bound below holds for trees, for graphs with $\delta(G) \le 3$ and for bipartite graphs, among other classes (see Fallat and Hogben), and Barioli, Fallat, Gupta and Li proved it for graphs of girth at least $11$ and minimum degree at least $4$.
Problem. Is there, for every $n \ge 1$ and every graph $G$ on $n$ vertices, a matrix $A \in \mathcal S(G)$ with $\dim \ker A \ge \delta(G)$; equivalently, is $\operatorname{mr}(G) \le n - \delta(G)$ for every such $G$?
Source: Posed at the 2006 AIM workshop on spectra of families of matrices described by graphs (workshop report, Conjecture 0.9, stated there over every infinite field); for real symmetric matrices, as here, see Barioli, Fallat, Gupta and Li (2026), §1.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- CO — Combinatorics
- Secondary
- NA, SP
- Keywords
- inverse eigenvalue problems, maximum nullity, minimum rank, OpenProblemsInNLA
- Literature checked
- Oct. 8, 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 = {Conjecture 0.9},
}
@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{lovasz1989,
author = {Lov{\'a}sz, L{\'a}szl{\'o} and Saks, Michael and Schrijver, Alexander},
title = {Orthogonal representations and connectivity of graphs},
journal = {Linear Algebra Appl.},
volume = {114/115},
year = {1989},
pages = {439--454},
doi = {10.1016/0024-3795(89)90475-8},
}
@article{lovasz2000,
author = {Lov{\'a}sz, L{\'a}szl{\'o} and Saks, Michael and Schrijver, Alexander},
title = {A correction: orthogonal representations and connectivity of graphs},
journal = {Linear Algebra Appl.},
volume = {313},
number = {1--3},
year = {2000},
pages = {101--105},
doi = {10.1016/S0024-3795(00)00091-4},
}
@misc{fallat2011,
author = {Fallat, Shaun M. and Hogben, Leslie},
title = {Variants on the minimum rank problem: A survey {II}},
year = {2011},
eprint = {1102.5142},
archivePrefix = {arXiv},
}
@misc{openproblemsinnla-sp11,
author = {Townsend, Alex},
title = {{SP-11}: The delta 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-11/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Canonical Lean statement
A submission resolves this problem by proving the constant Problem_OP_00252.
namespace RegistryProblems.OP_00252
noncomputable section
/-- Symmetry, the exact off-diagonal graph pattern, and unrestricted diagonal. -/
def HasPattern {n : ℕ} (G : SimpleGraph (Fin n))
(A : Matrix (Fin n) (Fin n) ℝ) : Prop :=
(∀ i j, A i j = A j i) ∧
∀ i j, i ≠ j → (A i j ≠ 0 ↔ G.Adj i j)
/-- Classical decidability is used only to compute finite neighbor cardinalities. -/
noncomputable def MinimumDegree {n : ℕ} (G : SimpleGraph (Fin n)) : ℕ := by
classical
exact G.minDegree
/-- OP-00252: The delta conjecture for minimum symmetric rank -/
def _root_.RegistryProblems.Problem_OP_00252 : Prop :=
∀ n : ℕ, 0 < n → ∀ G : SimpleGraph (Fin n),
∃ A : Matrix (Fin n) (Fin n) ℝ,
HasPattern G A ∧ MinimumDegree G ≤ n - A.rank
end
end RegistryProblems.OP_00252
Formalised by OpenAI Codex AI agents (Apache-2.0); reviewed by clemens-admin.
Available to match against in: Lean v4.33.1 with Mathlib v4.33.1.
Resolving this problem in Lean
Add the problems package as a dependency, import this problem's module, and prove the constant. Any published revision works.
In lakefile.toml:
[[require]] name = "RegistryProblems" git = "https://github.com/cthalhammer/registry-problems" rev = "753bebc58e3fee845f4fffec7d24e7c8cc2a689a"
In your proof:
import RegistryProblems.OP_00252 theorem resolution : RegistryProblems.Problem_OP_00252 := by sorry
In preprint.toml, mapping the claim to the declaration that establishes it:
[[statements]] label = "Theorem 1" lean = "resolution" latex = "..." problem = "OP-00252" claim = "full"
To disprove it instead, prove the negation and claim "disproof", or "counterexample" if the proof exhibits one:
theorem disproof : ¬ RegistryProblems.Problem_OP_00252 := by sorry
You can also write the statement out in full; the verifier checks it matches up to definitional equality. Partial results and reductions are not matched against this statement.
Resolution claims
Complete proof of the unchanged all-graph real symmetric delta target, with exact copied source closure and kernel trust. Independent full source/package reviews and actual isolated Linux Comparator/kernel verification are complete.
In 1987 Hiroshi Maehara conjectured that a graph can be represented by vectors considered adjacent when not orthogonal (a faithful orthogonal representation) in codimension the minimum degree of the graph. Without settling the conjecture, Làslò Lovàsz, Michael Saks, and Alexander Schrijver (LSS) showed that a codimension of vertex connectivity both suffices and is best possible under the additional assumption of …
By finding orthogonal representation for a family of simple connected called $δ$-graphs it is possible to show that $δ$-graphs satisfy delta conjecture. An extension of the argument to graphs of the form $\overline{P_{Δ(G)+2}\sqcup G}$ where $P_{Δ(G)+2}$ is a path and $G$ is a simple connected graph it is possible to find an orthogonal representation of $\overline{P_{Δ(G)+2}\sqcup G}$ in $\mathbb{R}^{Δ(G)+1}$. As …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-20 | Solution claimed → Lean verified | The registry's curators | SP-11: unrestricted real symmetric delta conjecture v1 recorded from OpenProblemsInNLA @ 5487945, SP-11/lean/. |
| 2026-10-08 | Needs verification → Solution claimed | clemens-admin | Listed with the record of its solution, unreviewed. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00252, "The delta conjecture for minimum symmetric rank", clopen.solutions.