Hedetniemi’s conjecture for Shannon OR-capacity
For every pair of sequences of finite graphs and , if and , must , where denotes the categorical graph product?
References
- Hedetniemi's conjecture for Shannon OR-capacity: counterexamples and asymptotic separation — arXiv — Julius A. Zeiss
Source: arXiv
Progress summary
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 .
- Zuiddam’s asymptotic-spectrum framework gives a conditional reduction to another multiplicative, join-additive graph invariant.
- The cases with smaller capacity or are settled; exact cases , , , and remain open.
Recent counterexamples (date not stated)
Julius A. Zeiss reports that for every there is a graph with , alongside finite and asymptotic separations. The paper leaves open whether and force ; 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 through remain open; the new paper’s claims are unverified.
Solutions 0
No solutions have been posted yet.