betaFeedback

WorksMathematics

Hedetniemi's conjecture for Shannon OR-capacity: counterexamples and asymptotic separation

Abstract

We disprove the analogue of Hedetniemi's conjecture for Shannon OR-capacity, which asserts that the capacity of a categorical product equals the smaller capacity of its factors. For every sufficiently large complete graph, we construct a second graph of larger capacity such that their categorical product has capacity strictly below that of the complete graph. Further constructions show that, for every real threshold above an explicit constant, both factor capacities can exceed that threshold while the product capacity lies below it. We also construct graph pairs, again with one complete factor, whose capacities tend to infinity while their product capacity is subpolynomial in the smaller factor capacity. Whether the product capacity must nevertheless tend to infinity whenever both factor capacities do remains open. The proofs use spectral interpolation, which also yields a single spectral point violating Hedetniemi's identity throughout the complete-factor family. Finally, we identify the categorical product as the distinguishability graph of a random-switching model for zero-error communication. In this model, our constructions show that switching can reduce the zero-error rate to a vanishing fraction of the smaller individual rate.

Introduction

Can combining two graphs reduce the number of colours needed for a proper colouring? This question lies at the heart of Hedetniemi’s conjecture [15] for the categorical product. Throughout, graphs are finite, simple and nonempty. For graphs GG and HH, the categorical product G×HG \times H has vertex set V(G)×V(H)V(G) \times V(H), with (g,h)(g,h) adjacent to (g′,h′)(g',h') if gg′∈E(G)gg' \in E(G) and hh′∈E(H)hh' \in E(H). The classical conjecture asserted that

χ(G×H)=min⁡{χ(G),χ(H)}.\chi(G \times H) = \min\{\chi(G), \chi(H)\}.

El-Zahar and Sauer proved that equality holds whenever min⁡{χ(G),χ(H)}≤4\min\{\chi(G),\chi(H)\} \le4 [9]. The identity also holds for several natural graph classes, including products with a perfect factor [6], products of two Kneser graphs, and products of two Schrijver graphs [14]. Shitov disproved the conjecture in general [23]. Subsequent work established counterexamples with the smaller factor chromatic number equal to any prescribed integer at least 5 [26], completing the classification by this minimum. Once equality is known to fail, it is natural to ask how small the product chromatic number can be relative to the smaller factor chromatic number. He and Wigderson proved an asymptotic separation by showing that the chromatic number of the product can be smaller than the minimum factor chromatic number by a fixed positive proportion [16]. Zhu improved the asymptotic ratio to at most one half [33]. The refutation of the classical weak Hedetniemi conjecture is stronger still. Raanes’s construction [20], in the form discussed in Subsection 3.1, keeps the product chromatic number bounded while both factor chromatic numbers diverge.

Hedetniemi’s conjecture has a natural formulation in terms of graph homomorphisms, which also leads to analogous questions for other graph parameters. A graph homomorphism is an adjacency-preserving vertex map, and we write G→HG \to H when such a map exists. In particular, a proper nn-colouring is a homomorphism to KnK_n. A graph parameter pp is homomorphism-monotone if G→HG \to H implies p(G)≤p(H)p(G) \le p(H). The coordinate projections2 give p(G×H)≤min⁡{p(G),p(H)}p(G \times H) \le\min\{p(G),p(H)\}. Following Simonyi [24], we call the identity

p(G×H)=min⁡{p(G),p(H)}p(G \times H) = \min\{p(G),p(H)\}

the Hedetniemi-type equality for pp. The corresponding conjecture asks whether it holds for every pair of graphs G,HG,H. This identity holds for the fractional chromatic number [32] and the Lovász theta number of the complement [11], whereas it fails for the quantum chromatic number [29]. For surveys of the conjecture and related problems, see Zhu [31, 34], Sauer [21] and Tardif [25].

In this work, we study the analogue of Hedetniemi’s conjecture for Shannon OR-capacity. To define this parameter, we use the OR-product G∨HG \vee H, which has vertex set V(G)×V(H)V(G) \times V(H) and requires adjacency in at least one coordinate. This differs from the categorical product appearing in Hedetniemi’s conjecture. Write G∨rG^{\vee r} for the OR-product of rr copies of GG. The Shannon OR-capacity [22] is

