← All problems

Hedetniemi’s conjecture for Shannon OR-capacity

For every pair of sequences of finite graphs (Gn)n≥1(G_n)_{n\ge 1} and (Hn)n≥1(H_n)_{n\ge 1}, if COR(Gn)→∞C_{\mathrm{OR}}(G_n)\to\infty and COR(Hn)→∞C_{\mathrm{OR}}(H_n)\to\infty, must COR(Gn×Hn)→∞C_{\mathrm{OR}}(G_n\times H_n)\to\infty, where ×\times denotes the categorical graph product?

References

Progress summary

Refreshed
Open · progress reported

A new paper gives strong counterexamples to the exact identity, but the weaker question about whether products of increasingly capable graphs must remain capable is still open.

The problem asks whether Shannon OR-capacity of a graph product always equals the smaller capacity of its two factors. The ordinary identity is now known to fail; the surviving asymptotic version asks whether two sequences whose capacities diverge must have products with diverging capacity.

Known results

  • Simonyi (2021) recorded strict counterexamples to the identity and the general upper bound COR⁡(F×G)≤min⁡{COR⁡(F),COR⁡(G)}\operatorname{COR}(F \times G) \le \min\{\operatorname{COR}(F),\operatorname{COR}(G)\}.
  • Zuiddam’s asymptotic-spectrum framework gives a conditional reduction to another multiplicative, join-additive graph invariant.
  • The cases with smaller capacity 11 or 22 are settled; exact cases 33, 44, 55, and 66 remain open.

Recent counterexamples (date not stated)

Julius A. Zeiss reports that for every m≥7m \ge 7 there is a graph GG with COR(G×Km)≤m−14<m=COR(Km)<COR(G)C_{\mathrm{OR}}(G \times K_m) \le m-\frac14 < m = C_{\mathrm{OR}}(K_m) < C_{\mathrm{OR}}(G), alongside finite and asymptotic separations. The paper leaves open whether COR(Gn)→∞C_{\mathrm{OR}}(G_n) \to \infty and COR(Hn)→∞C_{\mathrm{OR}}(H_n) \to \infty force COR(Gn×Hn)→∞C_{\mathrm{OR}}(G_n \times H_n) \to \infty; these claims are unverified.

Current status (as of November 2026): The exact identity is claimed false, while the weaker divergent-capacity formulation and the exact cases 33 through 66 remain open; the new paper’s claims are unverified.

Sources

Solutions 0

No solutions have been posted yet.