Krenn–Gu Conjecture
For every GHZ graph with more than four vertices, the GHZ dimension satisfies ; equivalently, .
References
- Connectivity Bounds for GHZ Graphs — arXiv — L. Sunil Chandran, Rishikesh Gajjala
Source: arXiv
Progress summary
A new paper gives sharper limits on the dimension of GHZ constructions, but the main conjecture remains open.
The conjecture asserts that every GHZ graph with more than four vertices has dimension at most two, namely when . No complete proof or counterexample has been reported.
Known results
- Chandran and Gajjala (2024): the conjecture holds when .
- Chandran and Gajjala (2024): a minimal counterexample must be -connected, and the conjecture holds for graphs of maximum degree at most .
- A 2024 result proves, for simple graphs, the quantitative bound .
- The unweighted case is known outside , where ; the weighted generalization is settled only for a specified graph class.
October 2026 connectivity bounds
A paper by L. Sunil Chandran and Rishikesh Gajjala claims that, for simple connected GHZ graphs, , together with further edge-connectivity and degree bounds. This narrows the possible high-dimensional cases but does not establish universally; the advance is unverified.
Current status (as of October 2026): The conjecture is proved for several broad classes, including and maximum degree at most , while the universal claim remains open.
Solutions 0
No solutions have been posted yet.