COR(G)=lim⁡r→∞ω(G∨r)1/r,(1)C_{\mathrm{OR}}(G) = \lim_{r \to\infty} \omega(G^{\vee r})^{1/r}, \tag*{(1)}

where ω(G)∈N\omega(G) \in\mathbb{N} denotes the number of vertices in a largest complete subgraph of GG (the clique number), equivalently the largest size of a set of pairwise adjacent vertices. The limit exists by supermultiplicativity and Fekete’s lemma [10, 22]. Unlike the integer-valued chromatic number, the Shannon OR-capacity is real-valued and need not be integral [17].

Shannon OR-capacity originates in the problem of communicating over a finite discrete memoryless channel without feedback, with zero probability of decoding error [22]. When graph edges represent input symbols that cannot produce a common output, ω(G∨r)\omega(G^{\vee r}) is the largest number of messages that can be distinguished without error in rr channel uses. Consequently, log⁡2COR(G)\log_2 C_{\mathrm{OR}}(G) is the optimal zero-error rate in bits per use; see Csonka and Simonyi [7 Sec. I] for this formulation in terms of distinguishability graphs and OR-products.

The same channel can also be described by its confusability graph G‾\overline{G}, the complement of GG, in which two distinct input symbols are adjacent when they can produce a common output. This convention uses the strong (AND) product. For finite graphs GG and HH, the strong product G⊠HG \boxtimes H has vertex set V(G)×V(H)V(G) \times V(H), with two distinct pairs adjacent precisely when their entries are equal or adjacent in each coordinate. Let α(G)\alpha(G) denote the independence number of GG, that is, the largest size of a set of pairwise nonadjacent vertices. Write G⊠rG^{\boxtimes r} for the strong product of rr copies of GG. The ordinary Shannon capacity, also called Shannon AND-capacity, is [22, 24]

Θ(G)=lim⁡r→∞α(G⊠r)1/r.\Theta(G) = \lim_{r \to\infty} \alpha(G^{\boxtimes r})^{1/r}.

Complementation turns cliques in G∨rG^{\vee r} into independent sets in (G‾)⊠r(\overline{G})^{\boxtimes r}, and conversely. Thus the two conventions describe the same zero-error codes on complementary graphs, giving COR(G)=Θ(G‾)C_{\mathrm{OR}}(G) = \Theta(\overline{G}). Appendix § 13 illustrates the graph products and their relationships.

Like the chromatic number, Shannon OR-capacity is monotone under graph homomorphisms [34 Secs. 2 and 2.2]. Simonyi asked whether it satisfies the Hedetniemi-type equality for the categorical product [24].

Conjecture 1 (Shannon OR-capacity version of Hedetniemi’s conjecture). For every pair of graphs GG, HH,

COR⁡(G×H)=min⁡{COR⁡(G),COR⁡(H)}.\operatorname{COR}(G \times H) = \min\{\operatorname{COR}(G), \operatorname{COR}(H)\}.

Simonyi established the conjectured equality whenever one factor admits a homomorphism to the other, including every pair of odd cycles [24 Cor. 10 and Claim 16]. Equality also holds when both factors have capacity equal to their clique number. The factors may be chosen from perfect graphs, certain Kneser graphs, and complements of Kneser graphs [24 Prop. 15]. He also proposed graph pairs based on Paley graphs as potential sources of counterexamples to the Shannon OR-capacity conjecture [24 Sec. 4.3].

By analogy with the classical weak Hedetniemi conjecture for graph colouring, we formulate the following weaker asymptotic conjecture for Shannon OR-capacity.

Conjecture 2 (Weak Hedetniemi conjecture for Shannon OR-capacity). Along any sequence of graph pairs, if both graph capacities tend to infinity, then the capacity of their categorical product also tends to infinity.

Refuting this weaker conjecture would establish a much stronger failure of the exact identity. It would give graph pairs whose capacities both tend to infinity while their product capacity remains uniformly bounded.

