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 G G G and H H H , the categorical product G × H G \times H G × H has vertex set V ( G ) × V ( H ) V(G) \times V(H) V ( G ) × V ( H ) , with ( g , h ) (g,h) ( g , h ) adjacent to ( g ′ , h ′ ) (g',h') ( g ′ , h ′ ) if g g ′ ∈ E ( G ) gg' \in E(G) g g ′ ∈ E ( G ) and h h ′ ∈ E ( H ) hh' \in E(H) h h ′ ∈ E ( H ) . The classical conjecture asserted that
χ ( G × H ) = min { χ ( G ) , χ ( H ) } . \chi(G \times H) = \min\{\chi(G), \chi(H)\}. χ ( G × H ) = min { χ ( G ) , χ ( H )} .
El-Zahar and Sauer proved that equality holds whenever min { χ ( G ) , χ ( H ) } ≤ 4 \min\{\chi(G),\chi(H)\} \le4 min { χ ( G ) , χ ( H )} ≤ 4 [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 → H G \to H G → H when such a map exists. In particular, a proper n n n -colouring is a homomorphism to K n K_n K n . A graph parameter p p p is homomorphism-monotone if G → H G \to H G → H implies p ( G ) ≤ p ( H ) p(G) \le p(H) p ( G ) ≤ p ( H ) . The coordinate projections2 give p ( G × H ) ≤ min { p ( G ) , p ( H ) } p(G \times H) \le\min\{p(G),p(H)\} p ( G × H ) ≤ 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)\} p ( G × H ) = min { p ( G ) , p ( H )}
the Hedetniemi-type equality for p p p . The corresponding conjecture asks whether it holds for every pair of graphs G , H G,H G , 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 ∨ H G \vee H G ∨ H , which has vertex set V ( G ) × V ( H ) V(G) \times V(H) V ( G ) × V ( H ) and requires adjacency in at least one coordinate. This differs from the categorical product appearing in Hedetniemi’s conjecture. Write G ∨ r G^{\vee r} G ∨ r for the OR-product of r r r copies of G G G . The Shannon OR-capacity [22 ] is
C O R ( G ) = lim r → ∞ ω ( G ∨ r ) 1 / r , (1) C_{\mathrm{OR}}(G) = \lim_{r \to\infty} \omega(G^{\vee r})^{1/r}, \tag*{(1)} C OR ( G ) = r → ∞ lim ω ( G ∨ r ) 1/ r , (1)
where ω ( G ) ∈ N \omega(G) \in\mathbb{N} ω ( G ) ∈ N denotes the number of vertices in a largest complete subgraph of G G G (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}) ω ( G ∨ r ) is the largest number of messages that can be distinguished without error in r r r channel uses. Consequently, log 2 C O R ( G ) \log_2 C_{\mathrm{OR}}(G) log 2 C 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} G , the complement of G G G , 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 G G G and H H H , the strong product G ⊠ H G \boxtimes H G ⊠ H has vertex set V ( G ) × V ( H ) V(G) \times V(H) V ( G ) × V ( H ) , with two distinct pairs adjacent precisely when their entries are equal or adjacent in each coordinate. Let α ( G ) \alpha(G) α ( G ) denote the independence number of G G G , that is, the largest size of a set of pairwise nonadjacent vertices. Write G ⊠ r G^{\boxtimes r} G ⊠ r for the strong product of r r r copies of G G G . 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}. Θ ( G ) = r → ∞ lim α ( G ⊠ r ) 1/ r .
Complementation turns cliques in G ∨ r G^{\vee r} G ∨ r into independent sets in ( G ‾ ) ⊠ r (\overline{G})^{\boxtimes r} ( G ) ⊠ r , and conversely. Thus the two conventions describe the same zero-error codes on complementary graphs, giving C O R ( G ) = Θ ( G ‾ ) C_{\mathrm{OR}}(G) = \Theta(\overline{G}) C OR ( G ) = Θ ( 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 G G G , H H H ,
COR ( G × H ) = min { COR ( G ) , COR ( H ) } . \operatorname{COR}(G \times H) = \min\{\operatorname{COR}(G), \operatorname{COR}(H)\}. COR ( G × H ) = min { COR ( G ) , 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 ≥ 7 m \ge7 m ≥ 7 , Theorem 1 gives a graph of capacity greater than m m m whose categorical product with K m K_m K m has capacity strictly below m = COR ( K m ) m = \operatorname{COR}(K_m) m = 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 K m K_m K m for every integer m ≥ 7 m \ge7 m ≥ 7 (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 F 9 F_9 F 9 and show that C O R ( F 9 ) ≥ 128 > 9 = C O R ( K 9 ) C_{\mathrm{OR}}(F_9) \ge\sqrt{128} > 9 = C_{\mathrm{OR}}(K_9) C OR ( F 9 ) ≥ 128 > 9 = C OR ( K 9 ) , so the smaller factor capacity is nine. We then outline a spectral argument giving C O R ( F 9 × K 9 ) ≤ 72 < 9 C_{\mathrm{OR}}(F_9 \times K_9) \le\sqrt{72} < 9 C OR ( F 9 × K 9 ) ≤ 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 ≥ 7 m \ge7 m ≥ 7 , yielding Theorem 1. Finally, Subsection 2.3 develops further refinements for smaller capacities and real separating thresholds.
Let F 2 = { 0 , 1 } \mathbb{F}_2 = \{0,1\} F 2 = { 0 , 1 } be the finite field with arithmetic modulo two. Among the 2 8 2^8 2 8 vectors in F 2 8 \mathbb{F}_2^8 F 2 8 , exactly half contain an odd number of ones. Let U 8 U_8 U 8 be the graph whose vertices are these 128 128 128 vectors, with distinct x , y x,y x , y adjacent when x ⋅ y = 0 x \cdot y = 0 x ⋅ y = 0 in F 2 \mathbb{F}_2 F 2 . Its complement U ‾ 8 \overline{U}_8 U 8 joins exactly the distinct pairs that U 8 U_8 U 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}) ω ( X ∨ r ) is the largest number of pairwise distinguishable words of length r r r for a graph X X X . Taking the r r r th root of this number and then the limit as r → ∞ r \to\infty r → ∞ gives COR ( X ) \operatorname{COR}(X) COR ( X ) , as in (1) . Both U 8 U_8 U 8 and U ‾ 8 \overline{U}_8 U 8 have capacity eight by Lemma E.1.
Keep the two graphs as separate components, with no edges between them, and write F 9 = U 8 ⊔ U ‾ 8 F_9 = U_8 \sqcup\overline{U}_8 F 9 = U 8 ⊔ U 8 for their disjoint union. Each binary vector x x x labels one vertex x U 8 x_{U_8} x U 8 in the first component and one vertex x U ‾ 8 x_{\overline{U}_8} x U 8 in the second. For each of the 128 labels, form the two-coordinate word
( x U 8 , x U ‾ 8 ) . (x_{U_8},x_{\overline{U}_8}). ( x U 8 , x U 8 ) .
Every word therefore uses the first component in its first coordinate and the second component in its second coordinate.
Recall that F 9 ∨ 2 = F 9 ∨ F 9 F_9^{\vee2} = F_9 \vee F_9 F 9 ∨ 2 = F 9 ∨ 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 , y x,y x , y . If x y xy x y is an edge of U 8 U_8 U 8 , the first coordinates of their words are adjacent. Otherwise, x y xy x y is an edge of U ‾ 8 \overline{U}_8 U 8 , so the second coordinates are adjacent. In either case, the words are adjacent in F 9 ∨ 2 F_9^{\vee2} F 9 ∨ 2 and can be distinguished without error.
Every pair among the 128 distinct words is therefore adjacent, so these words form a complete subgraph K 128 K_{128} K 128 (a clique of size 128) of F 9 ∨ 2 F_9^{\vee2} F 9 ∨ 2 . By supermultiplicativity and Fekete’s lemma, the limit defining COR ( X ) \operatorname{COR}(X) COR ( X ) equals sup r ≥ 1 ω ( X ∨ r ) 1 / r \sup_{r\geq1}\omega(X^{\vee r})^{1/r} sup r ≥ 1 ω ( X ∨ 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
ω ( F 9 ∨ 2 ) ≥ 128 , COR ( F 9 ) ≥ ω ( F 9 ∨ 2 ) 1 / 2 ≥ 128 . \omega(F_9^{\vee2}) \geq128,\qquad\operatorname{COR}(F_9) \geq\omega(F_9^{\vee2})^{1/2} \geq\sqrt{128}. ω ( F 9 ∨ 2 ) ≥ 128 , COR ( F 9 ) ≥ ω ( F 9 ∨ 2 ) 1/2 ≥ 128 .
Since COR ( K 9 ) = 9 < 128 \operatorname{COR}(K_9) = 9 < \sqrt{128} COR ( K 9 ) = 9 < 128 , this establishes
min { COR ( F 9 ) , COR ( K 9 ) } = 9. \min\{\operatorname{COR}(F_9),\operatorname{COR}(K_9)\} = 9. min { COR ( F 9 ) , COR ( K 9 )} = 9.
To refute Conjecture 1 for the two factors F 9 F_9 F 9 and K 9 K_9 K 9 , it remains to prove COR ( F 9 × K 9 ) < 9 \operatorname{COR}(F_9 \times K_9) < 9 COR ( F 9 × 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 F 9 × K 9 F_9 \times K_9 F 9 × K 9 is at most 72 < 9 \sqrt{72} < 9 72 < 9 .
The spectral argument
We first introduce the spectral tools needed for the product upper bound. We then apply them to prove COR ( F 9 × K 9 ) < 9 \operatorname{COR}(F_9 \times K_9) < 9 COR ( F 9 × K 9 ) < 9 , completing our simple counterexample.
For finite graphs G G G and H H H , the join G ⊕ H G \oplus H G ⊕ H is obtained from their disjoint union by adding all edges between V ( G ) V(G) V ( G ) and V ( H ) 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] .
Definition (OR asymptotic spectrum). Let G \mathcal{G} G denote the class of finite simple nonempty graphs. The asymptotic spectrum of graphs in the OR convention , denoted by Δ O R \Delta_{\mathrm{OR}} Δ OR , consists of all graph invariants φ : G → R ≥ 0 \varphi:\mathcal{G}\to\mathbb{R}_{\geq0} φ : G → R ≥ 0 satisfying, for all G , H ∈ G G,H\in\mathcal{G} G , H ∈ G ,
φ ( K 1 ) = 1 (normalization), φ ( G ⊕ H ) = φ ( G ) + φ ( H ) (join additivity), φ ( G ∨ H ) = φ ( G ) φ ( H ) (OR multiplicativity), G → H ⟹ φ ( G ) ≤ φ ( H ) (homomorphism monotonicity). \begin{aligned}
\varphi(K_1)&=1 &&\text{(normalization),}\\
\varphi(G\oplus H)&=\varphi(G)+\varphi(H) &&\text{(join additivity),}\\
\varphi(G\vee H)&=\varphi(G)\varphi(H) &&\text{(OR multiplicativity),}\\
G\to H&\ \Longrightarrow\ \varphi(G)\leq\varphi(H) &&\text{(homomorphism monotonicity).}
\end{aligned} φ ( K 1 ) φ ( G ⊕ H ) φ ( G ∨ H ) G → H = 1 = φ ( G ) + φ ( H ) = φ ( G ) φ ( H ) ⟹ φ ( G ) ≤ φ ( H ) (normalization), (join additivity), (OR multiplicativity), (homomorphism monotonicity). Its elements are called OR spectral points .
Since K m K_m K m is the join of m m m copies of K 1 K_1 K 1 , normalization and join additivity give φ ( K m ) = m \varphi(K_m)=m φ ( K m ) = m . Moreover, a clique of size a a a in G ∨ r G^{\vee r} G ∨ r is a copy of K a K_a K a , whose inclusion gives a homomorphism K a → G ∨ r K_a\to G^{\vee r} K a → G ∨ r . Thus
a = φ ( K a ) ≤ φ ( G ∨ r ) = φ ( G ) r . a=\varphi(K_a)\leq\varphi(G^{\vee r})=\varphi(G)^r. a = φ ( K a ) ≤ φ ( G ∨ r ) = φ ( G ) r . Choosing a = ω ( G ∨ r ) a=\omega(G^{\vee r}) a = ω ( G ∨ r ) , taking r r r th roots, and letting r → ∞ r\to\infty r → ∞ shows that every spectral point bounds capacity from above: C O R ( G ) ≤ φ ( G ) C_{\mathrm{OR}}(G)\leq\varphi(G) C OR ( G ) ≤ φ ( G ) .
Zuiddam formulates the graph spectrum using disjoint union, the strong product, and monotonicity under homomorphisms between complements. Write f f f for a spectral point in this convention. The identities
G ⊕ H ‾ = G ‾ ∪ H ‾ , G ∨ H ‾ = G ‾ ⊠ H ‾ \overline{G\oplus H}=\overline{G}\cup\overline{H},\qquad
\overline{G\vee H}=\overline{G}\boxtimes\overline{H} G ⊕ H = G ∪ H , G ∨ H = G ⊠ H
show that the assignment φ ( G ) = f ( G ‾ ) \varphi(G)=f(\overline{G}) φ ( G ) = f ( G ) gives a bijection between his spectrum and Δ O R \Delta_{\mathrm{OR}} Δ OR . Cliques in G ∨ r G^{\vee r} G ∨ r are independent sets in ( G ‾ ) ⊠ r (\overline{G})^{\boxtimes r} ( G ) ⊠ r and conversely, so the capacity definitions give C O R ( G ) = Θ ( G ‾ ) C_{\mathrm{OR}}(G)=\Theta(\overline{G}) C OR ( G ) = Θ ( G ) . Applying Zuiddam’s capacity characterization [35 Thm. 1.1(ii)] to G ‾ \overline{G} G gives (2) below, including attainment of the minimum.
The next lemma collects this characterization, the maximum rule for disjoint unions, and a spectral interpolation inequality. Here the maximum rule means that a fixed spectral point takes the maximum of its values on the components of a disjoint union. The latter two statements follow from Vrana’s results [27 Prop. 4.3 and Thms. 1.1–1.2] , translated to the OR convention.
Lemma 2.1 (Spectral characterization and interpolation). For every graph X X X ,
C O R ( X ) = min φ ∈ Δ O R φ ( X ) . (2) C_{\mathrm{OR}}(X)=\min_{\varphi\in\Delta_{\mathrm{OR}}}\varphi(X). \tag*{(2)} C OR ( X ) = φ ∈ Δ OR min φ ( X ) . (2) Every φ ∈ Δ O R \varphi\in\Delta_{\mathrm{OR}} φ ∈ Δ OR satisfies
φ ( X ⊔ Y ) = max { φ ( X ) , φ ( Y ) } . (3) \varphi(X\sqcup Y)=\max\{\varphi(X),\varphi(Y)\}. \tag*{(3)} φ ( X ⊔ Y ) = max { φ ( X ) , φ ( Y )} . (3) The spectral interpolation inequality states that if φ 1 , … , φ k ∈ Δ O R \varphi_1,\ldots,\varphi_k\in\Delta_{\mathrm{OR}} φ 1 , … , φ k ∈ Δ OR and w j ≥ 0 w_j\geq0 w j ≥ 0 with ∑ j w j = 1 \sum_j w_j=1 ∑ j w j = 1 , then there is a single ψ ∈ Δ O R \psi\in\Delta_{\mathrm{OR}} ψ ∈ Δ OR such that
ψ ( X ) ≤ ∏ j = 1 k φ j ( X ) w j for every graph X . (4) \psi(X)\leq\prod_{j=1}^{k}\varphi_j(X)^{w_j}
\qquad\text{for every graph }X. \tag*{(4)} ψ ( X ) ≤ j = 1 ∏ k φ j ( X ) w j for every graph X . (4)
The proof of Lemma 2.1 is given in Appendix C.
We use these three statements together to bound the capacity of a disjoint union. Equation (2) lets us choose, for each graph X X X , a spectral point φ \varphi φ with φ ( X ) = C O R ( X ) \varphi(X)=C_{\mathrm{OR}}(X) φ ( X ) = C OR ( X ) ; this choice may depend on X X X . Thus different components may have different spectral points giving their best bounds. The spectral interpolation inequality (4) combines these points into one spectral point ψ \psi ψ whose values are bounded by the corresponding weighted geometric means. Because the same ψ \psi ψ works on every component, the maximum rule (3) gives
COR ( X ⊔ Y ) ≤ ψ ( X ⊔ Y ) = max { ψ ( X ) , ψ ( Y ) } . \operatorname{COR}(X \mathbin{\sqcup} Y) \leq\psi(X \mathbin{\sqcup} Y) = \max\{\psi(X),\psi(Y)\}. COR ( X ⊔ Y ) ≤ ψ ( X ⊔ Y ) = max { ψ ( X ) , ψ ( Y )} .
Hence a common upper bound on ψ ( X ) \psi(X) ψ ( X ) and ψ ( Y ) \psi(Y) ψ ( Y ) also bounds the capacity of their disjoint union.
Equation (2) also gives lower bounds: if φ ( X ) ≥ L \varphi(X) \geq L φ ( X ) ≥ L for every φ ∈ Δ O R \varphi\in\Delta_{\mathrm{OR}} φ ∈ Δ OR , then taking the minimum gives COR ( X ) ≥ L \operatorname{COR}(X) \geq L COR ( X ) ≥ L . We use this observation in Lemma E.4 .
We now return to the explicit simple counterexample introduced at the beginning of § 3 , with F 9 = U 8 ⊔ U ‾ 8 F_9 = U_8 \sqcup\overline{U}_8 F 9 = U 8 ⊔ U 8 and second factor K 9 K_9 K 9 . It remains to prove COR ( F 9 × K 9 ) < 9 \operatorname{COR}(F_9 \times K_9) < 9 COR ( F 9 × K 9 ) < 9 . Since COR ( U 8 ) = COR ( U ‾ 8 ) = 8 \operatorname{COR}(U_8) = \operatorname{COR}(\overline{U}_8) = 8 COR ( U 8 ) = COR ( U 8 ) = 8 , the attained minimum in (2) lets us choose spectral points φ 1 , φ 2 ∈ Δ O R \varphi_1,\varphi_2 \in\Delta_{\mathrm{OR}} φ 1 , φ 2 ∈ Δ OR satisfying
φ 1 ( U 8 ) = φ 2 ( U ‾ 8 ) = 8. \varphi_1(U_8) = \varphi_2(\overline{U}_8) = 8. φ 1 ( U 8 ) = φ 2 ( U 8 ) = 8.
On each component product, the projections to its two factors give the following bounds.
Table 1.
The two rows of the table interchange the bounds 8 and 9, so we choose equal interpolation weights to obtain the same bound on both components. Applying the spectral interpolation inequality (4) with k = 2 k = 2 k = 2 and w 1 = w 2 = 1 2 w_1 = w_2 = \frac{1}{2} w 1 = w 2 = 2 1 gives a single spectral point ψ ∈ Δ O R \psi\in\Delta_{\mathrm{OR}} ψ ∈ Δ OR such that
ψ ( X ) ≤ φ 1 ( X ) 1 / 2 φ 2 ( X ) 1 / 2 = φ 1 ( X ) φ 2 ( X ) \psi(X) \leq\varphi_1(X)^{1/2}\varphi_2(X)^{1/2} = \sqrt{\varphi_1(X)\varphi_2(X)} ψ ( X ) ≤ φ 1 ( X ) 1/2 φ 2 ( X ) 1/2 = φ 1 ( X ) φ 2 ( X )
for every graph X X X .
Applying this inequality to the two component products and using the bounds in the table gives
ψ ( U 8 × K 9 ) ≤ 8 ⋅ 9 = 72 , \psi(U_8 \times K_9) \leq\sqrt{8 \cdot9} = \sqrt{72}, ψ ( U 8 × K 9 ) ≤ 8 ⋅ 9 = 72 ,
ψ ( U ‾ 8 × K 9 ) ≤ 9 ⋅ 8 = 72 . \psi(\overline{U}_8 \times K_9) \leq\sqrt{9 \cdot8} = \sqrt{72}. ψ ( U 8 × K 9 ) ≤ 9 ⋅ 8 = 72 .
Both estimates hold for the same spectral point ψ \psi ψ , because the interpolation inequality holds for every graph X X X . The categorical product distributes over disjoint union. Since F 9 = U 8 ⊔ U ‾ 8 F_9 = U_8 \sqcup\overline{U}_8 F 9 = U 8 ⊔ U 8 , we have
F 9 × K 9 = ( U 8 × K 9 ) ⊔ ( U ‾ 8 × K 9 ) . F_9 \times K_9 = (U_8 \times K_9) \sqcup(\overline{U}_8 \times K_9). F 9 × K 9 = ( U 8 × K 9 ) ⊔ ( U 8 × K 9 ) .
Indeed, the product vertices split according to which component of F 9 F_9 F 9 contains their first coordinate. Adjacency in the categorical product requires adjacency between the first coordinates, so no edge can join these two groups. The maximum rule (3) therefore gives
COR ( F 9 × K 9 ) ≤ ψ ( F 9 × K 9 ) ≤ 72 < 9. (5) \operatorname{COR}(F_9 \times K_9) \leq\psi(F_9 \times K_9) \leq\sqrt{72} < 9. \tag*{(5)} COR ( F 9 × K 9 ) ≤ ψ ( F 9 × K 9 ) ≤ 72 < 9. (5)
Since nine is the smaller factor capacity, this disproves Conjecture 1.
Remark (Role of interpolation). The same spectral point must control both components: the maximum rule applies to each fixed spectral point, but not generally to capacity. Indeed, F 9 F_9 F 9 itself illustrates the distinction. Its two components each have capacity 8, whereas COR ( F 9 ) ≥ 128 > 8 \operatorname{COR}(F_9) \geq\sqrt{128} > 8 COR ( F 9 ) ≥ 128 > 8 . The same argument gives a general product bound: for arbitrary graphs A A A , B B B and every integer m ≥ 1 m \geq1 m ≥ 1 ,
COR ( ( A ⊔ B ) × K m ) ≤ m max { COR ( A ) , COR ( B ) } . \operatorname{COR}((A \sqcup B) \times K_m) \leq\sqrt{m\max\{\operatorname{COR}(A),\operatorname{COR}(B)\}}. COR (( A ⊔ B ) × K m ) ≤ m max { COR ( A ) , COR ( B )} .
The weighted form of this bound is proved in Lemma D.1 in Appendix § 15 .
Remark (Connected factors). Adding one vertex adjacent to every vertex of F 9 F_9 F 9 gives a connected graph G = F 9 ⊕ K 1 G = F_9 \oplus K_1 G = F 9 ⊕ K 1 on 257 vertices. Using Lemma E.2, Lemma D.1 with m = 10 m = 10 m = 10 , and Lemma D.3 , we obtain
COR ( G ) = 128 + 1 > 10 , COR ( G × K 10 ) ≤ 80 + 1 < 10 = COR ( K 10 ) . \operatorname{COR}(G) = \sqrt{128} + 1 > 10,\qquad\operatorname{COR}(G \times K_{10}) \le\sqrt{80} + 1 < 10 = \operatorname{COR}(K_{10}). COR ( G ) = 128 + 1 > 10 , COR ( G × K 10 ) ≤ 80 + 1 < 10 = COR ( K 10 ) .
Thus both factors in this counterexample are connected. Disconnectedness is therefore not essential to the failure of the product identity.
A family of counterexamples with a complete factor
We now refine the simple counterexample to obtain a family with complete factor K m K_m K m and smaller factor capacity exactly m m m for every integer m ≥ 7 m \ge7 m ≥ 7 . The proof follows essentially the same steps as above, using modified components and weighted spectral interpolation.
The starting case is m = 7 m = 7 m = 7 , the smallest integer minimum attained by our constructions. For this example, we replace U 8 U_8 U 8 by the analogous graph U 6 U_6 U 6 on the odd-weight vectors in F 2 6 \mathbb{F}_2^6 F 2 6 . Letting Q Q Q denote the 5-regular Clebsch graph on 16 vertices [12 ] , we form the first factor X 7 = U 6 ⊔ ( U 6 ⊕ Q ) X_7 = U_6 \sqcup(U_6 \oplus Q) X 7 = U 6 ⊔ ( U 6 ⊕ Q ) by joining Q Q Q to U 6 U_6 U 6 and taking the disjoint union with U 6 U_6 U 6 . The second factor is K 7 K_7 K 7 . Lemmas E.3 and E.4 supply the additional capacity estimates and the lower bound for the enlarged union. Together with the weighted product bound in Lemma D.1, derived from spectral interpolation (4) , these establish the counterexample with K 7 K_7 K 7 . For m > 7 m > 7 m > 7 , let X m X_m X m be obtained by joining K m − 7 K_{m-7} K m − 7 to each of the two components of X 7 X_7 X 7 . This gives a family X m X_m X m , with 2 m + 66 2m + 66 2 m + 66 vertices for each integer m ≥ 7 m \ge7 m ≥ 7 , establishing the following result.
Theorem 1 (Counterexamples with a complete factor). For every integer m ≥ 7 m \ge7 m ≥ 7 , there exists a graph G G G such that
COR ( G × K m ) ≤ m − 1 4 < m = COR ( K m ) < COR ( G ) . \operatorname{COR}(G \times K_m) \le m - \frac{1}{4} < m = \operatorname{COR}(K_m) < \operatorname{COR}(G). COR ( G × K m ) ≤ m − 4 1 < m = COR ( K m ) < COR ( G ) .
The full construction and proof of Theorem 1 are given in Subsection E.3.
Sharper finite thresholds
In Theorem 1, the complete factor K m K_m K m has capacity m m m , while the other factor has larger capacity. The smaller factor capacity is therefore exactly m m m , and the construction works for every integer m ≥ 7 m \ge7 m ≥ 7 . We now drop the requirement that one factor be complete and show that the Hedetniemi identity can fail even when both factor capacities are below six. We also obtain counterexamples across a continuous range: for every real t ≥ 6.0101 t \ge6.0101 t ≥ 6.0101 , there are graphs whose factor capacities both exceed t t t , while their product capacity is strictly below t t t . We call such a value t t t a separating threshold for the pair.
Theorem 2 (Sharper finite thresholds).
There exist graphs G G G , H H H with COR ( G ) , COR ( H ) < 6 \operatorname{COR}(G), \operatorname{COR}(H) < 6 COR ( G ) , COR ( H ) < 6 such that
COR ( G × H ) < 27 ≤ min { COR ( G ) , COR ( H ) } . \operatorname{COR}(G \times H) < \sqrt{27} \le\min\{\operatorname{COR}(G), \operatorname{COR}(H)\}. COR ( G × H ) < 27 ≤ min { COR ( G ) , COR ( H )} . For every real t ≥ 6.0101 t \ge6.0101 t ≥ 6.0101 , there exist graphs G G G , H H H such that
COR ( G × H ) < t < min { COR ( G ) , COR ( H ) } . \operatorname{COR}(G \times H) < t < \min\{\operatorname{COR}(G), \operatorname{COR}(H)\}. COR ( G × H ) < t < min { COR ( G ) , COR ( H )} .
Parts (1) and (2) are proved in Appendix § 17 (Lemma F.1) and Appendix § 18 (Theorem G.1), respectively.
Remark. By Lemma C.2 , Theorem 2(2) already implies that counterexamples exist with smaller factor capacity exactly m m m for every integer m ≥ 7 m \ge7 m ≥ 7 . The construction for Theorem 1 additionally provides a complete factor K m K_m K m , a partner on 2 m + 66 2m+66 2 m + 66 vertices, and product capacity at most m − 1 4 m-\frac{1}{4} m − 4 1 . Allowing noncomplete factors lowers the smaller factor capacity to a value close to 27 ≈ 5.196 \sqrt{27} \approx5.196 27 ≈ 5.196 , but the smallest exact integer minimum attained by our constructions remains seven: these refinements do not settle the cases 3, 4, 5, 6.
The refinements in Theorem 2 strengthen the two ingredients needed for a counterexample: lower bounds on the factor capacities and an upper bound on the product capacity. For part (1), explicit codes of 27 words in two coordinates show that both factor capacities are at least 27 \sqrt{27} 27 . Exact matrix certificates provide the spectral estimates that interpolation (4) combines to place the product capacity strictly below this value. The same certificates bound both factor capacities below six, giving a counterexample at smaller capacities than the complete-factor construction. The graphs G , H G,H G , H have 54 and 27 vertices, respectively, and the certificates give the sharper estimate C O R ( G × H ) < 5.193957 C_{\mathrm{OR}}(G \times H) < 5.193957 C OR ( G × H ) < 5.193957 . Thus this pair separates every threshold t ∈ [ 5.193957 , 27 ) t \in[5.193957,\sqrt{27}) t ∈ [ 5.193957 , 27 ) . The graph and certificate data, together with their exact verification, are given in Appendix § 17 .
For part (2), the aim is to cover an entire range of thresholds. A single graph pair can already separate a whole interval: bounds of the form
C O R ( G × H ) ≤ U < L ≤ min { C O R ( G ) , C O R ( H ) } C_{\mathrm{OR}}(G \times H) \le U < L \le\min\{C_{\mathrm{OR}}(G),C_{\mathrm{OR}}(H)\} C OR ( G × H ) ≤ U < L ≤ min { C OR ( G ) , C OR ( H )}
show that the same pair separates every threshold t ∈ ( U , L ) t \in(U,L) t ∈ ( U , L ) . Its product capacity is below t t t , while both factor capacities are above t t t . We call ( U , L ) (U,L) ( U , L ) a range of separating thresholds for the pair.
We first choose the interpolation weight for an initial graph pair to minimize the larger of the two component bounds. This gives a product bound below 6.0101, while the smaller factor capacity is 37 \sqrt{37} 37 . The pair therefore separates every threshold in [ 6.0101 , 37 ) [6.0101,\sqrt{37}) [ 6.0101 , 37 ) . We choose several graph pairs whose ranges of separating thresholds overlap, so that every threshold in a continuous interval is covered. Lemma G.2 extends these examples by joining a copy of K j K_j K j to each of the two components of the first factor and to the second factor. For these constructions, a range ( U , L ) (U,L) ( U , L ) becomes ( U + j , L + j ) (U+j,L+j) ( U + j , L + j ) for every integer j ≥ 0 j \ge0 j ≥ 0 . The original covered interval has length greater than one, so shifting it repeatedly by one leaves no gaps in the covered thresholds. This construction therefore extends the coverage to every threshold above the interval’s lower endpoint. Combining this coverage with the initial pair yields counterexamples for every t ≥ 6.0101 t \ge6.0101 t ≥ 6.0101 .
These constructions do not connect the uniform range to the interval near 27 \sqrt{27} 27 . They establish strict capacity gaps for finite examples. We next ask how small the product capacity can remain as both factor capacities grow.
Asymptotic separation and the weak conjecture
Motivated by the classical weak Hedetniemi conjecture for graph colouring, we formulate an analogous conjecture for Shannon OR-capacity. It asks whether the capacity of the categorical product must tend to infinity whenever both factor capacities do. We introduce the corresponding analogue of the Poljak–Rödl function and prove a subpolynomial upper bound, leaving this conjecture open.
Extremal functions and the weak conjecture
The classical weak Hedetniemi conjecture concerns the Poljak–Rödl function [19 ]
f χ ( n ) = min { χ ( G × H ) : χ ( G ) ≥ n , χ ( H ) ≥ n } , f_{\chi}(n)=\min\{\chi(G \times H):\chi(G)\ge n,\ \chi(H)\ge n\}, f χ ( n ) = min { χ ( G × H ) : χ ( G ) ≥ n , χ ( H ) ≥ n } ,
and asks whether f χ ( n ) → ∞ f_{\chi}(n) \to\infty f χ ( n ) → ∞ . Raanes proposed a refutation using products of bounded chromatic number [20 ] . A correction to Raanes’s argument preserves his general proof strategy and gives f χ ( n ) ≤ 5 f_{\chi}(n) \le5 f χ ( n ) ≤ 5 for every n n n , so the product remains five-colourable while both factor chromatic numbers grow without bound.3 This conclusion does not transfer directly to Shannon OR-capacity. Although C O R ( G ) ≤ χ ( G ) C_{\mathrm{OR}}(G) \le\chi(G) C OR ( G ) ≤ χ ( G ) , a large chromatic number does not by itself establish a large capacity.
For real t ≥ 1 t \ge1 t ≥ 1 , define the Shannon OR-capacity analogue
f C ( t ) = inf { C O R ( G × H ) : C O R ( G ) ≥ t , C O R ( H ) ≥ t } . (6) f_C(t) = \inf\{C_{\mathrm{OR}}(G \times H) : C_{\mathrm{OR}}(G) \ge t,\ C_{\mathrm{OR}}(H) \ge t\}. \tag*{(6)} f C ( t ) = inf { C OR ( G × H ) : C OR ( G ) ≥ t , C OR ( H ) ≥ t } . (6)
Here t t t is a lower bound on both factor capacities; neither capacity is required to equal t t t . The function f C f_C f C is nondecreasing, as verified in Appendix § 14 . In terms of this function, Conjecture 2 takes the form
lim t → ∞ f C ( t ) = ∞ . \lim_{t\to\infty} f_C(t) = \infty. t → ∞ lim f C ( t ) = ∞.
Equivalently, for every B > 0 B > 0 B > 0 there is a T > 0 T > 0 T > 0 such that, for all graphs G G G , H H H ,
min { C O R ( G ) , C O R ( H ) } ≥ T ⟹ C O R ( G × H ) > B . (7) \min\{C_{\mathrm{OR}}(G), C_{\mathrm{OR}}(H)\} \ge T \quad\Longrightarrow\quad C_{\mathrm{OR}}(G \times H) > B. \tag*{(7)} min { C OR ( G ) , C OR ( H )} ≥ T ⟹ C OR ( G × H ) > B . (7)
The equivalence of these formulations is justified in Appendix § 14 .
Asymptotic separation
Although we do not refute the weak Hedetniemi conjecture for Shannon OR-capacity, we make progress in this direction by proving an asymptotic separation: both factor capacities can tend to infinity while the product capacity is subpolynomial in the smaller factor capacity. This holds even when both factors are connected and one is complete.
Theorem 3 (Asymptotic separation). For every sufficiently large integer m m m , there is a connected graph G m G_m G m satisfying
C O R ( G m ) ≥ m + 1 , C O R ( G m × K m ) ≤ exp ( ( log m ) 1 / 2 + o ( 1 ) ) . (8) C_{\mathrm{OR}}(G_m) \ge m + 1,\qquad C_{\mathrm{OR}}(G_m \times K_m) \le\exp((\log m)^{1/2+o(1)}). \tag*{(8)} C OR ( G m ) ≥ m + 1 , C OR ( G m × K m ) ≤ exp (( log m ) 1/2 + o ( 1 ) ) . (8)
The smaller factor capacity is therefore exactly m m m . More precisely, there are absolute constants K > 0 K > 0 K > 0 and m 0 m_0 m 0 such that these graphs can be chosen, for every integer m ≥ m 0 m \ge m_0 m ≥ m 0 , to satisfy
C O R ( G m × K m ) ≤ exp ( K log m ( log log m ) 2 log log log m ) . (9) C_{\mathrm{OR}}(G_m \times K_m) \le\exp\left(K\sqrt{\log m}\frac{(\log\log m)^2}{\log\log\log m}\right). \tag*{(9)} C OR ( G m × K m ) ≤ exp ( K log m log log log m ( log log m ) 2 ) . (9)
Consequently, for every δ > 0 \delta> 0 δ > 0 and all sufficiently large real t t t ,
f C ( t ) ≤ exp ( ( log t ) 1 / 2 + δ ) . (10) f_C(t) \le\exp((\log t)^{1/2+\delta}). \tag*{(10)} f C ( t ) ≤ exp (( log t ) 1/2 + δ ) . (10)
The full construction, parameter choices, and proof of Theorem 3 are given in Appendix § 19 . In particular, f C ( t ) = t o ( 1 ) f_C(t) = t^{o(1)} f C ( t ) = t o ( 1 ) , so
lim t → ∞ f C ( t ) t = 0 , lim t → ∞ log f C ( t ) log t = 0. (11) \lim_{t\to\infty}\frac{f_C(t)}{t}=0,\qquad\lim_{t\to\infty}\frac{\log f_C(t)}{\log t}=0. \tag*{(11)} t → ∞ lim t f C ( t ) = 0 , t → ∞ lim log t log f C ( t ) = 0. (11)
Consequently, any lower bound for f C ( t ) f_C(t) f C ( t ) that tends to infinity must grow more slowly than every fixed positive power of t t t .
The idea behind the proof of Theorem 3 is to construct graphs with large capacities whose categorical product has much smaller capacity. One factor is again the complete graph K m K_m K m , with COR ( K m ) = m \operatorname{COR}(K_m)=m COR ( K m ) = m . We now construct the other factor with capacity at least m m m , so that the smaller factor capacity is exactly m m m .
The construction replaces the complementary pair U 8 , U ‾ 8 U_8,\overline{U}_8 U 8 , U 8 from § 3 with a family of graphs on a common set of n n n vertex labels, chosen so that every pair of distinct labels is adjacent in at least one graph; equivalently, their edge sets together cover all edges of K n K_n K n . Lemma H.1 provides such a family of N N N graphs. Let F F F be their disjoint union. Write x i x_i x i for the copy of vertex label x x x in the i i i th graph of the disjoint union F F F . For each label x x x , form the length-N N N word ( x 1 , … , x N ) (x_1,\ldots,x_N) ( x 1 , … , x N ) , using one vertex from each graph in this fixed order.
For distinct labels x , y x,y x , y , this covering condition gives a graph in which they are adjacent. If this is the i i i th graph, then x i x_i x i and y i y_i y i are adjacent in F F F , so the corresponding words are adjacent in their i i i th coordinate and hence in F ∨ N F^{\vee N} F ∨ N . Since this holds for every pair of distinct labels, the n n n words form a clique of size n n n . By (C.1) in Appendix § 14 ,
COR ( F ) ≥ ω ( F ∨ N ) 1 / N ≥ n 1 / N . \operatorname{COR}(F)\geq\omega(F^{\vee N})^{1/N}\geq n^{1/N}. COR ( F ) ≥ ω ( F ∨ N ) 1/ N ≥ n 1/ N .
We choose the construction parameters as functions of m m m so that n 1 / N ≥ m n^{1/N}\geq m n 1/ N ≥ m . Thus COR ( F ) ≥ m \operatorname{COR}(F)\geq m COR ( F ) ≥ m , and since COR ( K m ) = m \operatorname{COR}(K_m)=m COR ( K m ) = m , the smaller factor capacity is exactly m m m :
min { COR ( F ) , COR ( K m ) } = m . \min\{\operatorname{COR}(F),\operatorname{COR}(K_m)\}=m. min { COR ( F ) , COR ( K m )} = m .
To bound the product capacity, we use spectral points associated with k k k finite fields. For each graph in the family, Lemma H.1 supplies matrices of rank at most D D D over k − h k-h k − h of these fields. These matrices have diagonal entries 1 1 1 and vanish on the edges of that graph, so Lemma C.1 bounds the corresponding spectral values by D D D . We call the remaining h h h fields exceptional; the bound D D D is not required there, and these fields may depend on the graph. For the product of each graph with K m K_m K m , projection to that graph retains the bound D D D in its nonexceptional fields, while projection to K m K_m K m gives the bound m m m in its exceptional fields. Equal-weight spectral interpolation ((4) ) produces a single spectral point controlling all these products. Since F × K m F\times K_m F × K m is their disjoint union, applying the maximum rule to this spectral point gives, as formalized in Lemma D.2 ,
COR ( F × K m ) ≤ D 1 − h / k m h / k . \operatorname{COR}(F\times K_m)\leq D^{1-h/k}m^{h/k}. COR ( F × K m ) ≤ D 1 − h / k m h / k .
The gain comes from making the fraction h / k h/k h / k of exceptional fields tend to zero. The same parameter choices that ensure n 1 / N ≥ m n^{1/N}\geq m n 1/ N ≥ m , and hence COR ( F ) ≥ m \operatorname{COR}(F)\geq m COR ( F ) ≥ m , also give D = m o ( 1 ) D=m^{o(1)} D = m o ( 1 ) and h / k = o ( 1 ) h/k=o(1) h / k = o ( 1 ) . Thus the smaller factor capacity is exactly m m m , whereas the product capacity is subpolynomial in m m m .
Remark (Connected factors). To obtain the connected factor in Theorem 3 , add one universal vertex to F F F and set G m = F ⊕ K 1 G_m=F\mathbin{\oplus}K_1 G m = F ⊕ K 1 . By Lemma D.3 ,
COR ( G m ) = COR ( F ) + 1 ≥ m + 1 , COR ( G m × K m ) ≤ COR ( F × K m ) + 1. \operatorname{COR}(G_m)=\operatorname{COR}(F)+1\geq m+1,\qquad\operatorname{COR}(G_m\times K_m)\leq\operatorname{COR}(F\times K_m)+1. COR ( G m ) = COR ( F ) + 1 ≥ m + 1 , COR ( G m × K m ) ≤ COR ( F × K m ) + 1.
Thus the smaller factor capacity remains exactly m m m , while the product capacity remains subpolynomial in m m m .
The quantitative choices in Appendix § 19 yield the bound in Theorem 3 .
The upper bound in Theorem 3 tends to infinity and therefore does not resolve Conjecture 2. A refutation would require an absolute constant B B B and graph pairs ( G n , H n ) (G_n,H_n) ( G n , H n ) with
min { COR ( G n ) , COR ( H n ) } ⟶ ∞ , COR ( G n × H n ) ≤ B for every n . \min\{\operatorname{COR}(G_n),\operatorname{COR}(H_n)\}\longrightarrow\infty,\qquad\operatorname{COR}(G_n\times H_n)\leq B\quad\text{for every }n. min { COR ( G n ) , COR ( H n )} ⟶ ∞ , COR ( G n × H n ) ≤ B for every n .
Conversely, proving the conjecture would require a lower bound tending to infinity for f C f_C f C , which our argument does not provide. The equivalence between failure of Conjecture 2 and the existence of such a sequence is proved in Appendix § 14 .
Consequences for the asymptotic spectrum
Our counterexamples show that even a graph parameter satisfying all the defining properties of a spectral point can assign a categorical product a smaller value than either factor. This follows from Simonyi’s theorem: every failure of Hedetniemi’s identity for Shannon OR-capacity yields a failure for some point of the asymptotic spectrum Δ O R \Delta_{\mathrm{OR}} Δ OR introduced in Subsection 2.1 [24 Thm. 8] ; see also Zhu’s survey [34 Sec. 2.2] . In general, the witnessing point may depend on the graph pair. For the complete-factor family in Subsection 2.2, we obtain a stronger uniform conclusion: spectral interpolation (4) supplies one fixed spectral point that witnesses failure for every member.
Corollary 4 (Failure of Hedetniemi’s identity in the asymptotic spectrum). There exists a spectral point ψ ∈ Δ O R \psi\in\Delta_{\mathrm{OR}} ψ ∈ Δ OR such that, for every integer m ≥ 7 m \ge7 m ≥ 7 , there is a graph G m G_m G m satisfying
ψ ( G m × K m ) < m = min { ψ ( G m ) , ψ ( K m ) } . \psi(G_m \times K_m) < m = \min\{\psi(G_m),\psi(K_m)\}. ψ ( G m × K m ) < m = min { ψ ( G m ) , ψ ( K m )} . The proof follows from the fixed spectral point constructed for Theorem 1 and is given in Subsection E.3.
Thus homomorphism monotonicity, additivity under joins, and multiplicativity under the OR-product do not imply Hedetniemi’s identity for the categorical product, even when one factor is complete. This contrasts with the fractional chromatic number and the Lovász theta number of the complement, two spectral points for which the identity holds [32 , 11 ] .
Operational interpretation
The categorical product has a natural interpretation in zero-error communication: a sender supplies inputs to two channels, and a random switch determines which output reaches the receiver. Under this interpretation, our counterexamples show that switching can reduce the communication rate below what either channel supports individually.
For a finite discrete memoryless channel W W W , let D ( W ) D(W) D ( W ) be its distinguishability graph : vertices are inputs, and two inputs are adjacent when their possible output sets are disjoint. Write M 0 ( W , n ) M_0(W,n) M 0 ( W , n ) for the largest number of messages that can be transmitted with zero error in n n n uses without feedback. Shannon’s coding relations [22 ] , expressed in the distinguishability-graph convention of Csóka and Simonyi [7 Sec. I] , give
M 0 ( W , n ) = ω ( D ( W ) ∨ n ) , M_0(W,n) = \omega(D(W)^{\vee n}), M 0 ( W , n ) = ω ( D ( W ) ∨ n ) ,
R 0 ( W ) = sup n ≥ 1 log 2 M 0 ( W , n ) n = log 2 C O R ( D ( W ) ) . (12) R_0(W) = \sup_{n \ge1} \frac{\log_2 M_0(W,n)}{n} = \log_2 \operatorname{C}_{\mathrm{OR}}(D(W)). \tag*{(12)} R 0 ( W ) = n ≥ 1 sup n log 2 M 0 ( W , n ) = log 2 C OR ( D ( W )) . (12)
Here R 0 ( W ) R_0(W) R 0 ( W ) is measured in bits per use. Every finite graph is the distinguishability graph of some channel; see Alon [2 Sec. 2] for the equivalent statement for confusability graphs. An explicit realization is given in Appendix § 20 .
Let A \mathcal{A} A and B \mathcal{B} B be finite input alphabets, and let Y \mathcal{Y} Y and Z \mathcal{Z} Z be finite output alphabets. Consider channels W G : A → Y W_G : \mathcal{A} \to\mathcal{Y} W G : A → Y and W H : B → Z W_H : \mathcal{B} \to\mathcal{Z} W H : B → Z with distinguishability graphs G G G and H H H . Before transmission, the sender fixes for each message a sequence of n n n input pairs ( a i , b i ) ∈ A × B (a_i,b_i) \in\mathcal{A} \times\mathcal{B} ( a i , b i ) ∈ A × B , where i = 1 , … , n i = 1,\ldots,n i = 1 , … , n labels the channel use. At use i i i , the inputs a i a_i a i and b i b_i b i are supplied to W G W_G W G and W H W_H W H , respectively. No information about which channel was selected or what output it produced is returned to the sender during transmission. For each message, the sender may choose any sequence of input pairs from ( A × B ) n (\mathcal{A} \times\mathcal{B})^n ( A × B ) n . At each use, independently of the message, channel randomness and previous uses, a switch selects the first channel with probability p ∈ ( 0 , 1 ) p \in(0,1) p ∈ ( 0 , 1 ) and the second otherwise. The receiver observes the selected channel and its output. The resulting memoryless channel W s w W_{\mathrm{sw}} W sw has input alphabet A × B \mathcal{A} \times\mathcal{B} A × B and output alphabet ( { 0 } × Y ) ∪ ( { 1 } × Z ) (\{0\} \times\mathcal{Y}) \cup(\{1\} \times\mathcal{Z}) ({ 0 } × Y ) ∪ ({ 1 } × Z ) . An output ( s , u ) (s,u) ( s , u ) records the selected channel (s = 0 s=0 s = 0 for W G W_G W G and s = 1 s=1 s = 1 for W H W_H W H ) and its output u u u . For each input ( a , b ) ∈ A × B (a,b) \in\mathcal{A} \times\mathcal{B} ( a , b ) ∈ A × B , the probability of receiving ( s , u ) (s,u) ( s , u ) is
W s w ( ( s , u ) ∣ ( a , b ) ) = { p W G ( u ∣ a ) , s = 0 , u ∈ Y , ( 1 − p ) W H ( u ∣ b ) , s = 1 , u ∈ Z . W_{\mathrm{sw}}((s,u) \mid(a,b)) =
\begin{cases}
pW_G(u \mid a), & s=0,\quad u \in\mathcal{Y},\\
(1-p)W_H(u \mid b), & s=1,\quad u \in\mathcal{Z}.
\end{cases} W sw (( s , u ) ∣ ( a , b )) = { p W G ( u ∣ a ) , ( 1 − p ) W H ( u ∣ b ) , s = 0 , u ∈ Y , s = 1 , u ∈ Z .
Zero-error decoding must succeed for every message and every possible switch and output sequence. This is a state-dependent channel with state information available only to the receiver [8 Sec. 7.4] . For message j j j , write ( a i ( j ) , b i ( j ) ) (a_i(j),b_i(j)) ( a i ( j ) , b i ( j )) for the input pair at use i i i , and ( S i , U i ) (S_i,U_i) ( S i , U i ) for the corresponding random labelled output. Figure 1 illustrates the task.
Figure 1. Random switching between two channels. The receiver observes the selected channel and its output, and decoding must succeed for every possible switch and output sequence. OpenAI Codex assisted with preparation of the TikZ source.
Proposition 5.1 (Random switching realizes the categorical product). For every p ∈ ( 0 , 1 ) p \in(0,1) p ∈ ( 0 , 1 ) ,
D ( W s w ) = G × H . (13) D(W_{\mathrm{sw}}) = G \times H. \tag*{(13)} D ( W sw ) = G × H . (13) Consequently, for every n ≥ 1 n \ge1 n ≥ 1 ,
M 0 ( W s w , n ) = ω ( ( G × H ) ∨ n ) , R 0 ( W s w ) = log 2 COR ( G × H ) . M_0(W_{\mathrm{sw}},n) = \omega\left((G \times H)^{\vee n}\right), \qquad R_0(W_{\mathrm{sw}}) = \log_2 \operatorname{COR}(G \times H). M 0 ( W sw , n ) = ω ( ( G × H ) ∨ n ) , R 0 ( W sw ) = log 2 COR ( G × H ) . Both quantities are independent of p p p .
Indeed, two paired inputs are distinguishable precisely when their component inputs are distinguishable in both channels. This gives the categorical product for a single use, whereas the OR-power governs repeated uses. The full proof is given in Appendix § 20 .
Since every finite graph has a channel realization, the Shannon OR-capacity version of Hedetniemi’s conjecture is therefore equivalent to the assertion that
R 0 ( W s w ) = min { R 0 ( W G ) , R 0 ( W H ) } (14) R_0(W_{\mathrm{sw}}) = \min\{R_0(W_G), R_0(W_H)\} \tag*{(14)} R 0 ( W sw ) = min { R 0 ( W G ) , R 0 ( W H )} (14)
for every pair of channels. Our counterexamples show that this equality can fail even when one channel is noiseless.
Such a loss does not occur for ordinary vanishing-error capacity, denoted by C S h C_{\mathrm{Sh}} C Sh . Indeed, the same switching model satisfies
C S h ( W s w ) = p C S h ( W G ) + ( 1 − p ) C S h ( W H ) , C_{\mathrm{Sh}}(W_{\mathrm{sw}})=pC_{\mathrm{Sh}}(W_G)+(1-p)C_{\mathrm{Sh}}(W_H), C Sh ( W sw ) = p C Sh ( W G ) + ( 1 − p ) C Sh ( W H ) ,
which is at least the smaller component capacity. Appendix § 20 proves this identity. Zero-error communication must also accommodate arbitrarily unlikely switch sequences, which accounts for both the additional loss and its independence from p p p .
Return to the simple pair F 9 , K 9 F_9,K_9 F 9 , K 9 from § 3 . Let W F W_F W F realize F 9 F_9 F 9 , and let W 9 W_9 W 9 be a noiseless nine-symbol channel. For every p ∈ ( 0 , 1 ) p \in(0,1) p ∈ ( 0 , 1 ) ,
R 0 ( W F ) = 1 2 log 2 128 > log 2 9 = R 0 ( W 9 ) , R_0(W_F)=\frac{1}{2}\log_2 128>\log_2 9=R_0(W_9), R 0 ( W F ) = 2 1 log 2 128 > log 2 9 = R 0 ( W 9 ) ,
R 0 ( W s w ) ≤ 1 2 log 2 72 < log 2 9. (15) R_0(W_{\mathrm{sw}})\leq\frac{1}{2}\log_2 72<\log_2 9. \tag*{(15)} R 0 ( W sw ) ≤ 2 1 log 2 72 < log 2 9. (15)
The loss is already visible in two uses:
M 0 ( W F , 2 ) = 128 , M 0 ( W 9 , 2 ) = 81 , M 0 ( W s w , 2 ) ≤ 72. (16) M_0(W_F,2)=128,\qquad M_0(W_9,2)=81,\qquad M_0(W_{\mathrm{sw}},2)\leq72. \tag*{(16)} M 0 ( W F , 2 ) = 128 , M 0 ( W 9 , 2 ) = 81 , M 0 ( W sw , 2 ) ≤ 72. (16)
Thus either channel individually can transmit 81 messages without error in two uses, whereas their switched combination can transmit at most 72. The bounds follow from the explicit two-coordinate code and the capacity estimates for F 9 F_9 F 9 and F 9 × K 9 F_9 \times K_9 F 9 × K 9 ; the details are given in Appendix § 20 .
Theorems 1 and 2 give the following broader coding consequences.
Corollary 5 (Finite loss under switching). In each part, the channels are chosen independently of p p p , and the conclusions hold for every p ∈ ( 0 , 1 ) p \in(0,1) p ∈ ( 0 , 1 ) .
For every integer m ≥ 7 m \geq7 m ≥ 7 , there are channels W G , W m W_G,W_m W G , W m , with W m W_m W m noiseless on m m m symbols, such that
R 0 ( W s w ) ≤ log 2 ( m − 1 4 ) < log 2 m = R 0 ( W m ) < R 0 ( W G ) . R_0(W_{\mathrm{sw}})\leq\log_2\left(m-\frac{1}{4}\right)<\log_2m=R_0(W_m)<R_0(W_G). R 0 ( W sw ) ≤ log 2 ( m − 4 1 ) < log 2 m = R 0 ( W m ) < R 0 ( W G ) . There are channels W G , W H W_G,W_H W G , W H with both individual zero-error rates below log 2 6 \log_2 6 log 2 6 such that
R 0 ( W s w ) < 1 2 log 2 27 ≤ min { R 0 ( W G ) , R 0 ( W H ) } . R_0(W_{\mathrm{sw}})<\frac{1}{2}\log_2 27\leq\min\{R_0(W_G),R_0(W_H)\}. R 0 ( W sw ) < 2 1 log 2 27 ≤ min { R 0 ( W G ) , R 0 ( W H )} . Each channel admits a zero-error code of 27 messages in two uses, whereas the switched channel admits at most 26.
For every real target rate r ≥ log 2 ( 6.0101 ) r \geq\log_2(6.0101) r ≥ log 2 ( 6.0101 ) , there are channels W G , W H W_G,W_H W G , W H such that
R 0 ( W s w ) < r < min { R 0 ( W G ) , R 0 ( W H ) } . R_0(W_{\mathrm{sw}})<r<\min\{R_0(W_G),R_0(W_H)\}. R 0 ( W sw ) < r < min { R 0 ( W G ) , R 0 ( W H )} .
The proof is given in Appendix § 20 . These finite examples establish strict loss and locate it across a range of rates. The asymptotic construction shows how severe the relative loss can become along a growing family of channels. Here m m m indexes a family of channels. For each fixed m m m , the zero-error capacities already allow codes of arbitrarily large block length; the limit m → ∞ m \to\infty m → ∞ concerns the channel family.
Corollary 6 (Asymptotic loss under switching). For every sufficiently large integer m m m , there are channels W G m W_{G_m} W G m and W m W_m W m , with W m W_m W m noiseless on m m m symbols, whose smaller individual zero-error rate is
R m = min { R 0 ( W G m ) , R 0 ( W m ) } = log 2 m . R_m=\min\{R_0(W_{G_m}),R_0(W_m)\}=\log_2 m. R m = min { R 0 ( W G m ) , R 0 ( W m )} = log 2 m . For every p ∈ ( 0 , 1 ) p\in(0,1) p ∈ ( 0 , 1 ) , their switched channel satisfies
R 0 ( W s w , m ) ≤ R m 1 / 2 + o ( 1 ) , R 0 ( W s w , m ) R m ⟶ 0 ( m → ∞ ) . (17) R_0(W_{\mathrm{sw},m})\leq R_m^{1/2+o(1)},\qquad\frac{R_0(W_{\mathrm{sw},m})}{R_m}\longrightarrow0\quad(m\to\infty). \tag*{(17)} R 0 ( W sw , m ) ≤ R m 1/2 + o ( 1 ) , R m R 0 ( W sw , m ) ⟶ 0 ( m → ∞ ) . (17) The proof is given in Appendix § 20 .
Switching can severely reduce the zero-error communication rate compared with using either channel alone. In our construction, both individual rates grow without bound, yet switching reduces the achievable rate to an arbitrarily small fraction of the smaller individual rate. This does not establish whether the switched rate itself remains bounded.
Discussion
We have shown that the Shannon OR-capacity of a categorical product can be strictly smaller than the capacity of either factor. This disproves the Shannon OR-capacity version of Hedetniemi’s conjecture. For every integer m ≥ 7 m\geq7 m ≥ 7 , we construct a counterexample in which one factor is the complete graph K m K_m K m and the other has capacity greater than m m m . We also give a counterexample in which both factor capacities are below six.
Our constructions also show that the product identity can fail for parameters in the asymptotic spectrum. One fixed spectral point witnesses this failure throughout the complete-factor family. In the operational interpretation, our results mean that random switching between two channels can reduce the zero-error communication rate below both individual rates. This loss already appears in the number of messages that can be transmitted without error in just two uses. Along our asymptotic family, both individual rates grow without bound while the fraction of the smaller rate retained under switching tends to zero.
Several questions remain at smaller capacities. The product identity holds whenever the smaller factor capacity is 1 or 2 [24 Rem. 5] . Whether it holds when the smaller factor capacity is exactly 3, 4, 5, or 6 remains open.
The first unresolved integer case is therefore the following.
Question 1 (Capacity three). Do all graphs G , H G,H G , H satisfy
min { C O R ( G ) , C O R ( H ) } = 3 ⟹ C O R ( G × H ) = 3 ? \min\{C_{\mathrm{OR}}(G),C_{\mathrm{OR}}(H)\}=3\ \Longrightarrow\ C_{\mathrm{OR}}(G\times H)=3? min { C OR ( G ) , C OR ( H )} = 3 ⟹ C OR ( G × H ) = 3 ?
Thus, the smallest integer value of the smaller factor capacity admitting a counterexample lies between 3 and 7. Determining this value, and whether counterexamples exist at every larger integer value, remains open.
Since Shannon OR-capacity need not be an integer, there is also a separate question about real thresholds: for which real numbers t t t can both factor capacities exceed t t t while the product capacity is below t t t ? Our constructions establish this for a small interval of thresholds immediately below 27 \sqrt{27} 27 , and for every threshold above an explicit constant slightly larger than 6. We do not yet have a complete description of these thresholds or a continuous range connecting the two ranges above. These results do not require either factor capacity to equal t t t . In particular, the example with both capacities below six does not resolve the exact integer cases 3, 4, 5, 6.
At large capacities, we prove that both factor capacities can tend to infinity while the product capacity remains below every fixed positive power of the smaller factor capacity, once that capacity is sufficiently large. This is possible even with connected factors and one complete factor.
The weak Hedetniemi conjecture for Shannon OR-capacity nevertheless remains open. It asks whether the product capacity must tend to infinity whenever both factor capacities do. To disprove it, one would need graph pairs whose factor capacities tend to infinity while their product capacities stay below one fixed constant. Our asymptotic bound does not establish this, and we also do not prove that the product capacity must diverge.
Acknowledgements
The author acknowledges support from the European Research Council (ERC Grant Agreement No. 948139) and from the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy – EXC 2004/2 – 390534769 (ML4Q-2). The funders had no role in the research, preparation of the manuscript, or decision to submit the article for publication.
Declaration of competing interest
The author declares no competing interests.
Data and code availability
The graph definitions, finite codes and exact certificates are included in the supplementary appendices. The accompanying public repository [30 ] provides the verification programs, machine-readable graph and certificate data, and instructions for reproducing the finite checks. These programs use only the Python standard library. No numerical solver is needed to verify the certificates.
Declaration of generative AI and AI-assisted technologies
The author used OpenAI Codex (OpenAI) to assist with mathematical exploration, developing and reviewing arguments, literature searches, preparation of the manuscript and TikZ figures, and development and review of verification code. The verification subsection of Appendix § 17 describes the computational checks and the role of AI assistance. The author takes full responsibility for the content, accuracy, originality and integrity of the manuscript, including all AI-assisted material.
Notation and conventions
This appendix collects the notation and conventions used throughout the paper. It provides a reference for the graph operations, capacity parameters and asymptotic estimates in the main text.
All graphs are finite, simple and nonempty. A graph homomorphism is a map f : V ( G ) → V ( H ) f: V(G) \to V(H) f : V ( G ) → V ( H ) such that x y ∈ E ( G ) xy \in E(G) x y ∈ E ( G ) implies f ( x ) f ( y ) ∈ E ( H ) f(x)f(y) \in E(H) f ( x ) f ( y ) ∈ E ( H ) ; it need not be injective. Graphs are homomorphically equivalent if homomorphisms exist in both directions. A real-valued graph invariant p p p is homomorphism-monotone if G → H G \to H G → H implies p ( G ) ≤ p ( H ) p(G) \le p(H) p ( G ) ≤ p ( H ) . Such invariants agree on homomorphically equivalent graphs; examples include ω \omega ω , χ \chi χ and C O R \mathrm{COR} COR .
Logarithms in asymptotic estimates are natural; communication rates use log 2 \log_2 log 2 and are measured in bits per channel use. For a real-valued function a a a and a positive function b b b , the notation a = O ( b ) a = O(b) a = O ( b ) means that ∣ a ∣ / b |a|/b ∣ a ∣/ b remains bounded, a = o ( b ) a = o(b) a = o ( b ) means a / b → 0 a/b \to0 a / b → 0 , and a ∼ b a \sim b a ∼ b means a / b → 1 a/b \to1 a / b → 1 , as the indicated parameter tends to infinity. In particular, for a ( t ) ≥ 1 a(t) \ge1 a ( t ) ≥ 1 , a ( t ) = t o ( 1 ) a(t) = t^{o(1)} a ( t ) = t o ( 1 ) means log a ( t ) / log t → 0 \log a(t)/\log t \to0 log a ( t ) / log t → 0 and describes growth slower than every fixed positive power of t t t .
Table 2.
Graph products
This appendix compares the categorical, OR and strong graph products and explains their relation under complementation. These distinctions underlie the capacity arguments in § 3 and the channel interpretation in § 6 .
All three graph products have vertex set V ( G ) × V ( H ) V(G) \times V(H) V ( G ) × V ( H ) . The strong product permits adjacent pairs to share one coordinate, whereas the categorical product requires adjacency in both.
Complementation relates the OR and strong products through
G ∨ H ‾ = G ‾ ⊠ H ‾ , ω ( G ∨ r ) = α ( ( G ‾ ) ⊠ r ) . \overline{G \vee H} = \overline{G} \boxtimes\overline{H}, \qquad\omega(G^{\vee r}) = \alpha\left((\overline{G})^{\boxtimes r}\right). G ∨ H = G ⊠ H , ω ( G ∨ r ) = α ( ( G ) ⊠ r ) .
Indeed, two distinct pairs are nonadjacent in the OR-product precisely when, in each coordinate, their entries are equal or adjacent in the complementary graph. Cliques become independent sets under complementation. Taking r r r th roots and limits in the capacity definitions gives C O R ( G ) = Θ ( G ‾ ) C_{\mathrm{OR}}(G) = \Theta(\overline{G}) C OR ( G ) = Θ ( G ) , as used in Subsec. 2.1; see Simonyi [24, Sec. 2].
In the distinguishability convention, adjacent inputs can be distinguished with zero error. Two words are distinguishable if this holds in at least one coordinate. Thus a clique in G ∨ r G^{\vee r} G ∨ r is a zero-error code for r r r channel uses, and log 2 C O R ( G ) \log_{2} C_{\mathrm{OR}}(G) log 2 C OR ( G ) is the asymptotic communication rate. Equivalently, the same code is an independent set in the strong power of the confusability graph G ‾ \overline{G} G . The categorical product is the operation tested by Hedetniemi’s identity, as in the framework of Zhu [34, Secs. 2 and 2.2]. Fig. B.1 compares the three products and illustrates the complement relation.
Figure B.1. Three products of G = K 2 G = K_{2} G = K 2 and H = P 3 H = P_{3} H = P 3 on the same six vertices. Solid edges form the categorical product; dashed edges are added in the AND-product and dotted edges in the OR-product. Below, complementing panel (c) gives G ‾ ⊠ H ‾ \overline{G} \boxtimes\overline{H} G ⊠ H , with two edges and two isolated vertices. Its factors are complemented, so it differs from panel (b). These graphs illustrate the definitions and are not counterexamples. OpenAI Codex assisted with preparation of the TikZ source.
Capacity and the asymptotic spectrum
This appendix establishes the basic capacity properties and spectral tools used in the main text. It supplies the proof of Lem. 2.1 , together with the facts about joins and thresholds needed for the finite and asymptotic results.
For a r = ω ( X ∨ r ) a_r=\omega(X^{\vee r}) a r = ω ( X ∨ r ) , concatenating every word in a largest clique of X ∨ r X^{\vee r} X ∨ r with every word in a largest clique of X ∨ s X^{\vee s} X ∨ s gives a r a s a_ra_s a r a s pairwise distinguishable words of length r + s r+s r + s . Thus a r + s ≥ a r a s a_{r+s}\ge a_ra_s a r + s ≥ a r a s , and 1 ≤ a r ≤ ∣ V ( X ) ∣ r 1\le a_r\le|V(X)|^r 1 ≤ a r ≤ ∣ V ( X ) ∣ r . Fekete’s lemma applied to log a r \log a_r log a r therefore gives
C O R ( X ) = lim r → ∞ a r 1 / r = sup r ≥ 1 a r 1 / r . (18) \mathrm{C}_{\mathrm{OR}}(X)=\lim_{r\to\infty}a_r^{1/r}=\sup_{r\ge1}a_r^{1/r}. \tag*{(18)} C OR ( X ) = r → ∞ lim a r 1/ r = r ≥ 1 sup a r 1/ r . (18)
In particular, taking the supremum of finite-block rates agrees with the limiting rate used in Supplementary App. I.
Applying a graph homomorphism coordinatewise gives a homomorphism between the corresponding OR-powers. A homomorphism into a simple graph is injective on every clique, so
X ⟶ Y ⟹ C O R ( X ) ≤ C O R ( Y ) . X\longrightarrow Y\quad\Longrightarrow\quad\mathrm{C}_{\mathrm{OR}}(X)\le\mathrm{C}_{\mathrm{OR}}(Y). X ⟶ Y ⟹ C OR ( X ) ≤ C OR ( Y ) .
In particular, C O R ( K m ) = m \mathrm{C}_{\mathrm{OR}}(K_m)=m C OR ( K m ) = m , and the product projections imply C O R ( X × Y ) ≤ min { C O R ( X ) , C O R ( Y ) } \mathrm{C}_{\mathrm{OR}}(X\times Y)\le\min\{\mathrm{C}_{\mathrm{OR}}(X),\mathrm{C}_{\mathrm{OR}}(Y)\} C OR ( X × Y ) ≤ min { C OR ( X ) , C OR ( Y )} . For completeness, this is equality when the smaller factor capacity is 1 or 2 [24 Rem. 5] . A graph has capacity 1 exactly when it is edgeless. If the smaller capacity is 2, both factors contain an edge, so their product contains an edge and has capacity at least 2. The projection bound completes both cases.
The clique and coloring homomorphisms also give ω ( X ) ≤ C O R ( X ) ≤ χ ( X ) \omega(X)\le\mathrm{C}_{\mathrm{OR}}(X)\le\chi(X) ω ( X ) ≤ C OR ( X ) ≤ χ ( X ) . If f : X → Y f:X\to Y f : X → Y is a homomorphism, then x ↦ ( x , f ( x ) ) x\mapsto(x,f(x)) x ↦ ( x , f ( x )) is a homomorphism X → X × Y X\to X\times Y X → X × Y ; together with projection, this proves the equality recalled in the introduction. If both factors have capacity equal to their clique number, pair vertices of their maximum cliques to obtain a clique of size min { ω ( X ) , ω ( Y ) } \min\{\omega(X),\omega(Y)\} min { ω ( X ) , ω ( Y )} in X × Y X\times Y X × Y , proving that positive case as well.
The asymptotic spectrum and the spectral characterization used below are introduced in Subsec. 2.1. We give the proof of the spectral lemma here, including the interpolation step based on Vrana’s probabilistic refinement.
Proof of Lem. 2.1 . Eq. (2) , including attainment, is Zuiddam’s spectrum theorem [35 Thm. 1.1(ii)] , translated by complementation to the OR convention. Since X ⊔ Y = X ⊕ Y X\sqcup Y=X\oplus Y X ⊔ Y = X ⊕ Y , Eq. (3) is the same translation of Vrana’s maximum rule for joins [27 Prop. 4.3] .
We spell out how the spectral interpolation inequality (4) follows from Vrana’s probabilistic refinement. Set f j ( Y ) = φ j ( Y ‾ ) f_j(Y)=\varphi_j(\overline{Y}) f j ( Y ) = φ j ( Y ) , so that f j f_j f j is a spectral point in the usual confusability convention. Let F j ( Y , P ) F_j(Y,P) F j ( Y , P ) be its logarithmic probabilistic refinement, with logarithms to base two and P P P a probability distribution on V ( Y ) V(Y) V ( Y ) . Let T n , ε ( P ) T_{n,\varepsilon}(P) T n , ε ( P ) be the set of words in V ( Y ) n V(Y)^n V ( Y ) n for which the frequency of each vertex v v v differs from P ( v ) P(v) P ( v ) by at most ε \varepsilon ε . Writing Y ⊠ n [ T ] Y^{\boxtimes n}[T] Y ⊠ n [ T ] for the subgraph induced by a set of words T T T , the refinement is
F j ( Y , P ) = lim ε ↓ 0 lim sup n → ∞ 1 n log 2 f j ( Y ⊠ n [ T n , ε ( P ) ] ) . F_j(Y,P)=\lim_{\varepsilon\downarrow0}\limsup_{n\to\infty}\frac{1}{n}\log_2 f_j\left(Y^{\boxtimes n}[T_{n,\varepsilon}(P)]\right). F j ( Y , P ) = ε ↓ 0 lim n → ∞ lim sup n 1 log 2 f j ( Y ⊠ n [ T n , ε ( P )] ) .
It thus measures the asymptotic logarithmic value per coordinate when the empirical vertex distribution approaches P P P . Vrana’s Theorems 1.1–1.2 [27 ] identify spectral points with their logarithmic probabilistic refinements and give the inverse formula
f j ( Y ) = max P 2 F j ( Y , P ) . f_j(Y)=\max_P 2^{F_j(Y,P)}. f j ( Y ) = P max 2 F j ( Y , P ) .
The same characterization shows that these refinements form a convex set: its defining inequalities are affine in the refinement. Consequently F = ∑ j w j F j F=\sum_j w_jF_j F = ∑ j w j F j is the refinement of a single spectral point f f f . This assertion concerns functions of all pairs ( Y , P ) (Y,P) ( Y , P ) , so the same f f f is used for every graph. Returning to the OR convention, put ψ ( X ) = f ‾ ( X ) \psi(X)=\overline{f}(X) ψ ( X ) = f ( X ) . Then
ψ ( X ) = max P 2 ∑ j w j F j ‾ ( X , P ) ≤ ∏ j ( max P 2 F j ‾ ( X , P ) ) w j = ∏ j φ j ( X ) w j . \psi(X)=\max_{P}2^{\sum_j w_j\overline{F_j}(X,P)}\leq\prod_j\left(\max_{P}2^{\overline{F_j}(X,P)}\right)^{w_j}=\prod_j\varphi_j(X)^{w_j}. ψ ( X ) = P max 2 ∑ j w j F j ( X , P ) ≤ j ∏ ( P max 2 F j ( X , P ) ) w j = j ∏ φ j ( X ) w j .
The same ψ \psi ψ works for all X X X . This does not require the pointwise geometric mean of the original spectral points to be spectral. The result numbers in this proof refer to the arXiv versions listed in the bibliography. □
Complementary fractional Haemers bounds turn matrix-rank estimates into spectral upper bounds. A d d d -dimensional fitting matrix for a graph Y Y Y over a field K \mathbb{K} K is a block matrix M M M , indexed by V ( Y ) × V ( Y ) V(Y)\times V(Y) V ( Y ) × V ( Y ) , with d × d d\times d d × d identity matrices as diagonal blocks and zero blocks on distinct nonadjacent pairs. The fractional Haemers bound, introduced by Blasiak [4 Sec. 2.2] , is the infimum of rank K ( M ) / d \operatorname{rank}_{\mathbb{K}}(M)/d rank K ( M ) / d over all such matrices and all positive integers d d d .
Lemma C.1 (Fractional Haemers spectral bounds). For every field K \mathbb{K} K , the parameter
φ K ( X ) = H f K ( X ‾ ) \varphi_{\mathbb{K}}(X)=\mathcal{H}^{\mathbb{K}}_f(\overline{X}) φ K ( X ) = H f K ( X ) belongs to Δ O R \Delta_{\mathrm{OR}} Δ OR . In particular, if a scalar matrix M M M indexed by V ( X ) V(X) V ( X ) has diagonal entries 1 1 1 and vanishes on edges of X X X , then
φ K ( X ) ≤ rank K ( M ) . \varphi_{\mathbb{K}}(X)\leq\operatorname{rank}_{\mathbb{K}}(M). φ K ( X ) ≤ rank K ( M ) .
Proof. Spectral membership is the complementary form of the fractional Haemers result recorded in the arXiv version of [35 Sec. 5.2.2] ; its multiplicativity is proved in [5 Thm. 3] . The matrix in the statement is an admissible fitting matrix for X X X with block size 1 1 1 . □
Fractional colourings. Let I ( X ) \mathcal{I}(X) I ( X ) be the family of independent sets of X X X , that is, vertex sets containing no edge. A fractional colouring assigns weights w I ≥ 0 w_I\geq0 w I ≥ 0 to these sets such that ∑ I ∋ v w I ≥ 1 \sum_{I\ni v}w_I\geq1 ∑ I ∋ v w I ≥ 1 for every vertex v v v . The fractional chromatic number χ f ( X ) \chi_f(X) χ f ( X ) is the minimum total weight ∑ I ∈ I ( X ) w I \sum_{I\in\mathcal{I}(X)}w_I ∑ I ∈ I ( X ) w I . A d d d -fold colouring with k k k colours assigns a d d d -element subset of { 1 , … , k } \{1,\ldots,k\} { 1 , … , k } to each vertex, with disjoint subsets at adjacent vertices. Equivalently, χ f ( X ) = inf k / d \chi_f(X)=\inf k/d χ f ( X ) = inf k / d over positive integers k , d k,d k , d for which such a colouring exists. Indeed, such a colouring gives each colour class weight 1 / d 1/d 1/ d . Conversely, the finite covering linear program has a rational optimal solution. Clearing its denominators produces colour classes covering each vertex at least d d d times; discarding excess colour memberships at each vertex gives a d d d -fold colouring with the same ratio k / d k/d k / d .
For every field K \mathbb{K} K , these colourings give
φ K ( X ) ≤ χ f ( X ) . (19) \varphi_{\mathbb{K}}(X)\leq\chi_f(X). \tag*{(19)} φ K ( X ) ≤ χ f ( X ) . (19)
For a d d d -fold colouring with k k k colours, let P v P_v P v have as columns the d d d standard coordinate vectors of K k \mathbb{K}^k K k assigned to v v v . The blocks P u T P v P_u^{\mathsf{T}}P_v P u T P v form a fitting matrix for X ‾ \overline{X} X of rank at most k k k , with identity diagonal blocks and zero blocks on edges of X X X . Taking the infimum of k / d k/d k / d proves (C.2).
An automorphism is a vertex permutation preserving adjacency. A graph is vertex-transitive if an automorphism carries any specified vertex to any other. One useful construction averages a nonempty independent a a a -set I I I in a vertex-transitive graph X X X on n n n vertices over its automorphism group Γ \Gamma Γ . Each vertex occurs in exactly ∣ Γ ∣ a / n |\Gamma|a/n ∣Γ∣ a / n of the sets g ( I ) g(I) g ( I ) , counted with multiplicity. Giving each occurrence weight n / ( ∣ Γ ∣ a ) n/(|\Gamma|a) n / ( ∣Γ∣ a ) therefore covers every vertex with total weight one and yields χ f ( X ) ≤ n / a \chi_f(X)\leq n/a χ f ( X ) ≤ n / a .
For the edgeless graph I m I_m I m on m ≥ 1 m \ge1 m ≥ 1 vertices, every spectral point satisfies φ ( I m ) = 1 \varphi(I_m)=1 φ ( I m ) = 1 , since I m I_m I m and K 1 K_1 K 1 are homomorphically equivalent. Two useful consequences of (2) are
C O R ( X ⊕ ⋯ ⊕ X ⏟ k c o p i e s ⊕ K s ) = k C O R ( X ) + s ( k ≥ 1 , s ≥ 0 ) , (20) \mathrm{C}_{\mathrm{OR}}\left(\underbrace{X \mathbin{\oplus}\cdots\mathbin{\oplus} X}_{k\ \mathrm{copies}}\mathbin{\oplus}K_s\right)=k\mathrm{C}_{\mathrm{OR}}(X)+s \qquad(k\ge1,\ s\ge0), \tag*{(20)} C OR k copies X ⊕ ⋯ ⊕ X ⊕ K s = k C OR ( X ) + s ( k ≥ 1 , s ≥ 0 ) , (20)
where K 0 K_0 K 0 is omitted, and
C O R ( X ⊕ I m ) = C O R ( X ) + 1 ( m ≥ 1 ) . (21) \mathrm{C}_{\mathrm{OR}}(X\mathbin{\oplus} I_m)=\mathrm{C}_{\mathrm{OR}}(X)+1 \qquad(m\ge1). \tag*{(21)} C OR ( X ⊕ I m ) = C OR ( X ) + 1 ( m ≥ 1 ) . (21)
These follow by taking the minimum of k φ ( X ) + s k\varphi(X)+s k φ ( X ) + s and φ ( X ) + 1 \varphi(X)+1 φ ( X ) + 1 , respectively. They do not assert additivity of capacity under arbitrary joins.
The next lemma relates f C ( m ) = m f_C(m)=m f C ( m ) = m to the product identity for pairs whose smaller capacity is exactly m m m .
Lemma C.2 (Integer thresholds and exact minima). For every positive integer m m m , f C ( m ) = m f_C(m)=m f C ( m ) = m if and only if
C O R ( G × H ) = m whenever min { C O R ( G ) , C O R ( H ) } = m . \mathrm{C}_{\mathrm{OR}}(G\times H)=m \qquad\text{whenever}\qquad\min\{\mathrm{C}_{\mathrm{OR}}(G),\mathrm{C}_{\mathrm{OR}}(H)\}=m. C OR ( G × H ) = m whenever min { C OR ( G ) , C OR ( H )} = m .
Proof. If f C ( m ) = m f_C(m)=m f C ( m ) = m , its definition gives the required lower bound, and the coordinate projections give the upper bound. Conversely, suppose the stated identity holds, and let C O R ( G ) , C O R ( H ) ≥ m \mathrm{C}_{\mathrm{OR}}(G),\mathrm{C}_{\mathrm{OR}}(H)\ge m C OR ( G ) , C OR ( H ) ≥ m . Applying it to ( G , K m ) (G,K_m) ( G , K m ) shows that A = G × K m A=G\times K_m A = G × K m has capacity m m m . Applying it again to ( A , H ) (A,H) ( A , H ) gives C O R ( A × H ) = m \mathrm{C}_{\mathrm{OR}}(A\times H)=m C OR ( A × H ) = m . The homomorphism ( ( g , i ) , h ) ↦ ( g , h ) ((g,i),h)\mapsto(g,h) (( g , i ) , h ) ↦ ( g , h ) from A × H A\times H A × H to G × H G\times H G × H then gives C O R ( G × H ) ≥ m \mathrm{C}_{\mathrm{OR}}(G\times H)\ge m C OR ( G × H ) ≥ m . Taking the infimum yields f C ( m ) ≥ m f_C(m)\ge m f C ( m ) ≥ m , while the pair ( K m , K m ) (K_m,K_m) ( K m , K m ) gives the reverse inequality.
We also record the threshold facts used in the main text. The admissible pairs in (6) form a decreasing family as t t t increases, so f C f_C f C is nondecreasing; moreover 1 ≤ f C ( t ) ≤ ⌈ t ⌉ 1\le f_C(t)\le\lceil t\rceil 1 ≤ f C ( t ) ≤ ⌈ t ⌉ , using the pair ( K ⌈ t ⌉ , K ⌈ t ⌉ ) (K_{\lceil t\rceil},K_{\lceil t\rceil}) ( K ⌈ t ⌉ , K ⌈ t ⌉ ) for the upper bound. Thus f C ( t ) → ∞ f_C(t)\to\infty f C ( t ) → ∞ is equivalent to the uniform lower-bound formulation (7) . For the converse implication, apply that formulation with B + 1 B+1 B + 1 before taking the infimum, to obtain f C ( T ) ≥ B + 1 > B f_C(T)\ge B+1>B f C ( T ) ≥ B + 1 > B . If the limit is not infinite, monotonicity gives a finite bound B B B on f C f_C f C . For each integer n n n , the definition of the infimum supplies graphs of capacities at least n n n whose product has capacity less than f C ( n ) + 1 ≤ B + 1 f_C(n)+1\le B+1 f C ( n ) + 1 ≤ B + 1 . Conversely, any sequence with diverging factor capacities and uniformly bounded product capacities bounds f C f_C f C by the same constant. If the product capacities fail to diverge, we may first pass to a subsequence on which they are uniformly bounded. This gives the equivalence with the sequence formulation in Conj. 2. No attainment of the infimum is required.
Product bounds from interpolation
This appendix turns spectral interpolation into upper bounds for categorical products. These bounds support the finite and asymptotic constructions in § 3 and § 4 ; we also show how to make the first factor connected.
The categorical product distributes over disjoint union. Fix two spectral points h , q ∈ Δ O R h,q\in\Delta_{\mathrm{OR}} h , q ∈ Δ OR and suppose h ( A i × H ) ≤ h i h(A_i\times H)\le h_i h ( A i × H ) ≤ h i and q ( A i × H ) ≤ q i q(A_i\times H)\le q_i q ( A i × H ) ≤ q i for i = 0 , 1 i=0,1 i = 0 , 1 . For any λ ∈ [ 0 , 1 ] \lambda\in[0,1] λ ∈ [ 0 , 1 ] , the spectral interpolation inequality (4) supplies a single ψ ∈ Δ O R \psi\in\Delta_{\mathrm{OR}} ψ ∈ Δ OR with ψ ( X ) ≤ h ( X ) λ q ( X ) 1 − λ \psi(X)\le h(X)^\lambda q(X)^{1-\lambda} ψ ( X ) ≤ h ( X ) λ q ( X ) 1 − λ for every graph X X X . Combining this with the maximum rule (3) gives the weighted product bound
C O R ( ( A 0 ⊔ A 1 ) × H ) ≤ max i = 0 , 1 h i λ q i 1 − λ ≤ max i = 0 , 1 { λ h i + ( 1 − λ ) q i } . (22) \mathrm{C}_{\mathrm{OR}}\bigl((A_0\mathbin{\sqcup}A_1)\times H\bigr)\le\max_{i=0,1}h_i^\lambda q_i^{1-\lambda}\le\max_{i=0,1}\{\lambda h_i+(1-\lambda)q_i\}. \tag*{(22)} C OR ( ( A 0 ⊔ A 1 ) × H ) ≤ i = 0 , 1 max h i λ q i 1 − λ ≤ i = 0 , 1 max { λ h i + ( 1 − λ ) q i } . (22)
Each h i h_i h i and q i q_i q i can be bounded by projecting to either factor. This lets different bounds control different components.
For a complete second factor K m K_m K m , choose spectral points attaining the two component capacities. Projection to K m K_m K m supplies a second bound for each component product. Interpolating with freely chosen weights combines these bounds into one spectral point.
Proposition D.1 (Weighted two-component product bound). For graphs A , B A, B A , B , every integer m ≥ 1 m \ge1 m ≥ 1 and every λ ∈ [ 0 , 1 ] \lambda\in[0,1] λ ∈ [ 0 , 1 ] ,
COR ( ( A ⊔ B ) × K m ) ≤ max { COR ( A ) λ m 1 − λ , m λ COR ( B ) 1 − λ } . \operatorname{COR}((A \sqcup B) \times K_m) \le\max\{\operatorname{COR}(A)^\lambda m^{1-\lambda},m^\lambda\operatorname{COR}(B)^{1-\lambda}\}. COR (( A ⊔ B ) × K m ) ≤ max { COR ( A ) λ m 1 − λ , m λ COR ( B ) 1 − λ } . In particular, taking λ = 1 / 2 \lambda= 1/2 λ = 1/2 gives
COR ( ( A ⊔ B ) × K m ) ≤ m max { COR ( A ) , COR ( B ) } . \operatorname{COR}((A \sqcup B) \times K_m) \le\sqrt{m\max\{\operatorname{COR}(A),\operatorname{COR}(B)\}}. COR (( A ⊔ B ) × K m ) ≤ m max { COR ( A ) , COR ( B )} . Proof. Choose φ 1 , φ 2 ∈ Δ O R \varphi_1,\varphi_2 \in\Delta_{\mathrm{OR}} φ 1 , φ 2 ∈ Δ OR with φ 1 ( A ) = COR ( A ) \varphi_1(A) = \operatorname{COR}(A) φ 1 ( A ) = COR ( A ) and φ 2 ( B ) = COR ( B ) \varphi_2(B) = \operatorname{COR}(B) φ 2 ( B ) = COR ( B ) . Apply the spectral interpolation inequality (4) with weights λ , 1 − λ \lambda,1-\lambda λ , 1 − λ to obtain ψ \psi ψ . The two projections imply
ψ ( A × K m ) ≤ φ 1 ( A × K m ) λ φ 2 ( A × K m ) 1 − λ ≤ COR ( A ) λ m 1 − λ , \psi(A \times K_m) \le\varphi_1(A \times K_m)^\lambda\varphi_2(A \times K_m)^{1-\lambda} \le\operatorname{COR}(A)^\lambda m^{1-\lambda}, ψ ( A × K m ) ≤ φ 1 ( A × K m ) λ φ 2 ( A × K m ) 1 − λ ≤ COR ( A ) λ m 1 − λ , ψ ( B × K m ) ≤ φ 1 ( B × K m ) λ φ 2 ( B × K m ) 1 − λ ≤ m λ COR ( B ) 1 − λ . \psi(B \times K_m) \le\varphi_1(B \times K_m)^\lambda\varphi_2(B \times K_m)^{1-\lambda} \le m^\lambda\operatorname{COR}(B)^{1-\lambda}. ψ ( B × K m ) ≤ φ 1 ( B × K m ) λ φ 2 ( B × K m ) 1 − λ ≤ m λ COR ( B ) 1 − λ . Since the categorical product distributes over disjoint union,
COR ( ( A ⊔ B ) × K m ) ≤ ψ ( ( A ⊔ B ) × K m ) = max { ψ ( A × K m ) , ψ ( B × K m ) } . \operatorname{COR}((A \sqcup B) \times K_m) \le\psi((A \sqcup B) \times K_m) = \max\{\psi(A \times K_m),\psi(B \times K_m)\}. COR (( A ⊔ B ) × K m ) ≤ ψ (( A ⊔ B ) × K m ) = max { ψ ( A × K m ) , ψ ( B × K m )} . The preceding bounds prove the weighted inequality, and λ = 1 / 2 \lambda= 1/2 λ = 1/2 gives the square-root bound. The same spectral point ψ \psi ψ must control both components for this step to apply.
For the asymptotic construction, each component may have its own exceptional spectral points, where the common bound is not assumed. Projection to K m K_m K m controls these exceptions.
Lemma D.2 (Several spectral bounds). Let A 1 , … , A N A_1,\ldots,A_N A 1 , … , A N be graphs and φ 1 , … , φ k ∈ Δ O R \varphi_1,\ldots,\varphi_k \in\Delta_{\mathrm{OR}} φ 1 , … , φ k ∈ Δ OR . Suppose 1 ≤ h < k 1 \le h < k 1 ≤ h < k , D ≥ 1 D \ge1 D ≥ 1 , and for each i i i there is a set S i ⊆ { 1 , … , k } S_i \subseteq\{1,\ldots,k\} S i ⊆ { 1 , … , k } of cardinality exactly h h h such that
φ j ( A i ) ≤ D ( j ∉ S i ) . \varphi_j(A_i) \le D \qquad(j \notin S_i). φ j ( A i ) ≤ D ( j ∈ / S i ) . Then, for every integer m ≥ 1 m \ge1 m ≥ 1 ,
COR ( ( ⨆ i = 1 N A i ) × K m ) ≤ D 1 − h / k m h / k . \operatorname{COR}\left(\left(\bigsqcup_{i=1}^{N} A_i\right) \times K_m\right) \le D^{1-h/k}m^{h/k}. COR ( ( i = 1 ⨆ N A i ) × K m ) ≤ D 1 − h / k m h / k . Proof. Apply the spectral interpolation inequality (4) to the k k k spectral points with equal weights to obtain ψ \psi ψ . On A i × K m A_i \times K_m A i × K m , projection to A i A_i A i gives a bound D D D for each of the k − h k-h k − h indices outside S i S_i S i . Projection to K m K_m K m gives a bound m m m for each of the remaining h h h indices. Hence, for every i i i ,
ψ ( A i × K m ) ≤ ∏ j = 1 k φ j ( A i × K m ) 1 / k ≤ ( D k − h m h ) 1 / k . \psi(A_i \times K_m) \le\prod_{j=1}^{k}\varphi_j(A_i \times K_m)^{1/k} \le(D^{k-h}m^h)^{1/k}. ψ ( A i × K m ) ≤ j = 1 ∏ k φ j ( A i × K m ) 1/ k ≤ ( D k − h m h ) 1/ k . The maximum rule (3) gives the same bound on the disjoint union of these products, and COR ≤ ψ \operatorname{COR} \le\psi COR ≤ ψ proves the claim.
Our constructions initially give disjoint unions. Adding one universal vertex makes them connected, at an additive cost of at most one in the product bound.
Lemma D.3 (Adding a universal vertex). For every graph X X X and every integer m ≥ 1 m \ge1 m ≥ 1 , the connected graph X + = X ⊕ K 1 X^+ = X \oplus K_1 X + = X ⊕ K 1 satisfies
COR ( X + ) = COR ( X ) + 1 , COR ( X + × K m ) ≤ COR ( X × K m ) + 1. \operatorname{COR}(X^+) = \operatorname{COR}(X) + 1,\qquad\operatorname{COR}(X^+ \times K_m) \le\operatorname{COR}(X \times K_m) + 1. COR ( X + ) = COR ( X ) + 1 , COR ( X + × K m ) ≤ COR ( X × K m ) + 1. Proof. The equality is (C.3). The graph X + × K m X^+ \times K_m X + × K m is a spanning subgraph of ( X × K m ) ⊕ I m (X \times K_m) \oplus I_m ( X × K m ) ⊕ I m . The vertices above the new universal vertex form an independent set of size m m m . Monotonicity and (C.4) prove the upper bound.
Proof of Theorem 1: counterexamples with a complete factor
This appendix supplies the proofs for the finite counterexamples with a complete factor in § 3 . We first establish the binary graph estimates shared by the constructions, then prove the simple example, Thm. 1 and Thm. 4.
Binary orthogonality graphs
For even r ≥ 2 r \ge2 r ≥ 2 , let U r U_r U r be the graph on the odd-weight vectors of F 2 r \mathbb{F}_2^r F 2 r , with distinct x , y x,y x , y adjacent when x ⋅ y = 0 x \cdot y = 0 x ⋅ y = 0 in F 2 \mathbb{F}_2 F 2 . Here the Hamming weight of a vector is its number of nonzero coordinates. The introductory example uses r = 8 r = 8 r = 8 , whereas the construction for Thm. 1 and the real-threshold refinements use r = 6 r = 6 r = 6 . The next lemma determines the capacities of U r U_r U r and its complement by matching explicit cliques with upper bounds valid for every OR-power. We also record the theta bounds needed for spectral interpolation. In our convention, Lovász’s orthonormal-representation formula bounds ϑ ‾ ( X ) = ϑ ( X ‾ ) \overline{\vartheta}(X) = \vartheta(\overline{X}) ϑ ( X ) = ϑ ( X ) by max x ∣ ⟨ u , v x ⟩ ∣ − 2 \max_x |\langle u,v_x\rangle|^{-2} max x ∣ ⟨ u , v x ⟩ ∣ − 2 whenever u , v x u,v_x u , v x are unit vectors and v x ⊥ v y v_x \perp v_y v x ⊥ v y for every edge x y xy x y of X X X [17 ] . The fixed unit reference vector u u u is called the handle .
Lemma E.1 (Binary orthogonality graphs). For every even integer r ≥ 2 r \ge2 r ≥ 2 ,
COR ( U r ) = r , COR ( U r ‾ ) = ϑ ( U r ) = 2 r / 2 − 1 . \operatorname{COR}(U_r)=r,\qquad\operatorname{COR}(\overline{U_r})=\vartheta(U_r)=2^{r/2-1}. COR ( U r ) = r , COR ( U r ) = ϑ ( U r ) = 2 r /2 − 1 .
Proof. For U r U_r U r , we apply Haemers’ matrix-rank bound [13 ] . The binary matrix M x y = x ⋅ y M_{xy}=x\cdot y M x y = x ⋅ y has diagonal 1 1 1 , vanishes on edges of U r U_r U r , and has rank at most r r r . A clique in U r ∨ t U_r^{\vee t} U r ∨ t indexes an identity principal submatrix of M ⊗ t M^{\otimes t} M ⊗ t , so its size is at most r t r^t r t . The r r r coordinate vectors form a clique in U r U_r U r , proving the first equality.
For the complementary graph, we use Lovász’s orthonormal representation method [17 ] . We construct unit vectors orthogonal on edges, all with the same overlap with a fixed unit vector. Tensoring these vectors will bound cliques in every OR-power. Write V = V ( U r ) V=V(U_r) V = V ( U r ) , n = 2 r − 1 n=2^{r-1} n = 2 r − 1 and q = 2 r / 2 − 1 q=2^{r/2-1} q = 2 r /2 − 1 , so n = 2 q 2 n=2q^2 n = 2 q 2 . Since r r r is even, addition of the all-ones vector 1 \mathbf{1} 1 pairs the elements of V V V . In R V \mathbb{R}^{V} R V , let b x b_x b x be the coordinate vector indexed by x x x , and define h x ( z ) = ( − 1 ) x ⋅ z h_x(z)=(-1)^{x\cdot z} h x ( z ) = ( − 1 ) x ⋅ z for z ∈ V z\in V z ∈ V . With δ \delta δ denoting the Kronecker delta, we have
⟨ h x , h y ⟩ = ∑ z ∈ V ( − 1 ) ( x + y ) ⋅ z = n ( δ x y − δ y , x + 1 ) . \langle h_x,h_y\rangle=\sum_{z\in V}(-1)^{(x+y)\cdot z}=n(\delta_{xy}-\delta_{y,x+\mathbf{1}}). ⟨ h x , h y ⟩ = z ∈ V ∑ ( − 1 ) ( x + y ) ⋅ z = n ( δ x y − δ y , x + 1 ) .
The sum is n n n when x = y x=y x = y and − n -n − n when x + y = 1 x+y=\mathbf{1} x + y = 1 . Otherwise, choose i , j i,j i , j with ( x + y ) i ≠ ( x + y ) j (x+y)_i\ne(x+y)_j ( x + y ) i = ( x + y ) j and pair the summands at z z z and z + e i + e j z+e_i+e_j z + e i + e j ; these have opposite signs and cancel.
Define
w x = ( q − 1 / 2 , b x − b x + 1 2 + h x 2 q ) , u = ( 1 , 0 , … , 0 ) . w_x=\left(q^{-1/2},\frac{b_x-b_{x+\mathbf{1}}}{2}+\frac{h_x}{2q}\right),\qquad u=(1,0,\ldots,0). w x = ( q − 1/2 , 2 b x − b x + 1 + 2 q h x ) , u = ( 1 , 0 , … , 0 ) .
Since h y ( x + 1 ) = − h y ( x ) h_y(x+\mathbf{1})=-h_y(x) h y ( x + 1 ) = − h y ( x ) , expansion of the inner product gives
⟨ w x , w y ⟩ = 1 q + 1 2 ( δ x y − δ y , x + 1 ) + ( − 1 ) x ⋅ y q + n 4 q 2 ( δ x y − δ y , x + 1 ) = δ x y − δ y , x + 1 + 1 + ( − 1 ) x ⋅ y q . \begin{aligned}
\langle w_x,w_y\rangle
&=\frac{1}{q}+\frac{1}{2}(\delta_{xy}-\delta_{y,x+\mathbf{1}})+\frac{(-1)^{x\cdot y}}{q}+\frac{n}{4q^2}(\delta_{xy}-\delta_{y,x+\mathbf{1}})\\
&=\delta_{xy}-\delta_{y,x+\mathbf{1}}+\frac{1+(-1)^{x\cdot y}}{q}.
\end{aligned} ⟨ w x , w y ⟩ = q 1 + 2 1 ( δ x y − δ y , x + 1 ) + q ( − 1 ) x ⋅ y + 4 q 2 n ( δ x y − δ y , x + 1 ) = δ x y − δ y , x + 1 + q 1 + ( − 1 ) x ⋅ y .
Thus every w x w_x w x is a unit vector and ∣ ⟨ u , w x ⟩ ∣ 2 = 1 / q |\langle u,w_x\rangle|^2=1/q ∣ ⟨ u , w x ⟩ ∣ 2 = 1/ q . If x , y x,y x , y are adjacent in U r ‾ \overline{U_r} U r , then x ⋅ y = 1 x\cdot y=1 x ⋅ y = 1 and y ∉ { x , x + 1 } y\notin\{x,x+\mathbf{1}\} y ∈ / { x , x + 1 } , since x ⋅ ( x + 1 ) = 0 x\cdot(x+\mathbf{1})=0 x ⋅ ( x + 1 ) = 0 . The displayed formula gives w x ⊥ w y w_x\perp w_y w x ⊥ w y . The orthonormal-representation formula then gives ϑ ( U r ) ≤ q \vartheta(U_r)\le q ϑ ( U r ) ≤ q .
A clique of size a a a in U r ‾ ∨ t \overline{U_r}^{\vee t} U r ∨ t gives a a a orthonormal vectors, each with squared overlap q − t q^{-t} q − t with u ⊗ t u^{\otimes t} u ⊗ t . Bessel’s inequality gives a q − t ≤ ∥ u ⊗ t ∥ 2 = 1 aq^{-t}\le\|u^{\otimes t}\|^2=1 a q − t ≤ ∥ u ⊗ t ∥ 2 = 1 , so COR ( U r ‾ ) ≤ q \operatorname{COR}(\overline{U_r})\le q COR ( U r ) ≤ q . For the matching lower bound, the q q q vectors
e r + span F 2 { e 1 + e 2 , e 3 + e 4 , … , e r − 3 + e r − 2 } e_r+\operatorname{span}_{\mathbb{F}_2}\{e_1+e_2,e_3+e_4,\ldots,e_{r-3}+e_{r-2}\} e r + span F 2 { e 1 + e 2 , e 3 + e 4 , … , e r − 3 + e r − 2 }
have pairwise dot product 1 and form a clique in U r ‾ \overline{U_r} U r . For r = 2 r=2 r = 2 , the span is { 0 } \{0\} { 0 } .
The simple counterexample
Proposition E.2 (The simple counterexample). Let F_9=U_8\mathbin{\mathaccent\cdot\cup}\overline{U_8} . Then
COR ( F 9 ) = 128 > 9 = COR ( K 9 ) , COR ( F 9 × K 9 ) ≤ 72 < 9. \operatorname{COR}(F_9)=\sqrt{128}>9=\operatorname{COR}(K_9),\qquad\operatorname{COR}(F_9\times K_9)\leq\sqrt{72}<9. COR ( F 9 ) = 128 > 9 = COR ( K 9 ) , COR ( F 9 × K 9 ) ≤ 72 < 9.
Proof of Lem. E.2 and (5) . By Lem. E.1, COR ( U 8 ) = COR ( U 8 ‾ ) = 8 \operatorname{COR}(U_8)=\operatorname{COR}(\overline{U_8})=8 COR ( U 8 ) = COR ( U 8 ) = 8 . For each vertex x x x of U 8 U_8 U 8 , take the word ( x U 8 , x U 8 ‾ ) (x_{U_8},x_{\overline{U_8}}) ( x U 8 , x U 8 ) in (U_8\mathbin{\mathaccent\cdot\cup}\overline{U_8})^2 . For distinct x , y x,y x , y , either x y ∈ E ( U 8 ) xy\in E(U_8) x y ∈ E ( U 8 ) or x y ∈ E ( U 8 ‾ ) xy\in E(\overline{U_8}) x y ∈ E ( U 8 ) , so the 128 words form a clique. Hence COR ( F 9 ) ≥ 128 > 9 \operatorname{COR}(F_9)\geq\sqrt{128}>9 COR ( F 9 ) ≥ 128 > 9 .
For the matching upper bound, first note that U 8 U_8 U 8 is vertex-transitive. Given an odd-weight vector x x x , choose i i i with x i = 0 x_i=0 x i = 0 and put v = x + e i v=x+e_i v = x + e i . Since v ⋅ v = 0 v\cdot v=0 v ⋅ v = 0 , the map z ↦ z + ( z ⋅ v ) v z\mapsto z+(z\cdot v)v z ↦ z + ( z ⋅ v ) v preserves dot products and sends e i e_i e i to x x x . Together with coordinate permutations, these maps prove transitivity. Put h = φ F 2 h=\varphi_{\mathbb{F}_2} h = φ F 2 and q ( X ) = ϑ ( X ‾ ) q(X)=\vartheta(\overline{X}) q ( X ) = ϑ ( X ) . The rank bound and the eight-clique in Lem. E.1 give h ( U 8 ) = 8 h(U_8)=8 h ( U 8 ) = 8 , and the same lemma gives q ( U 8 ‾ ) = 8 q(\overline{U_8})=8 q ( U 8 ) = 8 . Averaging that eight-clique, viewed as an independent set of U 8 ‾ \overline{U_8} U 8 , over automorphisms gives a fractional colouring of weight 128 / 8 = 16 128/8=16 128/8 = 16 , as explained in Supplementary App. § 14 . Thus (C.2) gives h ( U 8 ‾ ) ≤ χ f ( U 8 ‾ ) ≤ 16 h(\overline{U_8})\leq\chi_f(\overline{U_8})\leq16 h ( U 8 ) ≤ χ f ( U 8 ) ≤ 16 . Lovász’s vertex-transitive identity ϑ ( U 8 ) ϑ ( U 8 ‾ ) = 128 \vartheta(U_8)\vartheta(\overline{U_8})=128 ϑ ( U 8 ) ϑ ( U 8 ) = 128 [17 Thm. 8] also gives q ( U 8 ) = 16 q(U_8)=16 q ( U 8 ) = 16 . Applying the spectral interpolation inequality (4) to h , q h,q h , q with equal weights yields a single ψ ∈ Δ OR \psi\in\Delta_{\operatorname{OR}} ψ ∈ Δ OR satisfying
ψ ( U 8 ) ≤ 8 ⋅ 16 , ψ ( U 8 ‾ ) ≤ 16 ⋅ 8 . \psi(U_8)\leq\sqrt{8\cdot16},\qquad\psi(\overline{U_8})\leq\sqrt{16\cdot8}. ψ ( U 8 ) ≤ 8 ⋅ 16 , ψ ( U 8 ) ≤ 16 ⋅ 8 .
The maximum rule now gives COR ( F 9 ) ≤ ψ ( F 9 ) ≤ 128 \operatorname{COR}(F_9)\leq\psi(F_9)\leq\sqrt{128} COR ( F 9 ) ≤ ψ ( F 9 ) ≤ 128 , proving equality. Finally, the equal-weight bound in Lem. D.1 gives COR ( F 9 × K 9 ) ≤ 72 < 9 \operatorname{COR}(F_9\times K_9)\leq\sqrt{72}<9 COR ( F 9 × K 9 ) ≤ 72 < 9 .
Remark (Choice of the simple example). The graph F 9 F_9 F 9 illustrates the argument with two components of capacity 8 and equal interpolation weights. The construction in Subsec. E.3 gives a smaller first factor at m = 9 m=9 m = 9 and extends the range of complete factors to every integer m ≥ 7 m\geq7 m ≥ 7 .
The complete-factor family and its spectral consequence
We begin with a construction whose smaller factor capacity is seven and obtain the remaining integer cases by adding cliques. This proves Thm. 1, and the same spectral point yields Thm. 4.
Put A = U 6 A=U_6 A = U 6 , D = A ‾ D=\overline{A} D = A , and let Q Q Q be the 5-regular Clebsch graph on F 2 4 \mathbb{F}_2^4 F 2 4 , with adjacency differences { e 1 , e 2 , e 3 , e 4 , 1 } \{e_1,e_2,e_3,e_4,\mathbf{1}\} { e 1 , e 2 , e 3 , e 4 , 1 } . Set B=D\mathbin{\mathaccent\cdot\cup}Q and X_7=A\mathbin{\mathaccent\cdot\cup}B . The graph X 7 X_7 X 7 has 80 vertices. We will show that
COR ( X 7 ) ≥ ρ : = s + s 2 + 128 2 > 7 , s = 16 1 / 3 , (23) \operatorname{COR}(X_7)\geq\rho:=\frac{s+\sqrt{s^2+128}}{2}>7,\qquad s=16^{1/3}, \tag*{(23)} COR ( X 7 ) ≥ ρ := 2 s + s 2 + 128 > 7 , s = 1 6 1/3 , (23)
while both components have capacity at most 20 / 3 < 7 20/3<7 20/3 < 7 . Weighted spectral interpolation gives the counterexample with K 7 K_7 K 7 ; joining the same complete graph to both components gives the full statement.
Lemma E.3 (Clebsch graph). Let Q Q Q be the graph on F 2 4 \mathbb{F}_2^4 F 2 4 in which x x x and y y y are adjacent when x + y ∈ S : = { e 1 , e 2 , e 3 , e 4 , 1 } x+y\in S:=\{e_1,e_2,e_3,e_4,\mathbf{1}\} x + y ∈ S := { e 1 , e 2 , e 3 , e 4 , 1 } . Then
16 1 / 3 ≤ COR ( Q ) ≤ ϑ ( Q ‾ ) ≤ 8 3 . 16^{1/3}\leq\operatorname{COR}(Q)\leq\vartheta(\overline{Q})\leq\frac{8}{3}. 1 6 1/3 ≤ COR ( Q ) ≤ ϑ ( Q ) ≤ 3 8 . Moreover, Q Q Q admits unit vectors orthogonal on edges and a unit handle whose squared overlap with every vertex vector is 3 / 8 3/8 3/8 .
Proof. For the lower bound [12 , 24 ] , identify F 2 4 \mathbb{F}_2^4 F 2 4 with F 16 \mathbb{F}_{16} F 16 using the basis 1 , β , β 2 , β 3 1,\beta,\beta^2,\beta^3 1 , β , β 2 , β 3 , where β \beta β has multiplicative order five. Its minimal polynomial is z 4 + z 3 + z 2 + z + 1 z^4+z^3+z^2+z+1 z 4 + z 3 + z 2 + z + 1 , so the connection set S S S becomes the multiplicative subgroup H = { 1 , β , β 2 , β 3 , β 4 } H=\{1,\beta,\beta^2,\beta^3,\beta^4\} H = { 1 , β , β 2 , β 3 , β 4 } . Choose a ∈ F 16 × ∖ H a\in\mathbb{F}_{16}^{\times}\setminus H a ∈ F 16 × ∖ H . The three cosets H H H , a H aH a H , a 2 H a^2H a 2 H partition F 16 × \mathbb{F}_{16}^{\times} F 16 × . Consequently, for every nonzero d d d , exactly one of d d d , a d ad a d , a 2 d a^2d a 2 d belongs to H H H . The sixteen words
( x , a x , a 2 x ) , x ∈ F 16 , (x,ax,a^2x),\qquad x\in\mathbb{F}_{16}, ( x , a x , a 2 x ) , x ∈ F 16 ,
therefore form a clique in Q ∨ 3 Q^{\vee3} Q ∨ 3 , proving COR ( Q ) ≥ 16 1 / 3 \operatorname{COR}(Q)\ge16^{1/3} COR ( Q ) ≥ 1 6 1/3 .
For the upper bound, let D D D be the adjacency matrix of Q Q Q . The sixteen characters x ↦ ( − 1 ) u ⋅ x x\mapsto(-1)^{u\cdot x} x ↦ ( − 1 ) u ⋅ x , indexed by u ∈ F 2 4 u\in\mathbb{F}_2^4 u ∈ F 2 4 , form an orthogonal basis of R 16 \mathbb{R}^{16} R 16 . Each is an eigenvector of D D D with eigenvalue 4 − 2 ∣ u ∣ + ( − 1 ) ∣ u ∣ 4-2|u|+(-1)^{|u|} 4 − 2∣ u ∣ + ( − 1 ) ∣ u ∣ , where ∣ u ∣ |u| ∣ u ∣ is the Hamming weight of u u u . Thus the eigenvalues are 5 5 5 , 1 1 1 , and − 3 -3 − 3 , with the eigenvalue 5 5 5 occurring only for the constant character. Writing J J J for the all-ones matrix, the matrix
T = I + 1 2 ( J − I − D ) T=I+\frac{1}{2}(J-I-D) T = I + 2 1 ( J − I − D )
has eigenvalues 6 6 6 , 0 0 0 , and 2 2 2 , and is therefore positive semidefinite. It has diagonal entries one, vanishes on edges of Q Q Q , and has row sum six. Let ( v x ) x ∈ F 2 4 (v_x)_{x\in\mathbb{F}_2^4} ( v x ) x ∈ F 2 4 be unit vectors with Gram matrix T T T , meaning T x y = ⟨ v x , v y ⟩ T_{xy}=\langle v_x,v_y\rangle T x y = ⟨ v x , v y ⟩ . Such vectors exist because T T T is positive semidefinite with diagonal entries one. The vector
h = 1 96 ∑ x v x h=\frac{1}{\sqrt{96}}\sum_x v_x h = 96 1 x ∑ v x
is a unit vector satisfying ∣ ⟨ h , v x ⟩ ∣ 2 = 3 / 8 |\langle h,v_x\rangle|^2=3/8 ∣ ⟨ h , v x ⟩ ∣ 2 = 3/8 for every x x x . Thus the orthonormal-representation formula gives ϑ ( Q ) ≤ 8 / 3 \vartheta(Q)\le8/3 ϑ ( Q ) ≤ 8/3 . Tensoring this representation and applying Bessel’s inequality, as in Lem. E.1, gives ω ( Q ∨ t ) ≤ ( 8 / 3 ) t \omega(Q^{\vee t})\le(8/3)^t ω ( Q ∨ t ) ≤ ( 8/3 ) t . □
The next lemma explains how the complementary diagonal code and the additional joined graph increase the capacity of the disjoint union. It uses additivity of spectral points under join, without assuming that capacity itself is additive.
Lemma E.4 (A joined complementary component). Let A A A be a graph on n n n vertices, and let Q Q Q be a graph with COR ( Q ) ≥ s > 0 \operatorname{COR}(Q)\ge s>0 COR ( Q ) ≥ s > 0 . Then
COR ( A ⊔ ( A ‾ ⊕ Q ) ) ≥ s + s 2 + 4 n 2 . \operatorname{COR}\bigl(A\sqcup(\overline{A}\oplus Q)\bigr)\ge\frac{s+\sqrt{s^2+4n}}{2}. COR ( A ⊔ ( A ⊕ Q ) ) ≥ 2 s + s 2 + 4 n . Proof. For any φ ∈ Δ O R \varphi\in\Delta_{\mathrm{OR}} φ ∈ Δ OR , put x = φ ( A ) x=\varphi(A) x = φ ( A ) and y = φ ( A ‾ ) y=\varphi(\overline{A}) y = φ ( A ) . The n n n diagonal pairs ( v , v ) (v,v) ( v , v ) form a clique in A ∨ A ‾ A\vee\overline{A} A ∨ A , so multiplicativity and monotonicity give x y ≥ n xy\ge n x y ≥ n . By additivity under join and (3) ,
φ ( A ⊔ ( A ‾ ⊕ Q ) ) = max { x , y + φ ( Q ) } ≥ max { x , y + s } . \varphi\bigl(A\sqcup(\overline{A}\oplus Q)\bigr)=\max\{x,y+\varphi(Q)\}\ge\max\{x,y+s\}. φ ( A ⊔ ( A ⊕ Q ) ) = max { x , y + φ ( Q )} ≥ max { x , y + s } . Writing the last maximum as r r r gives x ≤ r x\le r x ≤ r , y ≤ r − s y\le r-s y ≤ r − s , and therefore n ≤ x y ≤ r ( r − s ) n\le xy\le r(r-s) n ≤ x y ≤ r ( r − s ) . Solving this quadratic inequality and taking the minimum over φ \varphi φ proves the claim. □
Proof of Thm. 1. Set
A = U 6 , B = A ‾ ⊕ Q , X 7 = A ⊔ B . A = U_6,\qquad B = \overline{A} \oplus Q,\qquad X_7 = A \sqcup B. A = U 6 , B = A ⊕ Q , X 7 = A ⊔ B .
By Lem. E.1, COR ( A ) = 6 \operatorname{COR}(A)=6 COR ( A ) = 6 and COR ( A ‾ ) = 4 \operatorname{COR}(\overline{A})=4 COR ( A ) = 4 . Its proof supplies a representation of A ‾ \overline{A} A with squared handle overlap 1 / 4 1/4 1/4 . Combine this representation with that of Q Q Q from Lem. E.3 in orthogonal summands. For handles u u u and h h h in the respective summands, use
c = 4 20 / 3 u ⊕ 8 / 3 20 / 3 h . c=\sqrt{\frac{4}{20/3}}\,u\oplus\sqrt{\frac{8/3}{20/3}}\,h. c = 20/3 4 u ⊕ 20/3 8/3 h .
This is a unit handle with squared overlap 3 / 20 3/20 3/20 with every vertex vector. The summands are orthogonal, so the representation also vanishes on all edges added by the join. Bessel’s inequality gives
max { COR ( A ) , COR ( B ) } ≤ 20 3 < 7. (24) \max\{\operatorname{COR}(A),\operatorname{COR}(B)\}\leq\frac{20}{3}<7. \tag*{(24)} max { COR ( A ) , COR ( B )} ≤ 3 20 < 7. (24)
The graph A A A has 32 vertices. Applying Lem. E.4 with s = 16 1 / 3 s=16^{1/3} s = 1 6 1/3 gives
COR ( X 7 ) ≥ s + s 2 + 128 2 = ρ > 7 , \operatorname{COR}(X_7)\geq\frac{s+\sqrt{s^2+128}}{2}=\rho>7, COR ( X 7 ) ≥ 2 s + s 2 + 128 = ρ > 7 ,
where ρ \rho ρ is defined in (E.1). For the strict comparison, s > 17 / 7 s>17/7 s > 17/7 because 16 ⋅ 7 3 = 5488 > 4913 = 17 3 16\cdot7^3=5488>4913=17^3 16 ⋅ 7 3 = 5488 > 4913 = 1 7 3 ; hence 7 2 − 7 s − 32 = 17 − 7 s < 0 7^2-7s-32=17-7s<0 7 2 − 7 s − 32 = 17 − 7 s < 0 .
Following the weighted argument of Lem. D.1, choose spectral points φ A , φ B \varphi_A,\varphi_B φ A , φ B attaining the capacities of the base components A , B A,B A , B , respectively. Interpolate them with weights 1 / 4 , 3 / 4 1/4,3/4 1/4 , 3/4 in (4) to obtain a single ψ 7 ∈ Δ O R \psi_7\in\Delta_{\mathrm{OR}} ψ 7 ∈ Δ OR , which we fix for the whole family. For an integer m ≥ 7 m\geq7 m ≥ 7 , let k = m − 7 k=m-7 k = m − 7 and set
A m = A ⊕ K k , B m = B ⊕ K k , X m = A m ⊔ B m , A_m=A\oplus K_k,\qquad B_m=B\oplus K_k,\qquad X_m=A_m\sqcup B_m, A m = A ⊕ K k , B m = B ⊕ K k , X m = A m ⊔ B m ,
omitting K 0 K_0 K 0 when k = 0 k=0 k = 0 . The spectral rules give φ ( X m ) = φ ( X 7 ) + k \varphi(X_m)=\varphi(X_7)+k φ ( X m ) = φ ( X 7 ) + k for every φ ∈ Δ O R \varphi\in\Delta_{\mathrm{OR}} φ ∈ Δ OR ; therefore COR ( X m ) = COR ( X 7 ) + k > m \operatorname{COR}(X_m)=\operatorname{COR}(X_7)+k>m COR ( X m ) = COR ( X 7 ) + k > m . Eq. (C.3) and (E.2) give
COR ( A m ) = m − 1 , COR ( B m ) ≤ m − 1 3 . \operatorname{COR}(A_m)=m-1,\qquad\operatorname{COR}(B_m)\leq m-\frac{1}{3}. COR ( A m ) = m − 1 , COR ( B m ) ≤ m − 3 1 .
Join additivity also gives φ A ( A m ) = m − 1 \varphi_A(A_m)=m-1 φ A ( A m ) = m − 1 and φ B ( B m ) ≤ m − 1 3 \varphi_B(B_m)\leq m-\frac{1}{3} φ B ( B m ) ≤ m − 3 1 . The coordinate projections and the weighted arithmetic–geometric mean inequality therefore give
ψ 7 ( A m × K m ) ≤ ( m − 1 ) 1 / 4 m 3 / 4 ≤ 1 4 ( m − 1 ) + 3 4 m = m − 1 4 , ψ 7 ( B m × K m ) ≤ m 1 / 4 ( m − 1 3 ) 3 / 4 ≤ 1 4 m + 3 4 ( m − 1 3 ) = m − 1 4 . \begin{aligned}
\psi_7(A_m\times K_m)&\leq(m-1)^{1/4}m^{3/4}\leq\frac{1}{4}(m-1)+\frac{3}{4}m=m-\frac{1}{4},\\
\psi_7(B_m\times K_m)&\leq m^{1/4}\left(m-\frac{1}{3}\right)^{3/4}\leq\frac{1}{4}m+\frac{3}{4}\left(m-\frac{1}{3}\right)=m-\frac{1}{4}.
\end{aligned} ψ 7 ( A m × K m ) ψ 7 ( B m × K m ) ≤ ( m − 1 ) 1/4 m 3/4 ≤ 4 1 ( m − 1 ) + 4 3 m = m − 4 1 , ≤ m 1/4 ( m − 3 1 ) 3/4 ≤ 4 1 m + 4 3 ( m − 3 1 ) = m − 4 1 .
Since the categorical product distributes over disjoint union, the maximum rule (3) yields
COR ( X m × K m ) ≤ ψ 7 ( X m × K m ) ≤ m − 1 4 < m = min { COR ( X m ) , COR ( K m ) } . \operatorname{COR}(X_m\times K_m)\leq\psi_7(X_m\times K_m)\leq m-\frac{1}{4}<m=\min\{\operatorname{COR}(X_m),\operatorname{COR}(K_m)\}. COR ( X m × K m ) ≤ ψ 7 ( X m × K m ) ≤ m − 4 1 < m = min { COR ( X m ) , COR ( K m )} .
Finally, ∣ V ( A ) ∣ = 32 |V(A)|=32 ∣ V ( A ) ∣ = 32 and ∣ V ( Q ) ∣ = 16 |V(Q)|=16 ∣ V ( Q ) ∣ = 16 , so ∣ V ( X m ) ∣ = 32 + ( 32 + 16 ) + 2 k = 2 m + 66 |V(X_m)|=32+(32+16)+2k=2m+66 ∣ V ( X m ) ∣ = 32 + ( 32 + 16 ) + 2 k = 2 m + 66 . Taking G = X m G=X_m G = X m proves Thm. 1.
Proof of Thm. 4. The preceding proof constructs a single spectral point ψ = ψ 7 \psi=\psi_7 ψ = ψ 7 , independent of m m m , such that G m = X m G_m=X_m G m = X m satisfies
ψ ( G m × K m ) ≤ m − 1 4 < m . \psi(G_m\times K_m)\leq m-\frac{1}{4}<m. ψ ( G m × K m ) ≤ m − 4 1 < m .
Every spectral point bounds capacity from above, so ψ ( G m ) ≥ COR ( G m ) > m \psi(G_m)\geq\operatorname{COR}(G_m)>m ψ ( G m ) ≥ COR ( G m ) > m . Normalization and join additivity give ψ ( K m ) = m \psi(K_m)=m ψ ( K m ) = m , proving the claim.
Proof of Theorem 2(1): a counterexample below six
This appendix gives the counterexample with both factor capacities below six, proving Thm. 2(1). We specify the graphs, codes and exact matrix certificates that establish the required capacity bounds, together with procedures for checking them.
The proof in this appendix combines analytical arguments with computer-assisted verification of explicit graph data, codes and matrix certificates. OpenAI Codex assisted with exploring candidate constructions and certificates and with developing and reviewing the verification code. The finite certificate checks use exact arithmetic, and the product-capacity bound follows from the analytical spectral argument.
Statement
We use the conventions of Supplementary Apps. A–C. A length-n n n code in X X X is a clique in X ∨ n X^{\vee n} X ∨ n , and COR ( X ) = sup n ≥ 1 ω ( X ∨ n ) 1 / n \operatorname{COR}(X)=\sup_{n\geq1}\omega(X^{\vee n})^{1/n} COR ( X ) = sup n ≥ 1 ω ( X ∨ n ) 1/ n .
Set
b = 32437757 6250000 = 5.19004112 , q = 12991403 2500000 = 5.1965612 , L = 5193957 1000000 = 5.193957. b=\frac{32437757}{6250000}=5.19004112,\qquad q=\frac{12991403}{2500000}=5.1965612,\qquad L=\frac{5193957}{1000000}=5.193957. b = 6250000 32437757 = 5.19004112 , q = 2500000 12991403 = 5.1965612 , L = 1000000 5193957 = 5.193957.
Proposition F.1. For the graphs G G G , H H H defined in Subsec. F.2,
COR ( G × H ) < L < 27 ≤ min { COR ( G ) , COR ( H ) } , \operatorname{COR}(G\times H)<L<\sqrt{27}\leq\min\{\operatorname{COR}(G),\operatorname{COR}(H)\}, COR ( G × H ) < L < 27 ≤ min { COR ( G ) , COR ( H )} , and, separately,
COR ( G ) ≤ 16 3 < 6 , COR ( H ) ≤ q < 6. \operatorname{COR}(G)\leq\frac{16}{3}<6,\qquad\operatorname{COR}(H)\leq q<6. COR ( G ) ≤ 3 16 < 6 , COR ( H ) ≤ q < 6. Consequently the Shannon OR-capacity Hedetniemi equality fails. The same pair witnesses COR ( G × H ) < r < min { COR ( G ) , COR ( H ) } \operatorname{COR}(G\times H)<r<\min\{\operatorname{COR}(G),\operatorname{COR}(H)\} COR ( G × H ) < r < min { COR ( G ) , COR ( H )} for every real r ∈ [ L , 27 ) r\in[L,\sqrt{27}) r ∈ [ L , 27 ) .
This proves Thm. 2(1). The smaller factor capacity lies in [ 27 , q ] [\sqrt{27},q] [ 27 , q ] ; its exact value is unknown. The construction establishes this local interval, with no claim that its lower endpoint is optimal or that failure extends to every larger threshold.
The graphs and their lower-bound codes
The 54-vertex graph
Use the following ordered list of vectors in F 3 5 \mathbb{F}_3^5 F 3 5 , with entries interpreted modulo three.
Table 1 (PDF p. 30).
Let B B B have vertex set { 0 , … , 26 } \{0,\ldots,26\} { 0 , … , 26 } and adjacency
i ∼ B j ⟺ i ≠ j and w i ⋅ w j = 0 in F 3 . i\sim_B j\quad\Longleftrightarrow\quad i\ne j\text{ and }w_i\cdot w_j=0\text{ in }\mathbb{F}_3. i ∼ B j ⟺ i = j and w i ⋅ w j = 0 in F 3 .
Let D = B ‾ D=\overline{B} D = B , the simple complement on the same vertex set. Define
G = B ⊔ D . G=B\mathbin{\sqcup}D. G = B ⊔ D .
For explicit labels, the B B B -copy uses 0 , … , 26 0,\ldots,26 0 , … , 26 and the D D D -copy uses 27 , … , 53 27,\ldots,53 27 , … , 53 , with 27 + i 27+i 27 + i representing vertex i i i of D D D . There are no edges between the copies. The 27 words
K G = { ( i , 27 + i ) : 0 ≤ i ≤ 26 } ⊆ V ( G ) 2 \mathcal{K}_G=\{(i,27+i):0\leq i\leq26\}\subseteq V(G)^2 K G = {( i , 27 + i ) : 0 ≤ i ≤ 26 } ⊆ V ( G ) 2
form a code because, for distinct i , j i,j i , j , exactly one of i ∼ B j i\sim_B j i ∼ B j and i ∼ D j i\sim_D j i ∼ D j holds. Therefore
COR ( G ) ≥ ω ( G ∨ G ) 1 / 2 ≥ 27 . (25) \operatorname{COR}(G)\geq\omega(G\vee G)^{1/2}\geq\sqrt{27}. \tag*{(25)} COR ( G ) ≥ ω ( G ∨ G ) 1/2 ≥ 27 . (25)
The 27-vertex graph
Let V ( H ) = Z 29 ∖ { 1 , 17 } V(H)=\mathbb{Z}_{29}\setminus\{1,17\} V ( H ) = Z 29 ∖ { 1 , 17 } , ordered as 0 , 2 , 3 , … , 16 , 18 , 19 , … , 28 0,2,3,\ldots,16,18,19,\ldots,28 0 , 2 , 3 , … , 16 , 18 , 19 , … , 28 . The following table defines the graph completely by listing, in row v v v , all its neighbours larger than v v v . Each listed pair is an undirected edge, and there are no loops. The residue labels specify the vertices of H H H ; adjacency is defined entirely by the table.
Table 1 (PDF p. 31).
This graph has 176 edges. The 27 words
K H = { ( i , 12 i mod 29 ) : i ∈ Z 29 ∖ { 1 , 17 , 28 } } ∪ { ( 28 , 12 ) } \mathcal{K}_H=\{(i,12i\mathbin{\operatorname{mod}}29):i\in\mathbb{Z}_{29}\setminus\{1,17,28\}\}\cup\{(28,12)\} K H = {( i , 12 i mod 29 ) : i ∈ Z 29 ∖ { 1 , 17 , 28 }} ∪ {( 28 , 12 )}
are all in V ( H ) 2 V(H)^2 V ( H ) 2 , since 12 i = 1 12i=1 12 i = 1 and 12 i = 17 12i=17 12 i = 17 modulo 29 have the unique solutions i = 17 i=17 i = 17 and i = 28 i=28 i = 28 , respectively. Their first coordinates are distinct, and the table verifies
( a , b ) , ( c , d ) ∈ K H , ( a , b ) ≠ ( c , d ) ⟹ a ∼ H c or b ∼ H d . (a,b),(c,d)\in K_H,\quad(a,b)\ne(c,d)\ \Longrightarrow\ a\sim_H c\text{ or }b\sim_H d. ( a , b ) , ( c , d ) ∈ K H , ( a , b ) = ( c , d ) ⟹ a ∼ H c or b ∼ H d .
This is a finite check of 351 unordered pairs, also performed by the exact verifier described in Subsec. F.8. Hence
COR ( H ) ≥ 27 . (26) \operatorname{COR}(H)\ge\sqrt{27}. \tag*{(26)} COR ( H ) ≥ 27 . (26)
The finite-field certificates
A block representation over F 3 \mathbb{F}_3 F 3 of a graph X X X , with local block size d d d and ambient dimension R R R , consists of matrices P v ∈ F 3 d × R P_v\in\mathbb{F}_3^{d\times R} P v ∈ F 3 d × R , Q v ∈ F 3 R × d Q_v\in\mathbb{F}_3^{R\times d} Q v ∈ F 3 R × d such that
P v Q v = I d , P v Q w = 0 whenever v ∼ X w . P_vQ_v=I_d,\qquad P_vQ_w=0\quad\text{whenever }v\sim_X w. P v Q v = I d , P v Q w = 0 whenever v ∼ X w .
Both orientations of an edge are included. The resulting block matrix ( P v Q w ) v , w (P_vQ_w)_{v,w} ( P v Q w ) v , w need not be symmetric and has rank at most R R R . By the definition of fractional Haemers’ bound in Supplementary App. C and Lem. C.1 , these factors certify
h 3 ( X ) : = φ F 3 ( X ) ≤ R / d . h_3(X):=\varphi_{\mathbb{F}_3}(X)\le R/d. h 3 ( X ) := φ F 3 ( X ) ≤ R / d .
Both h 3 h_3 h 3 and ϑ ‾ ( X ) = ϑ ( X ‾ ) \overline{\vartheta}(X)=\vartheta(\overline{X}) ϑ ( X ) = ϑ ( X ) are OR spectral points, as recalled in Subsec. 2.1 and Lem. C.1 .
A rank-five scalar representation of B
Every listed vector satisfies w i ⋅ w i ≠ 0 w_i\cdot w_i\ne0 w i ⋅ w i = 0 in F 3 \mathbb{F}_3 F 3 . Define the row and column factors
ℓ i = ( w i ⋅ w i ) − 1 w i T , v i = w i , \ell_i=(w_i\cdot w_i)^{-1}w_i^{\mathsf T},\qquad v_i=w_i, ℓ i = ( w i ⋅ w i ) − 1 w i T , v i = w i ,
where the first expression is regarded as a 1 × 5 1\times5 1 × 5 row and the second as a 5 × 1 5\times1 5 × 1 column. Then
ℓ i v i = 1 , ℓ i v j = 0 ( i ∼ B j ) . \ell_i v_i=1,\qquad\ell_i v_j=0\quad(i\sim_B j). ℓ i v i = 1 , ℓ i v j = 0 ( i ∼ B j ) .
Thus h 3 ( B ) ≤ 5 h_3(B)\le5 h 3 ( B ) ≤ 5 .
A rank-eleven, block-two representation of H
The following eleven subsets are independent in H H H , and every vertex belongs to exactly two of them.
Table 3.
Both claims can be checked directly from the adjacency table. Let e 1 , … , e 11 e_1,\ldots,e_{11} e 1 , … , e 11 be the standard coordinate vectors of F 3 11 \mathbb{F}_3^{11} F 3 11 . For h ∈ V ( H ) h \in V(H) h ∈ V ( H ) , let a ( h ) < b ( h ) a(h) < b(h) a ( h ) < b ( h ) be its two set indices and put
E h = [ e a ( h ) e b ( h ) ] ∈ F 3 11 × 2 . E_h = [e_{a(h)}\ e_{b(h)}] \in\mathbb{F}_3^{11 \times2}. E h = [ e a ( h ) e b ( h ) ] ∈ F 3 11 × 2 .
Then E h T E h = I 2 E_h^{T}E_h=I_2 E h T E h = I 2 , and adjacent vertices have disjoint index pairs, so E h T E h ′ = 0 E_h^{T}E_{h'}=0 E h T E h ′ = 0 on every H H H -edge. Thus h 3 ( H ) ≤ 11 / 2 h_3(H) \le11/2 h 3 ( H ) ≤ 11/2 ; the same representation works over every field.
Exact real Gram certificates
The following Gram-matrix criterion gives the theta bounds we need.
Lemma F.2. Suppose a real positive semidefinite matrix M M M , indexed by V ( X ) V(X) V ( X ) , has diagonal entries t − 1 t-1 t − 1 and entries − 1 -1 − 1 on every edge of X X X . Then there are unit vectors u v u_v u v and a fixed unit vector c c c , called the handle, satisfying
u v ⊥ u w ( v ∼ X w ) , ⟨ c , u v ⟩ = t − 1 / 2 . u_v \perp u_w \quad(v \sim_X w), \qquad\langle c,u_v\rangle= t^{-1/2}. u v ⊥ u w ( v ∼ X w ) , ⟨ c , u v ⟩ = t − 1/2 . Consequently ϑ ‾ ( X ) ≤ t \overline{\vartheta}(X) \le t ϑ ( X ) ≤ t and C O R ( X ) ≤ t C_{\mathrm{OR}}(X) \le t C OR ( X ) ≤ t .
Proof. Write M v w = ⟨ z v , z w ⟩ M_{vw}=\langle z_v,z_w\rangle M v w = ⟨ z v , z w ⟩ , using a real Gram factorization. Take u v = ( 1 , z v ) / t u_v=(1,z_v)/\sqrt{t} u v = ( 1 , z v ) / t and c = ( 1 , 0 , … , 0 ) c=(1,0,\ldots,0) c = ( 1 , 0 , … , 0 ) . The orthonormal-representation bound recalled in Supplementary App. E gives ϑ ‾ ( X ) ≤ t \overline{\vartheta}(X) \le t ϑ ( X ) ≤ t .
Subsec. F.7 supplies the following certificates.
Table 1 (PDF p. 33).
Each M X M_X M X is positive definite, has entry − s X -s_X − s X on graph edges, and has normalized diagonal t X − 1 t_X-1 t X − 1 . The symmetry reductions below verify positivity on blocks of size at most 6 for B B B , D D D , and of sizes 15 and 12 for H H H . Applying Lem. F.2 to the normalized matrices M X / s X M_X/s_X M X / s X gives
ϑ ‾ ( B ) ≤ 16 / 3 , ϑ ‾ ( D ) ≤ b , ϑ ‾ ( H ) ≤ q . \overline{\vartheta}(B) \le16/3,\qquad\overline{\vartheta}(D) \le b,\qquad\overline{\vartheta}(H) \le q. ϑ ( B ) ≤ 16/3 , ϑ ( D ) ≤ b , ϑ ( H ) ≤ q .
The maximum rule (3) therefore proves
C O R ( G ) ≤ ϑ ‾ ( G ) = max { ϑ ‾ ( B ) , ϑ ‾ ( D ) } ≤ 16 / 3 < 6 , C O R ( H ) ≤ q < 6. (27) C_{\mathrm{OR}}(G) \le\overline{\vartheta}(G)=\max\{\overline{\vartheta}(B),\overline{\vartheta}(D)\}\le16/3<6,\qquad C_{\mathrm{OR}}(H)\le q<6. \tag*{(27)} C OR ( G ) ≤ ϑ ( G ) = max { ϑ ( B ) , ϑ ( D )} ≤ 16/3 < 6 , C OR ( H ) ≤ q < 6. (27)
The product bound
The graph G × H G\times H G × H is ( B × H ) ⊔ ( D × H ) (B\times H)\sqcup(D\times H) ( B × H ) ⊔ ( D × H ) . Projecting to the appropriate factor in each component gives
Apply (D.1) with these two spectral points. For every 0 ≤ λ ≤ 1 0\le\lambda\le1 0 ≤ λ ≤ 1 ,
C O R ( G × H ) ≤ T λ : = max { 5 λ q 1 − λ , ( 11 / 2 ) λ b 1 − λ } . (28) C_{\mathrm{OR}}(G\times H)\le T_\lambda:=\max\{5^\lambda q^{1-\lambda},(11/2)^\lambda b^{1-\lambda}\}. \tag*{(28)} C OR ( G × H ) ≤ T λ := max { 5 λ q 1 − λ , ( 11/2 ) λ b 1 − λ } . (28)
This already controls arbitrary codes of every length, including words whose coordinates lie in different components.
Exact verification of the strict separation
Choose the rational weight λ = 13 / 1000 \lambda= 13/1000 λ = 13/1000 . The required strict comparisons reduce to the rational inequalities
5 13 ( 12991403 2500000 ) 987 < ( 5193957 1000000 ) 1000 , (29) 5^{13}\left(\frac{12991403}{2500000}\right)^{987}<\left(\frac{5193957}{1000000}\right)^{1000}, \tag*{(29)} 5 13 ( 2500000 12991403 ) 987 < ( 1000000 5193957 ) 1000 , (29)
( 11 2 ) 13 ( 32437757 6250000 ) 987 < ( 5193957 1000000 ) 1000 . (30) \left(\frac{11}{2}\right)^{13}\left(\frac{32437757}{6250000}\right)^{987}<\left(\frac{5193957}{1000000}\right)^{1000}. \tag*{(30)} ( 2 11 ) 13 ( 6250000 32437757 ) 987 < ( 1000000 5193957 ) 1000 . (30)
The inequalities (F.5)–(F.6) are checked by integer powers and cross multiplication; the exact Python statements are given below. Taking positive 1000-th roots proves T λ < L T_\lambda< L T λ < L . Also
5193957 2 = 26977189317849 < 27000000000000 = 27 ⋅ 10 12 , 5193957^2=26977189317849<27000000000000=27\cdot10^{12}, 519395 7 2 = 26977189317849 < 27000000000000 = 27 ⋅ 1 0 12 ,
so L < 27 L<\sqrt{27} L < 27 . Combining (F.1), (F.2), (F.3), and (F.4) proves Prop. F.1 .
To establish the sub-six spectral claim in § 5 , choose the single interpolating point ψ ∈ Δ O R \psi\in\Delta_{\mathrm{OR}} ψ ∈ Δ OR supplied by (4) for h 3 h_3 h 3 , ϑ ˉ \bar{\vartheta} ϑ ˉ with weights 13 / 1000 13/1000 13/1000 , 987 / 1000 987/1000 987/1000 . The component bounds above and the strict comparisons (F.5)–(F.6) give ψ ( G × H ) ≤ T 13 / 1000 < L \psi(G\times H)\le T_{13/1000}<L ψ ( G × H ) ≤ T 13/1000 < L . Every spectral point bounds capacity from above, so ψ ( G ) , ψ ( H ) ≥ 27 \psi(G),\psi(H)\ge\sqrt{27} ψ ( G ) , ψ ( H ) ≥ 27 . To bound their values from above, the identity fitting matrix gives h 3 ( D ) ≤ 27 h_3(D)\le27 h 3 ( D ) ≤ 27 , and the maximum rule gives h 3 ( G ) ≤ 27 h_3(G)\le27 h 3 ( G ) ≤ 27 . The existing certificates also give ϑ ˉ ( G ) ≤ 16 / 3 \bar{\vartheta}(G)\le16/3 ϑ ˉ ( G ) ≤ 16/3 , h 3 ( H ) ≤ 11 / 2 h_3(H)\le11/2 h 3 ( H ) ≤ 11/2 and ϑ ˉ ( H ) ≤ q < 11 / 2 \bar{\vartheta}(H)\le q<11/2 ϑ ˉ ( H ) ≤ q < 11/2 . Thus the same interpolant satisfies
ψ ( G ) ≤ 27 13 / 1000 ( 16 / 3 ) 987 / 1000 ≤ 13 1000 27 + 987 1000 16 3 = 1123 200 < 6 , \psi(G)\le27^{13/1000}(16/3)^{987/1000}\le\frac{13}{1000}27+\frac{987}{1000}\frac{16}{3}=\frac{1123}{200}<6, ψ ( G ) ≤ 2 7 13/1000 ( 16/3 ) 987/1000 ≤ 1000 13 27 + 1000 987 3 16 = 200 1123 < 6 ,
by the weighted arithmetic–geometric mean inequality, while
ψ ( H ) ≤ ( 11 / 2 ) 13 / 1000 q 987 / 1000 < 11 / 2 < 6. \psi(H)\le(11/2)^{13/1000}q^{987/1000}<11/2<6. ψ ( H ) ≤ ( 11/2 ) 13/1000 q 987/1000 < 11/2 < 6.
Thus one spectral point has product value below 27 \sqrt{27} 27 and both factor values in [ 27 , 6 ) [\sqrt{27},6) [ 27 , 6 ) , as asserted in § 5 .
Compact integer matrix certificates
The scales and diagonals are those in Subsec. F.4. Every edge entry is minus the scale. Only nonedge entries remain to be specified. In each table, i : j = value i:j=\text{value} i : j = value gives an entry at an unordered pair { i , j } \{i,j\} { i , j } ; extend it to the whole orbit under the stated permutations, and set M j i = M i j M_{ji}=M_{ij} M j i = M ij . For the group Γ \Gamma Γ generated by those permutations, this pair orbit is { { g ( i ) , g ( j ) } : g ∈ Γ } \{\{g(i),g(j)\}:g\in\Gamma\} {{ g ( i ) , g ( j )} : g ∈ Γ } . Each nonedge orbit occurs exactly once.
The two source matrices
Both B B B and D D D are preserved by the permutations
a = ( 45 ) ( 69 ) ( 7 11 ) ( 8 10 ) ( 17 22 ) ( 18 23 ) ( 19 24 ) ( 20 25 ) ( 21 26 ) a=(45)(69)(7\,11)(8\,10)(17\,22)(18\,23)(19\,24)(20\,25)(21\,26) a = ( 45 ) ( 69 ) ( 7 11 ) ( 8 10 ) ( 17 22 ) ( 18 23 ) ( 19 24 ) ( 20 25 ) ( 21 26 )
b 0 = ( 0 17 ) ( 1 19 ) ( 4 23 ) ( 6 25 ) ( 7 12 ) ( 8 26 ) ( 11 16 ) ( 13 24 ) ( 14 22 ) b_0=(0\,17)(1\,19)(4\,23)(6\,25)(7\,12)(8\,26)(11\,16)(13\,24)(14\,22) b 0 = ( 0 17 ) ( 1 19 ) ( 4 23 ) ( 6 25 ) ( 7 12 ) ( 8 26 ) ( 11 16 ) ( 13 24 ) ( 14 22 )
c = ( 0 16 ) ( 2 15 ) ( 4 25 ) ( 5 20 ) ( 6 23 ) ( 7 22 ) ( 9 18 ) ( 11 17 ) ( 12 14 ) . c=(0\,16)(2\,15)(4\,25)(5\,20)(6\,23)(7\,22)(9\,18)(11\,17)(12\,14). c = ( 0 16 ) ( 2 15 ) ( 4 25 ) ( 5 20 ) ( 6 23 ) ( 7 22 ) ( 9 18 ) ( 11 17 ) ( 12 14 ) .
They generate a group Γ \Gamma Γ of order 16. The following 23 and 19 entries determine M B M_B M B and M D M_D M D , respectively.
Source certificate M B M_B M B : 0: 1=24 2=6 7=15 8=22 14=−9 16=12 18=18 19=27 20=−2 1: 3=−31 4=4 19=11 21=5 2: 3=−4 4=20 8=27 3: 4=35 4: 6=2 8=−20 9=19 23=23 26=34 8: 10=6
Complement certificate M D M_D M D :
0: 3=92395858 4=145133660 6=−30688165 12=49988928 13=182327057 15=132541340 17=84507591 21=76315484 1: 2=3087050 6=138042021 8=109278319 13=−87574439 2: 6=127958661 15=−3681718 3: 8=40039826 4: 5=47798171 10=83490663 25=123407703 8: 26=−16181236
Here is an elementary reduction of their positivity checks. Write A A A , B 0 B_0 B 0 , C C C for the permutation matrices of a a a , b 0 b_0 b 0 , c c c , and put Z = ( A B 0 ) 2 Z=(AB_0)^2 Z = ( A B 0 ) 2 . These are symmetric involutions; C C C , Z Z Z commute with A A A , B 0 B_0 B 0 , and A B 0 = Z B 0 A AB_0=ZB_0A A B 0 = Z B 0 A . Thus A A A and B 0 B_0 B 0 commute on the Z = + I Z=+I Z = + I eigenspace and anticommute on the Z = − I Z=-I Z = − I eigenspace.
Let ε \varepsilon ε , δ \delta δ , α \alpha α , β ∈ { + 1 , − 1 } \beta\in\{+1,-1\} β ∈ { + 1 , − 1 } label the eigenvalues of Z Z Z , C C C , A A A , B 0 B_0 B 0 , respectively. When ε = + 1 \varepsilon=+1 ε = + 1 , the simultaneous eigenspaces of these four commuting symmetric matrices form an orthogonal decomposition. When ε = − 1 \varepsilon=-1 ε = − 1 , decompose instead by the eigenvalues δ , α \delta,\alpha δ , α of C , A C,A C , A . The orthogonal map B 0 B_0 B 0 carries each such space onto the space with signs δ , − α \delta,-\alpha δ , − α . A Γ \Gamma Γ -invariant symmetric matrix commutes with every generator, preserves these spaces, and has orthogonally equivalent restrictions on each paired set of spaces. It therefore suffices to check one member of each pair, explaining the multiplicity 2 below.
To obtain explicit integer bases, apply
( I + β B 0 ) ( I + α A ) ( I + δ C ) ( I + ε Z ) (I+\beta B_0)(I+\alpha A)(I+\delta C)(I+\varepsilon Z) ( I + β B 0 ) ( I + α A ) ( I + δ C ) ( I + εZ )
to e 0 , e 1 , … , e 26 e_0,e_1,\ldots,e_{26} e 0 , e 1 , … , e 26 when ε = + 1 \varepsilon=+1 ε = + 1 , and omit the first factor when ε = − 1 \varepsilon=-1 ε = − 1 . Divide each nonzero column by the gcd of its entries, then retain the first linearly independent columns. Denote the resulting basis matrix by P P P . The nonzero spaces are listed below; when ε = − 1 \varepsilon=-1 ε = − 1 , it suffices to take α = + 1 \alpha=+1 α = + 1 , with multiplicity 2. The dimensions, counted with multiplicity, sum to 27.
For each certificate, P T M X P P^{T}M_XP P T M X P represents the restricted quadratic form in the chosen basis, which need not be orthonormal. Its positive definiteness is therefore equivalent to that of the restriction. Divide this matrix by the positive gcd of its entries. The last column records the leading principal minors, the determinants of the upper-left square submatrices, for the resulting M B M_B M B blocks; all are positive. Applying the exact elimination below to the M D M_D M D blocks likewise gives only positive minors.
Table 1 (PDF p. 35).
Thus both source certificates are positive definite, using blocks of order at most six.
The partner matrix
On H H H , let σ \sigma σ fix 0, 12, 28 and send every other vertex v v v to 29 − v 29-v 29 − v . It preserves adjacency. The next 91 entries, extended under σ \sigma σ , specify M H M_H M H .
0: 3=-92182906 5=112385240 9=105366413 10=260048876 11=-64530825 14=103723987 28=24358075 2: 3=66703246 11=207795723 13=104538630 14=-136454182 16=177512886 18=115342751 19=-34383691 20=-100268450 21=76229467 24=-95624150 25=120690256 26=152316144 27=18986268 28=103951980 3: 4=-35794660 5=-98567795 6=149505933 7=190124261 10=-22994873 12=66710199 13=124899718 16=61341650 18=120482232 19=-19609272 21=-23529434 24=-98379162 25=42147361 4: 9=272941041 11=23305245 12=-70035550 14=241110784 16=61213470 19=135393685 21=30684152 24=262861878 5: 8=35191781 10=321011184 14=-104169070 15=375111138 20=418775902 23=-98757666 28=-47386121 6: 7=381208558 11=-42891154 12=337627573 13=-146194020 14=-78782821 16=19526989 19=-86283590 21=90671780 22=187815754 23=202130330 28=-36203985 7: 8=-59663804 9=-100785398 12=291996527 15=-44507231 16=55398098 21=117706337 22=165147825 8: 11=-56920029 13=259229426 14=-47902526 15=57463096 18=183702360 19=-222235396 20=41480973 21=10556935 28=92833206 9: 14=379995036 18=-98046773 19=316558361 28=-53434665 10: 12=-37639343 14=-98004443 15=294664038 16=-99343891 18=-90692258 19=60606640 11: 16=300836730 18=35163766 28=237971338 13: 14=-57898358 28=23099334
For the positivity check, order the vertices as F F F , P P P , σ ( P ) \sigma(P) σ ( P ) , where
F = ( 0 , 12 , 28 ) , P = ( 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 13 , 14 ) . F=(0,12,28),\qquad P=(2,3,4,5,6,7,8,9,10,11,13,14). F = ( 0 , 12 , 28 ) , P = ( 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 13 , 14 ) .
The invariant matrix has the form
M H = ( E F 0 F 0 F 0 T J K F 0 T K J ) . M_H=
\begin{pmatrix}
E & F_0 & F_0\\
F_0^{\mathsf T} & J & K\\
F_0^{\mathsf T} & K & J
\end{pmatrix}. M H = E F 0 T F 0 T F 0 J K F 0 K J .
Its quadratic form splits into symmetric and antisymmetric coordinates. Consequently it is positive definite if and only if
S = ( 2 E 2 F 0 2 F 0 T J + K ) and T = J − K S=\begin{pmatrix}
2E & 2F_0\\
2F_0^{\mathsf T} & J+K
\end{pmatrix}
\qquad\text{and}\qquad
T=J-K S = ( 2 E 2 F 0 T 2 F 0 J + K ) and T = J − K
are positive definite. Indeed, for coordinates ( x , y , z ) (x,y,z) ( x , y , z ) of dimensions 3, 12, 12, respectively,
( x y z ) T M H ( x y z ) = 1 2 ( x y + z ) T S ( x y + z ) + 1 2 ( y − z ) T T ( y − z ) . \begin{pmatrix}x\\y\\z\end{pmatrix}^{\mathsf T}
M_H
\begin{pmatrix}x\\y\\z\end{pmatrix}
=
\frac{1}{2}
\begin{pmatrix}x\\y+z\end{pmatrix}^{\mathsf T}
S
\begin{pmatrix}x\\y+z\end{pmatrix}
+\frac{1}{2}(y-z)^{\mathsf T}T(y-z). x y z T M H x y z = 2 1 ( x y + z ) T S ( x y + z ) + 2 1 ( y − z ) T T ( y − z ) .
The change of variables ( x , y , z ) ↦ ( x , y + z , y − z ) (x,y,z)\mapsto(x,y+z,y-z) ( x , y , z ) ↦ ( x , y + z , y − z ) is invertible, which proves the equivalence. Exact elimination gives 15 and 12 positive leading principal minors, respectively, proving that M H M_H M H is positive definite.
Exact verification and reproducibility
All entries are specified above. The permutations, orbit coverage, graph edges and block dimensions are finite checks. For positive definiteness, we use Bareiss’s fraction-free elimination [3 ] . Sylvester’s determinant identity shows that, at stage k k k , pivot is the leading principal minor of order k + 1 k + 1 k + 1 and all divisions are exact. Positivity of these minors proves positive definiteness by Sylvester’s criterion.
def positive_definite(M):
n = len(M)
assert all(len(row) == n for row in M)
assert all(M[i][j] == M[j][i]
for i in range(n) for j in range(n))
T = [row[:] for row in M]
previous = 1
for k in range(n):
pivot = T[k][k]
assert pivot > 0
for i in range(k + 1, n):
for j in range(i, n):
num = pivot*T[i][j] - T[i][k]*T[k][j]
assert num % previous == 0
T[i][j] = T[j][i] = num // previous
previous = pivot
return n
The following code checks the strict scalar comparisons.
from fractions import Fraction as F
b = F(32437757, 6250000)
q = F(12991403, 2500000)
L = F(5193957, 1000000)
assert F(5)**13 * q**987 < L**1000
assert F(11, 2)**13 * b**987 < L**1000
assert L*L < 27 and max(F(16, 3), b, q) < 6
The verification programs and machine-readable data are available in the accompanying repository [30 ] . The program verification/check_subsix.py verifies all finite inputs and the symmetry reductions. The independent verification/audit_subsix_from_tex.py reconstructs the printed data and checks the full matrices by rational L D L T LDLT L D L T factorization. Run either with Python 3.11 or later and assertions enabled: do not pass -O or set PYTHONOPTIMIZE. Only the standard library is required. Both checkers use exact arithmetic, without floating-point operations or a numerical solver. They verify the matrix certificates used by the analytical interpolation argument.
AI assistance and verification workflow. OpenAI Codex assisted with the development and review of the verification programs and with exploration of candidate constructions and certificates. The archived inputs are the explicit graph definitions, finite codes and integer or rational certificate entries printed in these appendices. The programs check these fixed inputs; they do not rely on an AI service, a numerical solver or an AI-generated assessment of correctness at run time. In particular, the source-derived checker reconstructs the printed matrices independently of the modular checker. Integer and rational computations establish the finite certificate inequalities. Decimal evaluation in the uniform-threshold audit is diagnostic only. The spectral interpolation and asymptotic arguments are proved analytically in the appendices and are not certified by these finite programs.
Proof of Theorem 2(2): coverage of real thresholds
This appendix proves the uniform threshold statement in Thm. 2(2). We construct graph pairs covering overlapping ranges of separating thresholds, then extend this coverage to every real threshold from 6.0101 by joining complete graphs.
This appendix combines an analytical construction with computer-assisted checks of finite graph data and threshold inequalities. OpenAI Codex assisted with exploring the constructions and with developing and reviewing the verification code. The finite threshold comparisons and interval overlaps are checked using exact integer and rational arithmetic; the extension to all thresholds in the claimed range is proved analytically.
Theorem G.1 (Failure at every real threshold from 6.0101). For every real t ≥ 6.0101 t \ge6.0101 t ≥ 6.0101 , there are finite simple graphs G G G , H H H such that
COR ( G × H ) < t < min { COR ( G ) , COR ( H ) } . \operatorname{COR}(G \times H) < t < \min\{\operatorname{COR}(G),\operatorname{COR}(H)\}. COR ( G × H ) < t < min { COR ( G ) , COR ( H )} . In particular, f C ( t ) < t f_{\mathrm{C}}(t) < t f C ( t ) < t throughout this range.
The proof gives the stronger range t > T 0 t > T_0 t > T 0 , where T 0 = 6.0100886404 … T_0 = 6.0100886404\ldots T 0 = 6.0100886404 … is defined exactly in (G.3). We first optimize a counterexample near six, then use eight witnesses to cover a full unit interval and extend that cover by joining complete graphs. The optimization is analytical, and all comparisons for the stated decimal cutoff use exact integer arithmetic.
We use the weighted product bound (D.1) from Supplementary App. § 15 . Throughout this section, put
A = U 6 , D = A ‾ , h ( X ) = φ F 2 ( X ) , q ( X ) = ϑ ( X ‾ ) . A = U_6,\qquad D = \overline{A},\qquad h(X) = \varphi_{\mathrm{F}_2}(X),\qquad q(X) = \vartheta(\overline{X}). A = U 6 , D = A , h ( X ) = φ F 2 ( X ) , q ( X ) = ϑ ( X ) .
Both h h h and q q q are OR spectral points. The constructions in Lems. E.1 and E.3 give
h ( A ) = 6 , q ( D ) ≤ 4 , COR ( Q ) ≥ 16 1 / 3 , q ( Q ) ≤ 8 / 3. h(A) = 6,\qquad q(D) \le4,\qquad\operatorname{COR}(Q) \ge16^{1/3},\qquad q(Q) \le8/3. h ( A ) = 6 , q ( D ) ≤ 4 , COR ( Q ) ≥ 1 6 1/3 , q ( Q ) ≤ 8/3.
We first provide the remaining small-graph estimates.
Fractional colourings and a 37-vertex partner
We use the fractional-colouring definitions in Supplementary App. § 14 and the inequality h ( X ) ≤ χ f ( X ) h(X) \le\chi_f(X) h ( X ) ≤ χ f ( X ) proved in (C.2) by the coordinate-vector fitting construction. In particular,
h ( D ) ≤ χ f ( D ) ≤ 16 3 . (31) h(D) \le\chi_f(D) \le\frac{16}{3}. \tag*{(31)} h ( D ) ≤ χ f ( D ) ≤ 3 16 . (31)
Indeed, A A A is vertex-transitive. Coordinate permutations and the maps T v ( x ) = x + ( x ⋅ v ) v T_v(x) = x + (x \cdot v)v T v ( x ) = x + ( x ⋅ v ) v for even-weight v v v preserve dot products and odd weight; moreover, T v 2 T_v^2 T v 2 is the identity. Taking v = e 1 + e 2 + e 3 + e 4 v = e_1 + e_2 + e_3 + e_4 v = e 1 + e 2 + e 3 + e 4 or v = 1 v = \mathbf{1} v = 1 sends e 1 e_1 e 1 to a vector of weight three or five. Permutations then reach every odd-weight vector. Thus D D D is also vertex-transitive. Averaging its independent six-set { e 1 , … , e 6 } \{e_1,\ldots,e_6\} { e 1 , … , e 6 } over the automorphism group covers every vertex equally. Normalizing this coverage to one gives a fractional colouring of total weight 32 / 6 32/6 32/6 , as explained in Supplementary App. § 14 , and proves (G.1).
Lemma G.1 (A self-complementary circulant). Let R R R be the graph on Z / 37 Z \mathbb{Z}/37\mathbb{Z} Z /37 Z in which two vertices are adjacent when their undirected cyclic distance belongs to
S = { 6 , 7 , 8 , 9 , 10 , 12 , 13 , 15 , 18 } . S = \{6,7,8,9,10,12,13,15,18\}. S = { 6 , 7 , 8 , 9 , 10 , 12 , 13 , 15 , 18 } . Then
COR ( R ) = q ( R ) = 37 , h ( R ) ≤ χ f ( R ) = 37 6 . \operatorname{COR}(R) = q(R) = \sqrt{37},\qquad h(R) \le\chi_f(R) = \frac{37}{6}. COR ( R ) = q ( R ) = 37 , h ( R ) ≤ χ f ( R ) = 6 37 .
Proof. Multiplication by six exchanges the two members of each distance pair
( 1 , 6 ) , ( 2 , 12 ) , ( 3 , 18 ) , ( 4 , 13 ) , ( 5 , 7 ) , ( 8 , 11 ) , ( 9 , 17 ) , ( 10 , 14 ) , ( 15 , 16 ) . (1,6),(2,12),(3,18),(4,13),(5,7),(8,11),(9,17),(10,14),(15,16). ( 1 , 6 ) , ( 2 , 12 ) , ( 3 , 18 ) , ( 4 , 13 ) , ( 5 , 7 ) , ( 8 , 11 ) , ( 9 , 17 ) , ( 10 , 14 ) , ( 15 , 16 ) .
Since S S S chooses one member of every pair, this map is an isomorphism R ≅ R ‾ R \cong\overline{R} R ≅ R . Consequently the 37 words ( i , 6 i ) (i,6i) ( i , 6 i ) form a clique in R ∨ R ‾ R \vee\overline{R} R ∨ R , proving COR ( R ) ≥ 37 \operatorname{COR}(R) \ge\sqrt{37} COR ( R ) ≥ 37 . The graph is vertex-transitive, so Lovász’s identity ϑ ( R ) ϑ ( R ‾ ) = 37 \vartheta(R)\vartheta(\overline{R})=37 ϑ ( R ) ϑ ( R ) = 37 [17 ] , together with self-complementarity, gives the matching theta upper bound.
The set B = { 0 , 6 , 12 , 18 , 24 , 30 } B=\{0,6,12,18,24,30\} B = { 0 , 6 , 12 , 18 , 24 , 30 } is a six-clique because its nonzero undirected differences lie in { 6 , 12 , 18 , 13 , 7 } \{6,12,18,13,7\} { 6 , 12 , 18 , 13 , 7 } . Thus 6 B 6B 6 B is an independent six-set. Its 37 translates cover every vertex six times, giving χ f ( R ) ≤ 37 / 6 \chi_f(R)\le37/6 χ f ( R ) ≤ 37/6 . Conversely, every independent set has size at most ϑ ( R ) = 37 < 7 \vartheta(R)=\sqrt{37}<7 ϑ ( R ) = 37 < 7 , hence at most six. Summing the covering constraints of any fractional colouring gives 37 ≤ 6 χ f ( R ) 37\le6\chi_f(R) 37 ≤ 6 χ f ( R ) . Thus χ f ( R ) = 37 / 6 \chi_f(R)=37/6 χ f ( R ) = 37/6 , proving the claim.
The initial pair near six
Put G = A ⊔ ( D ⊕ K 1 ) G=A\sqcup(D\oplus K_1) G = A ⊔ ( D ⊕ K 1 ) . For any φ ∈ Δ O R \varphi\in\Delta_{\mathrm{OR}} φ ∈ Δ OR , write x = φ ( A ) x=\varphi(A) x = φ ( A ) and y = φ ( D ) y=\varphi(D) y = φ ( D ) . The 32 diagonal words in A ∨ D A\vee D A ∨ D form a clique, so x y ≥ 32 xy\ge32 x y ≥ 32 . The join and maximum rules give φ ( G ) = max { x , y + 1 } \varphi(G)=\max\{x,y+1\} φ ( G ) = max { x , y + 1 } . If this maximum is r r r , then 32 ≤ x y ≤ r ( r − 1 ) 32\le xy\le r(r-1) 32 ≤ x y ≤ r ( r − 1 ) , and hence
COR ( G ) ≥ 1 + 129 2 > 37 = COR ( R ) . (32) \operatorname{COR}(G)\ge\frac{1+\sqrt{129}}{2}>\sqrt{37}=\operatorname{COR}(R). \tag*{(32)} COR ( G ) ≥ 2 1 + 129 > 37 = COR ( R ) . (32)
The projections give the spectral upper bounds
The geometric bound in (D.1) gives
COR ( G × R ) ≤ min 0 ≤ λ ≤ 1 max { 6 λ ( 37 ) 1 − λ , ( 37 / 6 ) λ 5 1 − λ } . \operatorname{COR}(G\times R)\le\min_{0\le\lambda\le1}\max\left\{6^\lambda(\sqrt{37})^{1-\lambda},(37/6)^\lambda5^{1-\lambda}\right\}. COR ( G × R ) ≤ 0 ≤ λ ≤ 1 min max { 6 λ ( 37 ) 1 − λ , ( 37/6 ) λ 5 1 − λ } .
Put d = log ( 37 / 6 ) > 0 d=\log(\sqrt{37}/6)>0 d = log ( 37 /6 ) > 0 and ℓ = log ( 6 / 5 ) > 0 \ell=\log(6/5)>0 ℓ = log ( 6/5 ) > 0 , using natural logarithms. After subtracting log 6 \log6 log 6 , the logarithms of the two branches are ( 1 − λ ) d (1-\lambda)d ( 1 − λ ) d and 2 λ d − ( 1 − λ ) ℓ 2\lambda d-(1-\lambda)\ell 2 λ d − ( 1 − λ ) ℓ . The first decreases and the second increases with λ \lambda λ . They agree at λ ∗ = ( ℓ + d ) / ( ℓ + 3 d ) ∈ ( 0 , 1 ) \lambda_*=(\ell+d)/(\ell+3d)\in(0,1) λ ∗ = ( ℓ + d ) / ( ℓ + 3 d ) ∈ ( 0 , 1 ) , which therefore minimizes their maximum. Consequently
COR ( G × R ) ≤ T 0 : = 6 exp ( 2 d 2 ℓ + 3 d ) = 6.0100886404 … (33) \operatorname{COR}(G\times R)\le T_0:=6\exp\left(\frac{2d^2}{\ell+3d}\right)=6.0100886404\ldots \tag*{(33)} COR ( G × R ) ≤ T 0 := 6 exp ( ℓ + 3 d 2 d 2 ) = 6.0100886404 … (33)
Together with (G.2), this proves failure at every threshold T 0 < t < 37 T_0<t<\sqrt{37} T 0 < t < 37 .
To prove T 0 < 6.0101 T_0<6.0101 T 0 < 6.0101 exactly, without using the decimal approximation in (G.3), use λ = 93 / 106 \lambda=93/106 λ = 93/106 in the geometric bound. Direct integer exponentiation gives
6 186 37 13 10000 212 < 60101 212 , 37 93 5 13 10000 106 < 6 93 60101 106 . (34) \begin{aligned}
6^{186}37^{13}10000^{212}&<60101^{212},\\
37^{93}5^{13}10000^{106}&<6^{93}60101^{106}. \tag*{(34)}
\end{aligned} 6 186 3 7 13 1000 0 212 3 7 93 5 13 1000 0 106 < 6010 1 212 , < 6 93 6010 1 106 . (34)
Taking the positive 212th and 106th roots, respectively, shows that both branches are strictly below 60101 / 10000 = 6.0101 60101/10000=6.0101 60101/10000 = 6.0101 . The supplementary script verification/check_uniform_cutoff.py in the accompanying repository [30 ] checks exactly these two integer comparisons. The same repository includes verification/check_exact.py and verification/audit_uniform_independent.py, which check the finite graph inputs and interval comparisons used below.
For the interval cover below, we retain a simpler arithmetic bound. Use (D.1) with λ = 13 / 15 \lambda= 13/15 λ = 13/15 and 37 < 73 / 12 \sqrt{37} < 73/12 37 < 73/12 . The two arithmetic means agree, giving
COR ( G × R ) ≤ 13 15 6 + 2 15 73 12 = 13 15 37 6 + 2 15 5 = 541 90 . \operatorname{COR}(G \times R) \le\frac{13}{15}6+\frac{2}{15}\frac{73}{12}=\frac{13}{15}\frac{37}{6}+\frac{2}{15}5=\frac{541}{90}. COR ( G × R ) ≤ 15 13 6 + 15 2 12 73 = 15 13 6 37 + 15 2 5 = 90 541 .
Thus this pair also supplies the interval ( 541 / 90 , 37 ) (541/90,\sqrt{37}) ( 541/90 , 37 ) . The next three subsections cover every t > 541 / 90 t > 541/90 t > 541/90 ; combining that cover with the optimized initial interval proves the theorem.
Write C n C_n C n for the cycle on Z / n Z \mathbb{Z}/n\mathbb{Z} Z / n Z , with two vertices adjacent when their difference is 1 1 1 or − 1 -1 − 1 modulo n n n (n ≥ 3 n \ge3 n ≥ 3 ). For the pentagon C 5 C_5 C 5 , the standard theta calculation and its five-word square code give
COR ( C 5 ) = q ( C 5 ) = 5 , h ( C 5 ) ≤ χ f ( C 5 ) = 5 / 2. \operatorname{COR}(C_5)=q(C_5)=\sqrt{5},\qquad h(C_5)\le\chi_f(C_5)=5/2. COR ( C 5 ) = q ( C 5 ) = 5 , h ( C 5 ) ≤ χ f ( C 5 ) = 5/2.
Explicitly, the words ( i , 2 i ) (i,2i) ( i , 2 i ) , for i ∈ Z / 5 Z i \in\mathbb{Z}/5\mathbb{Z} i ∈ Z /5 Z , form a clique in C 5 ∨ C 5 C_5 \lor C_5 C 5 ∨ C 5 . The upper bound is Lovász’s pentagon calculation [17 ] ; the five translates of an independent pair give the fractional colouring.
Write Z = C 9 ‾ Z=\overline{C_9} Z = C 9 . We need only
COR ( Z ) ≥ 81 1 / 3 , h ( Z ) ≤ 9 / 2 , q ( Z ) < 22 / 5. \operatorname{COR}(Z)\ge81^{1/3},\qquad h(Z)\le9/2,\qquad q(Z)<22/5. COR ( Z ) ≥ 8 1 1/3 , h ( Z ) ≤ 9/2 , q ( Z ) < 22/5.
For the first inequality, take the 81 words
( x , y , 2 x + 4 y ) , x , y ∈ Z / 9 Z . (x,y,2x+4y),\qquad x,y\in\mathbb{Z}/9\mathbb{Z}. ( x , y , 2 x + 4 y ) , x , y ∈ Z /9 Z .
If two distinct words were nonadjacent in Z ∨ 3 Z^{\vee3} Z ∨ 3 , their coordinate differences would have representatives a , b , c ∈ { − 1 , 0 , 1 } a,b,c\in\{-1,0,1\} a , b , c ∈ { − 1 , 0 , 1 } with c − 2 a − 4 b ≡ 0 ( m o d 9 ) c-2a-4b\equiv0\pmod9 c − 2 a − 4 b ≡ 0 ( mod 9 ) . Its absolute value is at most seven, so this is an integer equality. Since 4 > 2 + 1 4>2+1 4 > 2 + 1 and 2 > 1 2>1 2 > 1 , it forces a = b = c = 0 a=b=c=0 a = b = c = 0 , a contradiction. The nine translates of an edge of C 9 C_9 C 9 are independent pairs of Z Z Z , proving the colouring bound 9 / 2 9/2 9/2 . Finally, the odd-cycle theta formula [17 ] gives
q ( Z ) = ϑ ( C 9 ) = 9 cos ( π / 9 ) 1 + cos ( π / 9 ) < 22 5 . q(Z)=\vartheta(C_9)=\frac{9\cos(\pi/9)}{1+\cos(\pi/9)}<\frac{22}{5}. q ( Z ) = ϑ ( C 9 ) = 1 + cos ( π /9 ) 9 cos ( π /9 ) < 5 22 .
For a rational verification of the strict inequality, put x = π / 9 x=\pi/9 x = π /9 . Since 1 / 3 < x < 1 1/3<x<1 1/3 < x < 1 , the alternating Taylor estimate gives
cos x ≤ 1 − x 2 2 + x 4 24 ≤ 1 − 11 x 2 24 < 205 216 , 9 ( 205 / 216 ) 1 + 205 / 216 = 1845 421 < 22 5 . \cos x\le1-\frac{x^2}{2}+\frac{x^4}{24}\le1-\frac{11x^2}{24}<\frac{205}{216},\qquad\frac{9(205/216)}{1+205/216}=\frac{1845}{421}<\frac{22}{5}. cos x ≤ 1 − 2 x 2 + 24 x 4 ≤ 1 − 24 11 x 2 < 216 205 , 1 + 205/216 9 ( 205/216 ) = 421 1845 < 5 22 .
Balancing the bounds and adding cliques
For an auxiliary graph J J J , define
G J = A ⊔ ( D ⊕ J ) , ρ b = b + b 2 + 128 2 . G_J=A\sqcup(D\oplus J),\qquad\rho_b=\frac{b+\sqrt{b^2+128}}{2}. G J = A ⊔ ( D ⊕ J ) , ρ b = 2 b + b 2 + 128 .
If COR ( J ) ≥ b > 0 \operatorname{COR}(J)\ge b>0 COR ( J ) ≥ b > 0 , then Lem. E.4 gives COR ( G J ) ≥ ρ b \operatorname{COR}(G_J)\ge\rho_b COR ( G J ) ≥ ρ b . The following lemma chooses the interpolation weight once and for all from three projection bounds.
Lemma G.2 (Balancing and adding cliques). Let COR ( J ) ≥ b > 0 \operatorname{COR}(J) \ge b > 0 COR ( J ) ≥ b > 0 , and let H H H be a partner graph. Suppose a > 6 a > 6 a > 6 and s > d s > d s > d satisfy
s ≥ q ( H ) , a ≥ min { h ( D ⊕ J ) , h ( H ) } , d ≥ q ( D ⊕ J ) . s \ge q(H), \qquad a \ge\min\{h(D \mathbin{\oplus} J), h(H)\}, \qquad d \ge q(D \mathbin{\oplus} J). s ≥ q ( H ) , a ≥ min { h ( D ⊕ J ) , h ( H )} , d ≥ q ( D ⊕ J ) . Put
U = a s − 6 d a − 6 + s − d . (35) U = \frac{as-6d}{a-6+s-d}. \tag*{(35)} U = a − 6 + s − d a s − 6 d . (35) For every integer j ≥ 0 j \ge0 j ≥ 0 , there are graphs G ( j ) G^{(j)} G ( j ) , H ( j ) H^{(j)} H ( j ) with
COR ( G ( j ) × H ( j ) ) ≤ U + j , COR ( G ( j ) ) ≥ ρ b + j , COR ( H ( j ) ) = COR ( H ) + j . \operatorname{COR}(G^{(j)} \times H^{(j)}) \le U+j, \qquad\operatorname{COR}(G^{(j)}) \ge\rho b+j, \qquad\operatorname{COR}(H^{(j)}) = \operatorname{COR}(H)+j. COR ( G ( j ) × H ( j ) ) ≤ U + j , COR ( G ( j ) ) ≥ ρ b + j , COR ( H ( j ) ) = COR ( H ) + j . Proof. Take
G ( j ) = ( A ⊕ K j ) ⊔ ( D ⊕ J ⊕ K j ) , H ( j ) = H ⊕ K j , G^{(j)}=(A\mathbin{\oplus}K_j)\mathbin{\mathbin{\sqcup}}(D\mathbin{\oplus}J\mathbin{\oplus}K_j), \qquad H^{(j)}=H\mathbin{\oplus}K_j, G ( j ) = ( A ⊕ K j ) ⊔ ( D ⊕ J ⊕ K j ) , H ( j ) = H ⊕ K j , omitting K 0 K_0 K 0 . The categorical product distributes over disjoint union. Projection to the factors and additivity under join give the following bounds on its two components.
Choose λ = ( s − d ) / ( a − 6 + s − d ) ∈ ( 0 , 1 ) \lambda=(s-d)/(a-6+s-d)\in(0,1) λ = ( s − d ) / ( a − 6 + s − d ) ∈ ( 0 , 1 ) . By construction,
6 λ + s ( 1 − λ ) = a λ + d ( 1 − λ ) = U . 6\lambda+s(1-\lambda)=a\lambda+d(1-\lambda)=U. 6 λ + s ( 1 − λ ) = aλ + d ( 1 − λ ) = U . Apply the spectral interpolation inequality (4) to h , q h,q h , q with these weights. The resulting single spectral point, the maximum rule, and the weighted arithmetic–geometric mean bound the product capacity by U + j U+j U + j . Finally, every spectral point takes value φ ( G J ) + j \varphi(G_J)+j φ ( G J ) + j on G ( j ) G^{(j)} G ( j ) and value φ ( H ) + j \varphi(H)+j φ ( H ) + j on H ( j ) H^{(j)} H ( j ) . Taking spectral minima gives the two factor claims.
A single coverage table
In Tab. G.1, k C 5 kC_5 k C 5 means the join of k k k copies of C 5 C_5 C 5 , and every terminating decimal denotes an exact rational number. The columns s s s , a a a , d d d satisfy the preceding lemma, and U U U is given by (G.5). Each row gives
COR ( G J × H ) ≤ U < L < min { COR ( G J ) , COR ( H ) } . (36) \operatorname{COR}(G_J\times H)\le U<L<\min\{\operatorname{COR}(G_J),\operatorname{COR}(H)\}. \tag*{(36)} COR ( G J × H ) ≤ U < L < min { COR ( G J ) , COR ( H )} . (36)
Thus that row works for every threshold in the open interval ( U , L ) (U,L) ( U , L ) .
Here s s s bounds q ( H ) q(H) q ( H ) and d d d bounds q ( D ) + q ( J ) q(D)+q(J) q ( D ) + q ( J ) . For a a a , use h ( D ) + h ( J ) h(D)+h(J) h ( D ) + h ( J ) in rows 2 and 6, using (G.1), and h ( H ) h(H) h ( H ) in all other rows. All entries follow from the preceding graph bounds, additivity under join, and the elementary enclosures
2.235 < 5 < 2.24 , 2.5 < 16 1 / 3 , 4.325 < 81 1 / 3 , 2.235<\sqrt{5}<2.24,\qquad2.5<16^{1/3},\qquad4.325<81^{1/3}, 2.235 < 5 < 2.24 , 2.5 < 1 6 1/3 , 4.325 < 8 1 1/3 ,
and 6.08 < 37 < 73 / 12 6.08<\sqrt{37}<73/12 6.08 < 37 < 73/12 . Each follows by squaring or cubing.
For the first factor, L < ρ b L<\rho b L < ρ b follows from L > b L>b L > b and L ( L − b ) < 32 L(L-b)<32 L ( L − b ) < 32 . For each choice of J J J , it suffices to check the largest L L L . Using the respective lower bounds b = 1 , 2 , 2.235 , 2.5 b=1,2,2.235,2.5 b = 1 , 2 , 2.235 , 2.5 , we obtain
6.17 ( 6.17 − 1 ) = 31.8989 < 32 , 6.7 ( 6.7 − 2 ) = 31.49 < 32 , 6.17(6.17-1)=31.8989<32,\qquad6.7(6.7-2)=31.49<32, 6.17 ( 6.17 − 1 ) = 31.8989 < 32 , 6.7 ( 6.7 − 2 ) = 31.49 < 32 ,
6.88 ( 6.88 − 2.235 ) = 31.9576 < 32 , 7.02 ( 7.02 − 2.5 ) = 31.7304 < 32. 6.88(6.88-2.235)=31.9576<32,\qquad7.02(7.02-2.5)=31.7304<32. 6.88 ( 6.88 − 2.235 ) = 31.9576 < 32 , 7.02 ( 7.02 − 2.5 ) = 31.7304 < 32.
For the partners, the capacity lower bounds are, in row order,
37 , 4 + 5 , 4 + 5 , 2 + 81 1 / 3 , 2 + 2 5 , 3 5 , 7 , 1 + 37 . \sqrt{37},\ 4+\sqrt{5},\ 4+\sqrt{5},\ 2+81^{1/3},\ 2+2\sqrt{5},\ 3\sqrt{5},\ 7,\ 1+\sqrt{37}. 37 , 4 + 5 , 4 + 5 , 2 + 8 1 1/3 , 2 + 2 5 , 3 5 , 7 , 1 + 37 .
The same rational enclosures place each strictly above its listed L L L . This proves (G.6) for every row.
Table G.1. One formula certifies every interval ( U , L ) (U,L) ( U , L ) . The first factor is G J = A ⊔ ( D ⊕ J ) G_J=A\sqcup(D\oplus J) G J = A ⊔ ( D ⊕ J ) ; s , a , d s,a,d s , a , d are spectral projection bounds.
Completion of the proof of Thm. G.1. Write ( U i , L i ) (U_i,L_i) ( U i , L i ) for the intervals in Tab. G.1. Direct cross-multiplication gives U i < L i U_i<L_i U i < L i and U i + 1 < L i U_{i+1}<L_i U i + 1 < L i ; the smallest consecutive overlap is 6.325 − 234 / 37 = 1 / 1480 > 0 6.325-234/37=1/1480>0 6.325 − 234/37 = 1/1480 > 0 . Their union therefore contains ( 541 / 90 , 7.02 ) (541/90,7.02) ( 541/90 , 7.02 ) , an interval of length greater than one.
For any t > c : = 541 / 90 t>c:=541/90 t > c := 541/90 , choose j = ⌈ t − c ⌉ − 1 ≥ 0 j=\lceil t-c\rceil-1\geq0 j = ⌈ t − c ⌉ − 1 ≥ 0 . Then c < t − j ≤ c + 1 < 7.02 c<t-j\leq c+1<7.02 c < t − j ≤ c + 1 < 7.02 , so some row has U i < t − j < L i U_i<t-j<L_i U i < t − j < L i . Lem. G.2 gives
C O R ( G ( j ) × H ( j ) ) ≤ U i + j < t < L i + j < min { C O R ( G ( j ) ) , C O R ( H ( j ) ) } . C_{\mathrm{OR}}(G^{(j)}\times H^{(j)})\leq U_i+j<t<L_i+j<\min\{C_{\mathrm{OR}}(G^{(j)}),C_{\mathrm{OR}}(H^{(j)})\}. C OR ( G ( j ) × H ( j ) ) ≤ U i + j < t < L i + j < min { C OR ( G ( j ) ) , C OR ( H ( j ) )} .
Thus the same eight witnesses, extended by joining complete graphs, cover every t > 541 / 90 t>541/90 t > 541/90 .
The optimized initial pair covers ( T 0 , 37 ) (T_0,\sqrt{37}) ( T 0 , 37 ) , and (G.4) gives
T 0 < 6.0101 < 541 / 90 < 37 . T_0<6.0101<541/90<\sqrt{37}. T 0 < 6.0101 < 541/90 < 37 .
The two ranges overlap, so together they cover every t > T 0 t>T_0 t > T 0 . In particular they cover every t ≥ 6.0101 t\geq6.0101 t ≥ 6.0101 , including the stated endpoint. This proves the uniform clause of Thm. 2.
For the real-threshold spectral claim in § 5 , fix t ≥ 6.0101 t\geq6.0101 t ≥ 6.0101 and choose a pair G t , H t G_t,H_t G t , H t from the construction above. By (2) , there is a spectral point ψ t ∈ Δ O R \psi_t\in\Delta_{\mathrm{OR}} ψ t ∈ Δ OR attaining the capacity of G t × H t G_t\times H_t G t × H t . Since every spectral point bounds capacity from above, we obtain
ψ t ( G t × H t ) = C O R ( G t × H t ) < t < min { C O R ( G t ) , C O R ( H t ) } ≤ min { ψ t ( G t ) , ψ t ( H t ) } . \psi_t(G_t\times H_t)=C_{\mathrm{OR}}(G_t\times H_t)<t<\min\{C_{\mathrm{OR}}(G_t),C_{\mathrm{OR}}(H_t)\}\leq\min\{\psi_t(G_t),\psi_t(H_t)\}. ψ t ( G t × H t ) = C OR ( G t × H t ) < t < min { C OR ( G t ) , C OR ( H t )} ≤ min { ψ t ( G t ) , ψ t ( H t )} .
This is Simonyi’s implication [24 Thm. 8] applied to each pair. The choice of ψ t \psi_t ψ t may depend on t t t .
Scope of the sharper thresholds
The positive cases 1 and 2 recalled in Supplementary App. C, together with Thm. 1, show that the smallest integer value of the smaller factor capacity admitting a counterexample lies between 3 and 7. The unresolved exact integer minima are 3, . . . , 6. The pair in Sec. F has smaller factor capacity in [ 27 , 5.1965612 ] [\sqrt{27},5.1965612] [ 27 , 5.1965612 ] ; its exact value is unknown. The earlier pair in (G.2) has exact smaller factor capacity 37 \sqrt{37} 37 . By Lem. F.1, the sub-six pair gives failure at every threshold 5.193957 ≤ t < 27 5.193957\leq t<\sqrt{27} 5.193957 ≤ t < 27 , whereas this section covers every t > T 0 t>T_0 t > T 0 . A cover joining the lower interval to this upper ray is still missing. In particular, the strict-threshold formulation does not include t = 27 t=\sqrt{27} t = 27 merely from the lower bound min { C O R ( G ) , C O R ( H ) } ≥ 27 \min\{C_{\mathrm{OR}}(G),C_{\mathrm{OR}}(H)\}\geq\sqrt{27} min { C OR ( G ) , C OR ( H )} ≥ 27 , and the upper-ray proof does not include t = T 0 t=T_0 t = T 0 . This does not assert that each individual threshold between these endpoints is unresolved.
Neither result classifies all possible exact noninteger minimum capacities; no optimality is claimed. Polak’s circular-graph constructions provide, after complementation, graphs whose OR-capacities approach any integer r ≥ 3 r \ge3 r ≥ 3 from below [18 Chap. 9, Thms. 9.3.1 and 9.3.3] . These constructions do not determine whether the product identity holds at those capacities.
Proof of Theorem 3: asymptotic separation
This appendix proves the asymptotic separation in Thm. 3 . We construct graphs using several finite fields and choose their parameters so that both factor capacities grow while the product capacity is subpolynomial in the smaller factor capacity.
The next lemma provides both a large code and spectral bounds over several fields. Its polynomial-rank argument adapts Alon’s finite-field method [1 Secs. 3–4] . The edge sets need only cover the complete graph, so an edge may belong to more than one graph.
Lemma H.1 (A finite-field covering construction). Let P ≥ 2 P \ge2 P ≥ 2 be an integer, let q 1 , … , q k q_1,\ldots,q_k q 1 , … , q k be distinct primes in ( P , 2 P ) (P,2P) ( P , 2 P ) , and let 1 ≤ h < k 1 \le h < k 1 ≤ h < k . Set
L = P h + 1 , d = P L , n = ( d L ) , N = ( k h ) , D = d 2 P . L=P^{h+1}, \qquad d=PL, \qquad n=\binom{d}{L}, \qquad N=\binom{k}{h}, \qquad D=d^{2P}. L = P h + 1 , d = P L , n = ( L d ) , N = ( h k ) , D = d 2 P . There are graphs A S A_S A S , indexed by the h h h -element subsets S ⊆ { 1 , … , k } S \subseteq\{1,\ldots,k\} S ⊆ { 1 , … , k } , on a common set of n n n vertices, whose edges cover K n K_n K n and which satisfy
φ F q j ( A S ) ≤ D ( j ∉ S ) . (37) \varphi_{\mathbb{F}_{q_j}}(A_S) \le D \qquad(j \notin S). \tag*{(37)} φ F q j ( A S ) ≤ D ( j ∈ / S ) . (37) For their disjoint union F = ⨆ ∣ S ∣ = h A S F=\bigsqcup_{|S|=h} A_S F = ⨆ ∣ S ∣ = h A S , one has
COR ( F ) ≥ n 1 / N , COR ( F × K m ) ≤ D 1 − h / k m h / k ( m ≥ 1 ) . (38) \operatorname{COR}(F) \ge n^{1/N}, \qquad\operatorname{COR}(F \times K_m) \le D^{1-h/k}m^{h/k} \qquad(m \ge1). \tag*{(38)} COR ( F ) ≥ n 1/ N , COR ( F × K m ) ≤ D 1 − h / k m h / k ( m ≥ 1 ) . (38) Proof. Take the common vertex set to be ( [ d ] L ) \binom{[d]}{L} ( L [ d ] ) . For distinct vertices X , Y X,Y X , Y , put
B ( X , Y ) = { j : q j ∣ L − ∣ X ∩ Y ∣ } , X Y ∈ E ( A S ) ⟺ B ( X , Y ) ⊆ S . B(X,Y)=\{j:q_j \mid L-|X\cap Y|\}, \qquad XY \in E(A_S) \Longleftrightarrow B(X,Y) \subseteq S. B ( X , Y ) = { j : q j ∣ L − ∣ X ∩ Y ∣ } , X Y ∈ E ( A S ) ⟺ B ( X , Y ) ⊆ S . The positive integer L − ∣ X ∩ Y ∣ ≤ L L-|X\cap Y| \le L L − ∣ X ∩ Y ∣ ≤ L has at most h h h of the selected primes as divisors, since any h + 1 h+1 h + 1 of them have product strictly greater than P h + 1 = L P^{h+1}=L P h + 1 = L . Thus B ( X , Y ) B(X,Y) B ( X , Y ) is contained in some h h h -element set S S S , proving the covering condition.
Over F q j \mathbb{F}_{q_j} F q j define
M j ( X , Y ) = 1 − ( ∣ X ∩ Y ∣ − L ) q j − 1 . M_j(X,Y)=1-\left(|X\cap Y|-L\right)^{q_j-1}. M j ( X , Y ) = 1 − ( ∣ X ∩ Y ∣ − L ) q j − 1 . Its diagonal entries are 1. If X Y ∈ E ( A S ) XY \in E(A_S) X Y ∈ E ( A S ) and j ∉ S j \notin S j ∈ / S , then q j q_j q j does not divide L − ∣ X ∩ Y ∣ L-|X\cap Y| L − ∣ X ∩ Y ∣ , so Fermat’s theorem gives M j ( X , Y ) = 0 M_j(X,Y)=0 M j ( X , Y ) = 0 . Each row is a polynomial of degree at most q j − 1 q_j-1 q j − 1 in the incidence vector of Y Y Y , the zero-one vector recording membership in Y Y Y . On zero-one vectors, replacing every positive power of a variable by that variable leaves its value unchanged. The row space therefore lies in the common span of the evaluation vectors of squarefree monomials of degree at most q j − 1 q_j-1 q j − 1 . Explicitly, these are the vectors with entries Y ↦ 1 { T ⊆ Y } Y \mapsto\mathbf{1}\{T\subseteq Y\} Y ↦ 1 { T ⊆ Y } , indexed by subsets T ⊆ [ d ] T\subseteq[d] T ⊆ [ d ] with ∣ T ∣ ≤ q j − 1 |T|\le q_j-1 ∣ T ∣ ≤ q j − 1 . Since q j < 2 P ≤ d q_j<2P\le d q j < 2 P ≤ d , this gives
rank F q j M j ≤ ∑ ℓ = 0 q j − 1 ( d ℓ ) ≤ q j d q j − 1 ≤ d q j ≤ D . \operatorname{rank}_{\mathbb{F}_{q_j}} M_j \le\sum_{\ell=0}^{q_j-1}\binom{d}{\ell} \le q_jd^{q_j-1}\le d^{q_j}\le D. rank F q j M j ≤ ℓ = 0 ∑ q j − 1 ( ℓ d ) ≤ q j d q j − 1 ≤ d q j ≤ D . Lem. C.1 proves (H.1). For each vertex X X X , form the N N N -tuple of its copies in all graphs A S A_S A S . The covering condition makes these n n n tuples a clique in F ∨ N F^{\vee N} F ∨ N , giving the lower bound in (H.2). The upper bound is Lem. D.2 , with exceptional set S S S for graph A S A_S A S . □
Proof of Thm. 3 . Let x = log m x=\log m x = log m . For every sufficiently large integer m m m , choose
P = ⌈ x ⌉ , k = ⌊ P 3 log P ⌋ , h = ⌊ log P log log P ⌋ . P=\lceil\sqrt{x}\rceil,\qquad k=\left\lfloor\frac{P}{3\log P}\right\rfloor,\qquad h=\left\lfloor\frac{\log P}{\log\log P}\right\rfloor. P = ⌈ x ⌉ , k = ⌊ 3 log P P ⌋ , h = ⌊ log log P log P ⌋ .
Writing π ( u ) \pi(u) π ( u ) for the number of primes at most u u u , the prime number theorem [28 ] gives π ( 2 P ) − π ( P ) ∼ P / log P \pi(2P)-\pi(P)\sim P/\log P π ( 2 P ) − π ( P ) ∼ P / log P . The number of primes in the open interval ( P , 2 P ) (P,2P) ( P , 2 P ) differs from this count by at most one, so it eventually exceeds k k k . Also 2 ≤ h < k 2\le h<k 2 ≤ h < k eventually. Apply Lem. H.1 .
To bound the factor capacity from below, use ( d L ) ≥ ( d / L ) L = P L \binom{d}{L}\ge(d/L)^L=P^L ( L d ) ≥ ( d / L ) L = P L and N ≤ k h N\le k^h N ≤ k h . Since k ≤ P / log P k\le P/\log P k ≤ P / log P and ( log P ) h ≥ P (\log P)^h\ge P ( log P ) h ≥ P , we obtain
log n N ≥ P h + 1 log P k h ≥ P log P ( log P ) h ≥ P 2 log P ≥ x \frac{\log n}{N}\ge\frac{P^{h+1}\log P}{k^h}\ge P\log P(\log P)^h\ge P^2\log P\ge x N log n ≥ k h P h + 1 log P ≥ P log P ( log P ) h ≥ P 2 log P ≥ x
for sufficiently large P P P . Hence COR ( F ) ≥ m \operatorname{COR}(F)\ge m COR ( F ) ≥ m .
To bound the product capacity from above, note that h ≥ 2 h\ge2 h ≥ 2 gives log D = 2 P ( h + 2 ) log P ≤ 4 P h log P \log D=2P(h+2)\log P\le4Ph\log P log D = 2 P ( h + 2 ) log P ≤ 4 P h log P . Also k ≥ P / ( 4 log P ) k\ge P/(4\log P) k ≥ P / ( 4 log P ) eventually and x ≤ P 2 x\le P^2 x ≤ P 2 , so x h / k ≤ 4 P h log P xh/k\le4Ph\log P x h / k ≤ 4 P h log P . Therefore
log COR ( F × K m ) ≤ ( 1 − h / k ) log D + ( h / k ) x ≤ 8 P h log P = O ( x ( log x ) 2 log log x ) . (39) \begin{aligned}
\log\operatorname{COR}(F\times K_m)&\le(1-h/k)\log D+(h/k)x\\
&\le8Ph\log P=O\left(\sqrt{x}\frac{(\log x)^2}{\log\log x}\right). \tag*{(39)}
\end{aligned} log COR ( F × K m ) ≤ ( 1 − h / k ) log D + ( h / k ) x ≤ 8 P h log P = O ( x log log x ( log x ) 2 ) . (39)
All constants are absolute. Set G m = F ⊕ K 1 G_m=F\oplus K_1 G m = F ⊕ K 1 . By Lem. D.3 , it is connected, has capacity at least m + 1 m+1 m + 1 , and its product capacity is at most COR ( F × K m ) + 1 \operatorname{COR}(F\times K_m)+1 COR ( F × K m ) + 1 . Absorbing this additive 1 into the constant in (H.3) proves (8) –(9) .
For real t t t , take m = ⌈ t ⌉ m=\lceil t\rceil m = ⌈ t ⌉ . The pair ( G m , K m ) (G_m,K_m) ( G m , K m ) is admissible in (6) , and log ⌈ t ⌉ / log t → 1 \log\lceil t\rceil/\log t\to1 log ⌈ t ⌉ / log t → 1 . Thus the same explicit upper bound holds for f C ( t ) f_C(t) f C ( t ) after changing the constant. Since ( log log t ) 2 / log log log t = o ( ( log t ) δ ) (\log\log t)^2/\log\log\log t=o((\log t)^\delta) ( log log t ) 2 / log log log t = o (( log t ) δ ) for every δ > 0 \delta>0 δ > 0 , this proves (10) . Finally f C ( t ) ≥ 1 f_C(t)\ge1 f C ( t ) ≥ 1 and log f C ( t ) = o ( log t ) \log f_C(t)=o(\log t) log f C ( t ) = o ( log t ) give both limits in (11) .
Proof of Proposition 5.1 and its rate consequences
This appendix proves Lem. 5.1 and Thms. 5 and 6 from the channel interpretation in § 6 . We realize graphs as channels, identify the graph of the switched channel, and derive the stated zero-error rate bounds and the comparison with vanishing-error capacity.
Zero-error codes and graph realizations. We give the standard support argument for (12) and the realization fact used in Lem. 5.1. For a finite discrete memoryless channel W W W , put O W ( a ) = { y : W ( y ∣ a ) > 0 } O_W(a)=\{y:W(y\mid a)>0\} O W ( a ) = { y : W ( y ∣ a ) > 0 } . Distinct inputs a , a ′ a,a' a , a ′ are adjacent in D ( W ) D(W) D ( W ) if O W ( a ) ∩ O W ( a ′ ) = ∅ O_W(a)\cap O_W(a')=\varnothing O W ( a ) ∩ O W ( a ′ ) = ∅ . By memorylessness, the output support of an input word is the Cartesian product of its coordinate supports. Two such products are disjoint if and only if the supports are disjoint in at least one coordinate. Thus the largest zero-error code of block length n n n has size ω ( D ( W ) ∨ n ) \omega(D(W)^{\vee n}) ω ( D ( W ) ∨ n ) , proving R 0 ( W ) = log 2 COR ( D ( W ) ) R_0(W)=\log_2\operatorname{COR}(D(W)) R 0 ( W ) = log 2 COR ( D ( W )) by the supremum characterization of Shannon OR-capacity. This proves (12) .
Every finite graph G G G is a distinguishability graph. Assign each vertex a private output symbol, and each unordered pair of distinct nonadjacent vertices an additional output symbol shared by that pair. On input a a a , choose uniformly among its private symbol and the shared symbols assigned to pairs containing a a a . Two distinct inputs share a possible output exactly when they are nonadjacent in G G G .
Proof of Lem. 5.1. Since p p p and 1 − p 1-p 1 − p are positive, the output support of ( a , b ) (a,b) ( a , b ) is the disjoint union
( { 0 } × O W G ( a ) ) ∪ ( { 1 } × O W H ( b ) ) . \left(\{0\}\times O_{W_G}(a)\right)\cup\left(\{1\}\times O_{W_H}(b)\right). ( { 0 } × O W G ( a ) ) ∪ ( { 1 } × O W H ( b ) ) .
The labels 0 and 1 make outputs from different branches distinct. The supports for ( a , b ) (a,b) ( a , b ) and ( a ′ , b ′ ) (a',b') ( a ′ , b ′ ) are therefore disjoint if and only if
O W G ( a ) ∩ O W G ( a ′ ) = ∅ and O W H ( b ) ∩ O W H ( b ′ ) = ∅ . \mathcal{O}_{W_G}(a) \cap\mathcal{O}_{W_G}(a') = \varnothing\quad\text{and} \quad\mathcal{O}_{W_H}(b) \cap\mathcal{O}_{W_H}(b') = \varnothing. O W G ( a ) ∩ O W G ( a ′ ) = ∅ and O W H ( b ) ∩ O W H ( b ′ ) = ∅ .
These conditions are exactly a a ′ ∈ E ( G ) aa' \in E(G) a a ′ ∈ E ( G ) and b b ′ ∈ E ( H ) bb' \in E(H) b b ′ ∈ E ( H ) , which prove (13) . Applying (12) to the memoryless channel W s w W_{\mathrm{sw}} W sw gives the claimed block-code size and zero-error rate. Its output supports do not depend on the value of p ∈ ( 0 , 1 ) p \in(0,1) p ∈ ( 0 , 1 ) , so neither quantity depends on p p p .
If Conj. 1 holds, taking base-two logarithms and applying (12) proves (14) for every channel pair. Conversely, realize any finite graphs G , H G,H G , H by channels using the construction above. If (14) holds for every pair, the rate identity just proved gives
log 2 COR ( G × H ) = min { log 2 COR ( G ) , log 2 COR ( H ) } . \log_{2}\operatorname{COR}(G \times H) = \min\{\log_{2}\operatorname{COR}(G), \log_{2}\operatorname{COR}(H)\}. log 2 COR ( G × H ) = min { log 2 COR ( G ) , log 2 COR ( H )} .
Exponentiating proves Conj. 1. All capacities are at least one, so these logarithms are well-defined.
Comparison with vanishing-error capacity. For completeness, we prove the comparison stated in § 6 for the same channel W s w W_{\mathrm{sw}} W sw . If C S h C_{\mathrm{Sh}} C Sh denotes the ordinary vanishing-error capacity in bits per use, then
C S h ( W s w ) = p C S h ( W G ) + ( 1 − p ) C S h ( W H ) . (40) C_{\mathrm{Sh}}(W_{\mathrm{sw}}) = pC_{\mathrm{Sh}}(W_G) + (1-p)C_{\mathrm{Sh}}(W_H). \tag*{(40)} C Sh ( W sw ) = p C Sh ( W G ) + ( 1 − p ) C Sh ( W H ) . (40)
Proof. For a finite discrete memoryless channel, the channel-coding theorem gives C S h ( W ) = max P X I ( X ; Y ) C_{\mathrm{Sh}}(W) = \max_{P_X} I(X;Y) C Sh ( W ) = max P X I ( X ; Y ) [8 Sec. 3.1] . Here I ( X ; Y ) I(X;Y) I ( X ; Y ) is the mutual information in bits, defined by
I ( X ; Y ) = ∑ x , y P X Y ( x , y ) log 2 P X Y ( x , y ) P X ( x ) P Y ( y ) , I(X;Y) = \sum_{x,y} P_{XY}(x,y) \log_{2} \frac{P_{XY}(x,y)}{P_X(x)P_Y(y)}, I ( X ; Y ) = x , y ∑ P X Y ( x , y ) log 2 P X ( x ) P Y ( y ) P X Y ( x , y ) ,
with zero-probability terms omitted; conditional mutual information is the average of this quantity over the conditioning variable. Write A , B A,B A , B for the input random variables and S S S for the independent switch, with Pr ( S = 0 ) = p \Pr(S=0)=p Pr ( S = 0 ) = p . The mutual information between input and tagged output is
I ( A , B ; S , Y S ) = I ( A , B ; S ) + I ( A , B ; Y S ∣ S ) = p I ( A ; Y G ) + ( 1 − p ) I ( B ; Y H ) . \begin{aligned}
I(A,B;S,Y_S) &= I(A,B;S) + I(A,B;Y_S \mid S) \\
&= pI(A;Y_G) + (1-p)I(B;Y_H).
\end{aligned} I ( A , B ; S , Y S ) = I ( A , B ; S ) + I ( A , B ; Y S ∣ S ) = p I ( A ; Y G ) + ( 1 − p ) I ( B ; Y H ) .
Here S S S is independent of the inputs, and each component output depends only on its own input. This identity holds even when A A A and B B B are correlated. Each term is bounded by the corresponding component capacity. Choosing independent capacity-achieving input distributions for A A A and B B B attains both bounds simultaneously, proving (I.1).
The operational consequences now follow by applying Lem. 5.1 and taking base-two logarithms of the bounds on graph capacity, together with the explicit codes for the finite constructions. For every finite channel W W W and every n ≥ 1 n \ge1 n ≥ 1 , the definition of R 0 ( W ) R_0(W) R 0 ( W ) gives
M 0 ( W , n ) ≤ 2 n R 0 ( W ) = C O R ( D ( W ) ) n . (41) M_0(W,n) \le2^{nR_0(W)} = \mathrm{C}_{\mathrm{OR}}(\mathcal{D}(W))^n. \tag*{(41)} M 0 ( W , n ) ≤ 2 n R 0 ( W ) = C OR ( D ( W ) ) n . (41)
Proof of (5.4) and (5.5). Let W F W_F W F realize F 9 F_9 F 9 , and let W 9 W_9 W 9 be a noiseless nine-symbol channel. Lem. E.2 and (5) give
C O R ( F 9 ) = 128 > 9 , C O R ( F 9 × K 9 ) ≤ 72 < 9. \mathrm{C}_{\mathrm{OR}}(F_9) = \sqrt{128} > 9,\qquad\mathrm{C}_{\mathrm{OR}}(F_9 \times K_9) \le\sqrt{72} < 9. C OR ( F 9 ) = 128 > 9 , C OR ( F 9 × K 9 ) ≤ 72 < 9.
Taking base-two logarithms and applying Lem. 5.1 proves (5.4).
The explicit 128-word code in § 3 gives M 0 ( W F , 2 ) ≥ 128 M_0(W_F,2) \ge128 M 0 ( W F , 2 ) ≥ 128 , and (I.2) gives the matching upper bound. The noiseless channel satisfies M 0 ( W 9 , 2 ) = 9 2 = 81 M_0(W_9,2) = 9^2 = 81 M 0 ( W 9 , 2 ) = 9 2 = 81 . Finally, Lem. 5.1 and (I.2) give
M 0 ( W s w , 2 ) ≤ C O R ( F 9 × K 9 ) 2 ≤ 72 , M_0(W_{\mathrm{sw}},2) \le\mathrm{C}_{\mathrm{OR}}(F_9 \times K_9)^2 \le72, M 0 ( W sw , 2 ) ≤ C OR ( F 9 × K 9 ) 2 ≤ 72 ,
proving (5.5).
Proof of Thm. 5. For part (1), realize the graph G G G from Thm. 1 by a channel W G W_G W G , and take W m W_m W m to be noiseless on m m m symbols. Taking base-two logarithms of the theorem’s bounds and applying Lem. 5.1 gives the claimed inequalities.
For part (2), realize the graphs constructed for Thm. 2(1) by channels W G , W H W_G,W_H W G , W H . The rate bounds again follow by taking logarithms and applying Lem. 5.1. The explicit codes in Subsec. F.2 give 27 messages in two uses of each individual channel. On the other hand, (I.2) gives
M 0 ( W s w , 2 ) ≤ C O R ( G × H ) 2 < 27. M_0(W_{\mathrm{sw}},2) \le\mathrm{C}_{\mathrm{OR}}(G \times H)^2 < 27. M 0 ( W sw , 2 ) ≤ C OR ( G × H ) 2 < 27.
Since the number of messages is an integer, it is at most 26.
For part (3), put t = 2 r ≥ 6.0101 t = 2^r \ge6.0101 t = 2 r ≥ 6.0101 and realize the graphs supplied by Thm. 2(2). Taking logarithms of C O R ( G × H ) < t < min { C O R ( G ) , C O R ( H ) } \mathrm{C}_{\mathrm{OR}}(G \times H) < t < \min\{\mathrm{C}_{\mathrm{OR}}(G),\mathrm{C}_{\mathrm{OR}}(H)\} C OR ( G × H ) < t < min { C OR ( G ) , C OR ( H )} gives the claimed rate separation. In every part, the graph realizations are independent of p p p , and Lem. 5.1 applies to the same channels for every p ∈ ( 0 , 1 ) p \in(0,1) p ∈ ( 0 , 1 ) .
Proof of Thm. 6 . For each sufficiently large m m m , realize the graph G m G_m G m from Thm. 3 by a channel W G m W_{G_m} W G m , and let W m W_m W m be a noiseless m m m -symbol channel. By Lem. 5.1, taking base-two logarithms in (9) and writing R m = log 2 m R_m = \log_2 m R m = log 2 m gives, for every p ∈ ( 0 , 1 ) p \in(0,1) p ∈ ( 0 , 1 ) ,
R 0 ( W s w , m ) = O ( R m ( log R m ) 2 log log R m ) . R_0(W_{\mathrm{sw},m}) = O\left(\sqrt{R_m}\,\frac{(\log R_m)^2}{\log\log R_m}\right). R 0 ( W sw , m ) = O ( R m log log R m ( log R m ) 2 ) .
The factor multiplying R m \sqrt{R_m} R m is R m o ( 1 ) R_m^{o(1)} R m o ( 1 ) ; hence (5.6) follows. The smaller component rate is R m R_m R m because C O R ( G m ) ≥ m + 1 \mathrm{C}_{\mathrm{OR}}(G_m) \ge m+1 C OR ( G m ) ≥ m + 1 and C O R ( K m ) = m \mathrm{C}_{\mathrm{OR}}(K_m) = m C OR ( K m ) = m .