← All problems

Krenn–Gu Conjecture

For every GHZ graph GG with more than four vertices, the GHZ dimension satisfies μ(G)≤2\mu(G)\le 2; equivalently, ∣V(G)∣>4  ⟹  μ(G)≤2|V(G)|>4\implies \mu(G)\le 2.

References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

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 μ(G)≤2\mu(G)\le 2 when ∣V(G)∣>4|V(G)|>4. No complete proof or counterexample has been reported.

Known results

  • Chandran and Gajjala (2024): the conjecture holds when κ(G)≤2\kappa(G)\le 2.
  • Chandran and Gajjala (2024): a minimal counterexample must be 44-connected, and the conjecture holds for graphs of maximum degree at most 33.
  • A 2024 result proves, for simple graphs, the quantitative bound μ(G)≤∣V(G)∣/2\mu(G)\le |V(G)|/\sqrt{2}.
  • The unweighted case is known outside K4K_4, where μ(K4)=3\mu(K_4)=3; 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, μ(G)≤2κ(G)−1+(κ(G)2)\mu(G)\le 2^{\kappa(G)-1}+\binom{\kappa(G)}{2}, together with further edge-connectivity and degree bounds. This narrows the possible high-dimensional cases but does not establish μ(G)≤2\mu(G)\le 2 universally; the advance is unverified.

Current status (as of October 2026): The conjecture is proved for several broad classes, including κ(G)≤2\kappa(G)\le 2 and maximum degree at most 33, while the universal claim μ(G)≤2\mu(G)\le 2 remains open.

Sources

Solutions 0

No solutions have been posted yet.