Simonyi also connected Conjecture 1 to the asymptotic spectrum of graphs in the OR convention. Its parameters are homomorphism-monotone, additive under joins and multiplicative under the OR-product. This family includes the fractional chromatic number and the Lovász theta number of the complement. Via complementation, Zuiddam’s characterization connects this family to capacity by expressing Shannon OR-capacity as the minimum over the entire spectrum [35]. Simonyi used this characterization to prove that every counterexample for Shannon OR-capacity also violates the Hedetniemi-type equality for some parameter in the spectrum [24 Thm. 8]. We introduce the spectrum formally and explain the tools used in our constructions in Subsection 2.1.

Our results

We disprove Conjecture 1 even when one factor is a complete graph. For every integer m≥7m \ge7, Theorem 1 gives a graph of capacity greater than mm whose categorical product with KmK_m has capacity strictly below m=COR⁡(Km)m = \operatorname{COR}(K_m). We first explain the mechanism through a simple example at the beginning of § 3. Our graph pairs differ from Simonyi’s proposed candidates. We also construct a counterexample with both capacities below six (Theorem 2(1)). For every real threshold above an explicit constant slightly larger than six, we construct two graphs whose capacities exceed that threshold. Their product has capacity below it (Theorem 2(2)).

We make progress on the asymptotic question posed by the weak conjecture. Theorem 3 shows that, with one factor still complete, both graph capacities can tend to infinity while the product capacity is subpolynomial in the smaller graph capacity. Whether the product capacity can remain uniformly bounded is still open (Conjecture 2).

The interpolated spectral points used to bound the product capacities also witness failures of the Hedetniemi-type equality within the asymptotic spectrum. Thus the equality can fail even for homomorphism-monotone parameters that are additive under joins and multiplicative under the OR-product. In fact, one fixed spectral point violates the equality with a complete factor KmK_m for every integer m≥7m \ge7 (Theorem 4).

A further contribution is an operational formulation of the Shannon OR-capacity version of Hedetniemi’s conjecture. We show that the categorical product is the distinguishability graph of a zero-error communication task involving random switching between two channels (Lemma 5.1).

To our knowledge, this operational interpretation of the Shannon OR-capacity version of Hedetniemi’s conjecture has not previously been made explicit. Under this correspondence, the conjectured identity asserts that switching preserves the smaller individual zero-error rate. Our counterexamples therefore demonstrate that switching can impose an additional loss, with the retained fraction of that rate tending to zero in the asymptotic construction (see Theorems 5 and 6).

Methods. To obtain these counterexamples, we transfer spectral results for ordinary Shannon capacity to the OR convention by complementation. Zuiddam’s characterization [35] allows us to choose spectral bounds that are sharp on individual components and to derive capacity lower bounds from estimates valid for every spectral point. Vrana’s probabilistic refinement [27] supplies the spectral interpolation inequality (4) of Lemma 2.1, which combines bounds effective on different components into a single spectral point. This point bounds the capacity of the entire categorical product from above. Combining this bound with the lower bounds on the two factor capacities establishes the capacity counterexample. The same spectral point also witnesses failure of the Hedetniemi-type equality for that graph pair. A complementary pair of binary orthogonality graphs illustrates this mechanism. The sub-six refinement uses the same interpolation principle with explicit rational matrix certificates, compressed by graph symmetries. The asymptotic construction extends the mechanism to many components using Alon’s finite-field polynomial method [1].

Organization of the paper. § 3 presents the finite counterexamples: the simple example and its spectral argument, the complete-factor family in Subsection 2.2, and the sharper finite thresholds in Subsection 2.3. § 4 introduces the Shannon OR-capacity analogue of the Poljak–Rödl function, formulates the weak conjecture in these terms, and develops the asymptotic separation. § 5 collects the consequences for the asymptotic spectrum. § 6 gives an interpretation in terms of zero-error communication, and § 7 discusses open questions. Appendices § 12–§ 15 provide notation, graph-product conventions, proofs of the spectral tools and general interpolation bounds. Appendices § 16–§ 18 contain the finite constructions, refinements and exact certificates. Appendices § 19 and § 20 give the proofs of the asymptotic separation and the channel interpretation, respectively.

