← All problems

Open structure problem for the entanglement-assisted asymptotic spectrum of graphs

Determine the set X(G,≤∗)X(\mathcal{G},\leq^{*}) of all normalized graph parameters φ:G→R≥0\varphi:\mathcal{G}\to\mathbb{R}_{\geq 0} on finite graphs such that φ(K1)=1\varphi(K_1)=1, φ(∅)=0\varphi(\varnothing)=0, φ(G⊔H)=φ(G)+φ(H)\varphi(G\sqcup H)=\varphi(G)+\varphi(H), φ(G⊠H)=φ(G)φ(H)\varphi(G\boxtimes H)=\varphi(G)\varphi(H), and G≤∗HG\leq^{*}H implies φ(G)≤φ(H)\varphi(G)\leq\varphi(H), where ≤∗\leq^{*} denotes entanglement-assisted cohomomorphism and ⊠\boxtimes denotes the strong graph product. In particular, determine whether the spectrum consists only of the Lovász number ϑ\vartheta, or characterize all additional spectrum points.

References

Progress summary

Refreshed
Open · progress reported

A new paper claims many additional examples and settles several related questions, but the full structure of the spectrum remains unknown.

The problem asks for a description of all parameters in the entanglement-assisted asymptotic spectrum of graphs. Earlier work conjectured that the Lovász number might be the only such parameter, while also recording competing conjectures about related capacities.

Known results

  • The Lovász number is a spectrum point; the 2018 literature stated that no other classical points had been found and conjectured Θ∗(G)=ϑ(G)\Theta^*(G)=\vartheta(G) for every graph GG.
  • The spectrum gives the dual characterization Θ∗(G)=min⁡φ∈X(G,≤∗)φ(G)\Theta^*(G)=\min_{\varphi\in X(G,\leq^*)}\varphi(G).
  • Earlier work disproved equality between one-shot entanglement-assisted zero-error capacity and ⌊ϑ(G)⌋\lfloor\vartheta(G)\rfloor, while leaving the asymptotic gap open.

October 14, 2026 claimed progress

Mghirbi and Douglas introduce θα\theta_\alpha for 0≤α≤20\leq\alpha\leq2 and claim spectrum membership, Cmin⁡(C5)=log⁡2(5/2)C_{\min}(C_5)=\log_2(5/2), and resolutions of the pentagon and two simulation-rate links. These claims are not independently assessed in the retrieved evidence, and the paper does not claim a complete spectrum characterization.

Current status (as of October 2026): the spectrum has claimed new points and related conjectural links, but its complete structure and the claimed results remain unverified.

Sources

Solutions 0

No solutions have been posted yet.