Finite counterexamples

We begin with a simple counterexample, proceeding in two steps. First, we construct a graph F9F_9 and show that COR(F9)≥128>9=COR(K9)C_{\mathrm{OR}}(F_9) \ge\sqrt{128} > 9 = C_{\mathrm{OR}}(K_9), so the smaller factor capacity is nine. We then outline a spectral argument giving COR(F9×K9)≤72<9C_{\mathrm{OR}}(F_9 \times K_9) \le\sqrt{72} < 9. The categorical product therefore has smaller capacity than either factor, contradicting Conjecture 1. We then refine the construction to obtain counterexamples at every integer minimum m≥7m \ge7, yielding Theorem 1. Finally, Subsection 2.3 develops further refinements for smaller capacities and real separating thresholds.

Let F2={0,1}\mathbb{F}_2 = \{0,1\} be the finite field with arithmetic modulo two. Among the 282^8 vectors in F28\mathbb{F}_2^8, exactly half contain an odd number of ones. Let U8U_8 be the graph whose vertices are these 128128 vectors, with distinct x,yx,y adjacent when x⋅y=0x \cdot y = 0 in F2\mathbb{F}_2. Its complement U‾8\overline{U}_8 joins exactly the distinct pairs that U8U_8 does not join. In the communication interpretation, vertices are input symbols, and adjacency means that two symbols can be distinguished without error in one use. More generally, ω(X∨r)\omega(X^{\vee r}) is the largest number of pairwise distinguishable words of length rr for a graph XX. Taking the rrth root of this number and then the limit as r→∞r \to\infty gives COR⁡(X)\operatorname{COR}(X), as in (1). Both U8U_8 and U‾8\overline{U}_8 have capacity eight by Lemma E.1.

Keep the two graphs as separate components, with no edges between them, and write F9=U8⊔U‾8F_9 = U_8 \sqcup\overline{U}_8 for their disjoint union. Each binary vector xx labels one vertex xU8x_{U_8} in the first component and one vertex xU‾8x_{\overline{U}_8} in the second. For each of the 128 labels, form the two-coordinate word

(xU8,xU‾8).(x_{U_8},x_{\overline{U}_8}).

Every word therefore uses the first component in its first coordinate and the second component in its second coordinate.

Recall that F9∨2=F9∨F9F_9^{\vee2} = F_9 \vee F_9 has two-coordinate words as vertices, with two words adjacent when their corresponding entries are adjacent in at least one coordinate. Take distinct labels x,yx,y. If xyxy is an edge of U8U_8, the first coordinates of their words are adjacent. Otherwise, xyxy is an edge of U‾8\overline{U}_8, so the second coordinates are adjacent. In either case, the words are adjacent in F9∨2F_9^{\vee2} and can be distinguished without error.

Every pair among the 128 distinct words is therefore adjacent, so these words form a complete subgraph K128K_{128} (a clique of size 128) of F9∨2F_9^{\vee2}. By supermultiplicativity and Fekete’s lemma, the limit defining COR⁡(X)\operatorname{COR}(X) equals sup⁡r≥1ω(X∨r)1/r\sup_{r\geq1}\omega(X^{\vee r})^{1/r}; see (C.1) in Appendix § 14. Thus any fixed word length gives a lower bound on capacity, and our two-coordinate code gives

ω(F9∨2)≥128,COR⁡(F9)≥ω(F9∨2)1/2≥128.\omega(F_9^{\vee2}) \geq128,\qquad\operatorname{COR}(F_9) \geq\omega(F_9^{\vee2})^{1/2} \geq\sqrt{128}.

Since COR⁡(K9)=9<128\operatorname{COR}(K_9) = 9 < \sqrt{128}, this establishes

min⁡{COR⁡(F9),COR⁡(K9)}=9.\min\{\operatorname{COR}(F_9),\operatorname{COR}(K_9)\} = 9.

To refute Conjecture 1 for the two factors F9F_9 and K9K_9, it remains to prove COR⁡(F9×K9)<9\operatorname{COR}(F_9 \times K_9) < 9. The spectral argument below uses graph parameters that bound capacity from above: by combining two such parameters, we obtain one whose value on both components of F9×K9F_9 \times K_9 is at most 72<9\sqrt{72} < 9.

The spectral argument

We first introduce the spectral tools needed for the product upper bound. We then apply them to prove COR⁡(F9×K9)<9\operatorname{COR}(F_9 \times K_9) < 9, completing our simple counterexample.

For finite graphs GG and HH, the join G⊕HG \oplus H is obtained from their disjoint union by adding all edges between V(G)V(G) and V(H)V(H).

The asymptotic spectrum depends on the chosen operations and comparison relation. Here we use graph join as addition, the OR-product as multiplication, and graph homomorphisms for comparison, following [24 Def. 6].

References

  1. [1]N. Alon, The Shannon capacity of a union, Combinatorica 18 (1998), 301–310. doi:10.1007/PL00009824.DOI
  2. [2]N. Alon, Graph powers, in: B. Bollobás (ed.), Contemporary Combinatorics, Bolyai Society Mathematical Studies 10, Springer and János Bolyai Mathematical Society, 2002, 11–28. Publisher page.
  3. [3]E. H. Bareiss, Sylvester’s identity and multistep integer-preserving Gaussian elimination, Mathematics of Computation 22 (1968), 565–578. doi:10.1090/S0025-5718-1968-0226829-0.DOI
  4. [4]A. Blasiak, A graph-theoretic approach to network coding, Ph.D. thesis, Cornell University, 2013. hdl:1813/34147.
  5. [5]B. Bukh and C. Cox, On a fractional version of Haemers’ bound, IEEE Transactions on Information Theory 65 (2019), 3340–3348. doi:10.1109/TIT.2018.2889108.DOI
  6. [6]S. A. Burr, P. Erdős and L. Lovász, On graphs of Ramsey type, Ars Combinatoria 1 (1976), 167–190. Original paper.
  7. [7]B. Csonka and G. Simonyi, Shannon capacity, Lovász theta number and the Mycielski construction, IEEE Transactions on Information Theory 70 (2024), no. 11, 7632–7646. doi:10.1109/TIT.2024.3394775.DOI
  8. [8]A. El Gamal and Y.-H. Kim, Network Information Theory, Cambridge University Press, 2011. doi:10.1017/CBO9781139030687.DOI
  9. [9]M. El-Zahar and N. Sauer, The chromatic number of the product of two 4-chromatic graphs is 4, Combinatorica 5 (1985), 121–126. doi:10.1007/BF02579374.
  10. [10]M. Fekete, Über die Verteilung der Wurzeln bei gewissen algebraischen Gleichungen mit ganzzahligen Koeffizienten, Mathematische Zeitschrift 17 (1923), 228–249. doi:10.1007/BF01504345.DOI
  11. [11]C. Godsil, D. E. Robertson, R. Šámal and S. Severini, Sabidussi versus Hedetniemi for three variations of the chromatic number, Combinatorica 36 (2016), 395–415. doi:10.1007/s00493-014-3132-1.DOI
  12. [12]R. E. Greenwood and A. M. Gleason, Combinatorial relations and chromatic graphs, Canadian Journal of Mathematics 7 (1955), 1–7. doi:10.4153/CJM-1955-001-4.DOI
  13. [13]W. H. Haemers, On some problems of Lovász concerning the Shannon capacity of a graph, IEEE Transactions on Information Theory 25 (1979), 231–232. doi:10.1109/TIT.1979.1056027.DOI
  14. [14]H. Hajiabolhassan and F. Meunier, Hedetniemi’s conjecture for Kneser hypergraphs, Journal of Combinatorial Theory, Series A 143 (2016), 42–55. doi:10.1016/j.jcta.2016.05.002.DOI
  15. [15]S. T. Hedetniemi, Homomorphisms of graphs and automata, Ph.D. thesis, University of Michigan, 1966.DOI
  16. [16]X. He and Y. Wigderson, Hedetniemi’s conjecture is asymptotically false, Journal of Combinatorial Theory, Series B 146 (2021), 485–494. doi:10.1016/j.jctb.2020.03.003.DOI
  17. [17]L. Lovász, On the Shannon capacity of a graph, IEEE Transactions on Information Theory 25 (1979), 1–7. doi:10.1109/TIT.1979.1055985.DOI
  18. [18]S. C. Polak, New methods in coding theory: Error-correcting codes and the Shannon capacity, Ph.D. thesis, University of Amsterdam, 2019. arXiv:2005.02945 (2020).arxiv.org/abs/2005.02945
  19. [19]S. Poljak and V. Rödl, On the arc-chromatic number of a digraph, Journal of Combinatorial Theory, Series B 31 (1981), 190–198. doi:10.1016/S0095-8956(81)80024-X.DOI
  20. [20]S. Raanes, Counterexamples to the weak Hedetniemi Conjecture, arXiv:2608.07818v1 (2026).arxiv.org/abs/2608.07818
  21. [21]N. Sauer, Hedetniemi’s conjecture – a survey, Discrete Mathematics 229 (2001), 261–292. doi:10.1016/S0012-365X(00)00213-2.DOI
  22. [22]C. E. Shannon, The zero error capacity of a noisy channel, IRE Transactions on Information Theory 2 (1956), 8–19. doi:10.1109/TIT.1956.1056798.DOI
  23. [23]Y. Shitov, Counterexamples to Hedetniemi’s conjecture, Annals of Mathematics 190 (2019), 663–667. doi:10.4007/annals.2019.190.2.6.DOI
  24. [24]G. Simonyi, Shannon capacity and the categorical product, Electronic Journal of Combinatorics 28 (2021), P1.51. doi:10.37236/9113.DOI
  25. [25]C. Tardif, Hedetniemi’s conjecture, 40 years later, Graph Theory Notes of New York 54 (2008), 46–57.
  26. [26]C. Tardif, The chromatic number of the product of 5-chromatic graphs can be 4, Combinatorica 43 (2007), 1067–1073. doi:10.1007/s00493-023-00047-2.
  27. [27]P. Vrana, Probabilistic refinement of the asymptotic spectrum of graphs, Combinatorica 41 (2021), 873–904. doi:10.1007/s00493-020-4324-5. Also arXiv:1903.01857v1.DOI
  28. [28]D. Zagier, Newman’s short proof of the prime number theorem, American Mathematical Monthly 104 (1997), 705–708. doi:10.2307/2975232.DOI
  29. [29]J. A. Zeiss, A counterexample to the quantum Hedetniemi conjecture, arXiv:2609.20690 (2026).arxiv.org/abs/2609.20690
  30. [30]J. A. Zeiss, Shannon OR-capacity: accompanying code and data, GitHub repository (2026). https://github.com/JuliusAZeiss/shannon-or-capacity-data.
  31. [31]X. Zhu, A survey on Hedetniemi’s conjecture, Taiwanese Journal of Mathematics 2 (1998), 1–24. doi:10.11650/twjm/1500406890.DOI
  32. [32]X. Zhu, The fractional version of Hedetniemi’s conjecture is true, European Journal of Combinatorics 32 (2011), 1168–1175. doi:10.1016/j.ejc.2011.03.004.DOI
  33. [33]X. Zhu, A note on the Poljak–Rödl function, Electronic Journal of Combinatorics 27 (2020), P3.2. doi:10.37236/9371.DOI
  34. [34]X. Zhu, A survey on Hedetniemi’s conjecture, Computer Science Review 58 (2025), 100794. doi:10.1016/j.cosrev.2025.100794. Also arXiv:2502.16078.DOI
  35. [35]J. Zuiddam, The asymptotic spectrum of graphs and the Shannon capacity, Combinatorica 39 (2019), 1173–1184. doi:10.1007/s00493-019-3992-5. Also arXiv:1807.00169v2.DOI

Paper details

vlnc:W_3ddbrmvy
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Codex

View statement
Looking for related papers…
Contents