shannon_or_capacity_categorical_prod_of_min_eq_two
For any finite nonempty simple graphs G and H, if the minimum of their Shannon OR-capacities is 2, then the Shannon OR-capacity of their categorical product G × H is 2.
Statement
theorem shannon_or_capacity_categorical_prod_of_min_eq_two {V W : Type*} [Fintype V] [Nonempty V] [Fintype W] [Nonempty W] (G : SimpleGraph V) (H : SimpleGraph W) (h : min (shannon_or_capacity G) (shannon_or_capacity H) = 2) : shannon_or_capacity (simple_graph_categorical_prod G H) = 2
- Formalizes
- arXiv:2610.41977 Sec. 6
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- shannon_or_capacity_categorical_prod_le_minFor any finite nonempty simple graphs G and H, the Shannon OR-capacity of their categorical product G × H is at most the minimum of the…
- shannon_or_capacityThe Shannon OR-capacity C_OR(G) of a simple graph G is defined as the supremum over n ≥ 1 of (omega(G^{∨n}))^{1/n}, where omega denotes…
- simple_graph_categorical_prodThe categorical product (tensor product) G × H of two simple graphs G and H has vertex set V(G) × V(H), with an edge between (u₁, v₁) and…
- simple_graph_or_powerThe n-th OR-power (co-normal power) G^{∨n} of a simple graph G has vertex set Fin n → V, with an edge between two functions if they are…
Read back from the Lean
For any two finite, nonempty types $V$ and $W$, and any simple graphs $G$ on $V$ and $H$ on $W$, if the minimum of the Shannon OR-capacity of $G$ and the Shannon OR-capacity of $H$ is equal to $2$, then the Shannon OR-capacity of the categorical (tensor) product graph $G \times H$ is also equal to $2$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof establishes that C_OR(G × H) = 2 by sandwiching it between 2 and min(C_OR(G), C_OR(H)) = 2. The upper bound C_OR(G × H) ≤ min(C_OR(G), C_OR(H)) = 2 follows from the general categorical product inequality. For the lower bound, any graph with no edges has capacity at most 1, so the condition min(C_OR(G), C_OR(H)) = 2 forces both G and H to have at least one edge; these edges pair up to form an edge in G × H, which provides a 2-clique in its first OR-power and guarantees C_OR(G × H) ≥ 2.
A finite graph with no edges has clique number at most 1.
Let s be a maximum clique of G, so that |s| = ω(G). Suppose for contradiction that |s| > 1. Then by Finset.one_lt_card.mp, s contains two distinct vertices a ≠ b. Since s is a clique, a and b must be adjacent in G, contradicting the hypothesis that G has no edges.
uses
Finset.one_lt_card.mpobtain ⟨s, hs, hcard⟩ := G.exists_isNClique_cliqueNum rw [← hcard] by_contra hlt push Not at hlt obtain ⟨a, ha, b, hb, hab⟩ := Finset.one_lt_card.mp hlt exact h a b (hs ha hb hab)
A finite nonempty graph with no edges has Shannon OR-capacity at most 1.
Unfolding the definition of Shannon OR-capacity, it suffices by ciSup_le to show that each term indexed by n is at most 1. If 1 ≤ n, two tuples in the n-th OR-power G^{\lor n} are adjacent if and only if they are adjacent at some coordinate; since G has no edges, G^{\lor n} also has no edges. By the previous lemma, the clique number of G^{\lor n} is at most 1, and raising it to the power 1/n yields at most 1 by Real.rpow_le_one. The case n = 0 is degenerate and handled trivially by simp.
uses
ciSup_le,ciSup_pos,shannon_or_capacity_categorical_prod_of_min_eq_two_cliqueNum_le_one,Real.rpow_le_oneunfold shannon_or_capacity apply ciSup_le intro n by_cases hn : 1 ≤ n · rw [ciSup_pos hn] have hno : ∀ x y : Fin n → V, ¬ (simple_graph_or_power G n).Adj x y := by intro x y hxy obtain ⟨i, hi⟩ := hxy exact h (x i) (y i) hi have hcl : (simple_graph_or_power G n).cliqueNum ≤ 1 := shannon_or_capacity_categorical_prod_of_min_eq_two_cliqueNum_le_one _ hno have hclr : ((simple_graph_or_power G n).cliqueNum : ℝ) ≤ 1 := by exact_mod_cast hcl exact Real.rpow_le_one (by positivity) hclr (by positivity) · simp [hn]
If G contains an edge, the first OR-power of G has clique number at least 2.
Given an edge u ~ v in G, consider the two constant functions in Fin 1 → V taking value u and v respectively. Since u ~ v, u ≠ v by G.ne_of_adj, so these two functions are distinct, and their pair set has size 2 by Finset.card_pair. Because their values at coordinate 0 are adjacent, they form a 2-clique in the first OR-power of G, establishing that ω(G^{\lor 1}) ≥ 2.
uses
Finset.card_pair,congrFunclassical have hcl : 2 ≤ (simple_graph_or_power G 1).cliqueNum := by have hc : (simple_graph_or_power G 1).IsClique ({(fun _ : Fin 1 => u), (fun _ : Fin 1 => v)} : Finset (Fin 1 → V)) := by intro a ha b hb hab simp at ha hb rcases ha with rfl | rfl <;> rcases hb with rfl | rfl · exact absurd rfl hab · exact ⟨0, h⟩ · exact ⟨0, (G.adj_comm v u).mpr h⟩ · exact absurd rfl hab have hcard : ({(fun _ : Fin 1 => u), (fun _ : Fin 1 => v)} : Finset (Fin 1 → V)).card = 2 := by rw [Finset.card_pair] intro heq exact G.ne_of_adj h (congrFun heq 0) have := hc.card_le_cliqueNum rwa [hcard] at this
If G contains an edge, its Shannon OR-capacity is at least 2.
In the definition of Shannon OR-capacity, the term for n = 1 evaluates to ω(G^{\lor 1})^{1/1} = ω(G^{\lor 1}) ≥ 2, using Real.rpow_one. Because the sequence of powers is bounded above (by shannon_or_capacity_categorical_prod_le_min_bddAbove_shannon_range), this term is bounded by the supremum via le_ciSup, so 2 ≤ C_OR(G) by transitivity.
uses
ciSup_pos,le_refl,Real.rpow_one,shannon_or_capacity_categorical_prod_le_min_bddAbove_shannon_range,le_trans,le_ciSupunfold shannon_or_capacity have hclr : (2:ℝ) ≤ ((simple_graph_or_power G 1).cliqueNum : ℝ) := by exact_mod_cast hcl have hterm : (2:ℝ) ≤ ⨆ (_ : 1 ≤ (1:ℕ)), ((simple_graph_or_power G 1).cliqueNum : ℝ) ^ ((1:ℝ)/↑(1:ℕ)) := by rw [ciSup_pos (le_refl 1)] rw [show (1:ℝ)/↑(1:ℕ) = 1 by norm_num, Real.rpow_one] exact hclr have hbdd := shannon_or_capacity_categorical_prod_le_min_bddAbove_shannon_range G exact le_trans hterm (le_ciSup hbdd 1)
Both G and H have Shannon OR-capacity at least 2.
Since min(C_OR(G), C_OR(H)) = 2, the standard inequalities min_le_left and min_le_right immediately imply 2 ≤ C_OR(G) and 2 ≤ C_OR(H).
uses
min_le_left,min_le_righthave hG : 2 ≤ shannon_or_capacity G := by rw [← h]; exact min_le_left _ _ have hH : 2 ≤ shannon_or_capacity H := by rw [← h]; exact min_le_right _ _
Both G and H contain at least one edge.
Suppose for contradiction that G had no edges. Then by shannon_or_capacity_categorical_prod_of_min_eq_two_le_one_of_no_adj, C_OR(G) ≤ 1, which contradicts 2 ≤ C_OR(G). Thus G has an edge u ~ v. Symmetrically, H has an edge x ~ y.
uses
shannon_or_capacity_categorical_prod_of_min_eq_two_le_one_of_no_adjhave hedgeG : ∃ u v : V, G.Adj u v := by by_contra hne push Not at hne have hle := shannon_or_capacity_categorical_prod_of_min_eq_two_le_one_of_no_adj G hne linarith obtain ⟨u, v, huv⟩ := hedgeG have hedgeH : ∃ x y : W, H.Adj x y := by by_contra hne push Not at hne have hle := shannon_or_capacity_categorical_prod_of_min_eq_two_le_one_of_no_adj H hne linarith obtain ⟨x, y, hxy⟩ := hedgeH
The Shannon OR-capacity of the categorical product G × H is at least 2.
The pairs (u, x) and (v, y) form an edge in G × H because u ~ v in G and x ~ y in H. Since G × H contains an edge, shannon_or_capacity_categorical_prod_of_min_eq_two_two_le_of_adj implies 2 ≤ C_OR(G × H).
uses
shannon_or_capacity_categorical_prod_of_min_eq_two_two_le_of_adjhave hadj : (simple_graph_categorical_prod G H).Adj (u, x) (v, y) := ⟨huv, hxy⟩ have hlower : 2 ≤ shannon_or_capacity (simple_graph_categorical_prod G H) := shannon_or_capacity_categorical_prod_of_min_eq_two_two_le_of_adj _ hadj
The Shannon OR-capacity of the categorical product G × H is at most 2.
By the general upper bound shannon_or_capacity_categorical_prod_le_min, C_OR(G × H) ≤ min(C_OR(G), C_OR(H)). Substituting min(C_OR(G), C_OR(H)) = 2 yields C_OR(G × H) ≤ 2.
uses
shannon_or_capacity_categorical_prod_le_minhave hupper : shannon_or_capacity (simple_graph_categorical_prod G H) ≤ 2 := by have hle := shannon_or_capacity_categorical_prod_le_min G H rw [h] at hle exact hle
The Shannon OR-capacity of the categorical product G × H equals 2. automation
Linear arithmetic over ℝ combines the inequalities 2 ≤ C_OR(G × H) and C_OR(G × H) ≤ 2 to conclude C_OR(G × H) = 2.
linarith
Finset.one_lt_card.mp- A finite set has cardinality strictly greater than 1 if and only if it contains two distinct elements.
ciSup_le- The supremum of an indexed family in a conditionally complete lattice is at most c if every term in the family is at most c.
ciSup_pos- The supremum over a true proposition p evaluates to the value of the function at the proof of p.
shannon_or_capacity_categorical_prod_of_min_eq_two_cliqueNum_le_one- A finite simple graph with no edges has clique number at most 1.
Real.rpow_le_one- For non-negative real numbers x and z, if x ≤ 1 then x^z ≤ 1.
Finset.card_pair- A pair set {a, b} has cardinality 2 if and only if a ≠ b.
congrFun- If two functions are equal, then they take the same value at any given argument.
le_refl- The preorder relation ≤ is reflexive: a ≤ a for any a.
Real.rpow_one- Any real number raised to the power 1 equals itself.
shannon_or_capacity_categorical_prod_le_min_bddAbove_shannon_range- The sequence of n-th root clique numbers of the OR-powers defining the Shannon OR-capacity is bounded above.
le_trans- The preorder relation ≤ is transitive: if a ≤ b and b ≤ c, then a ≤ c.
le_ciSup- In a conditionally complete lattice, any element of a family is at most the supremum of the family, provided the family is bounded above.
min_le_left- The minimum of two elements a and b is less than or equal to a.
min_le_right- The minimum of two elements a and b is less than or equal to b.
shannon_or_capacity_categorical_prod_of_min_eq_two_le_one_of_no_adj- If a finite nonempty simple graph has no edges, its Shannon OR-capacity is at most 1.
shannon_or_capacity_categorical_prod_of_min_eq_two_two_le_of_adj- If a finite nonempty simple graph contains at least one edge, its Shannon OR-capacity is at least 2.
shannon_or_capacity_categorical_prod_le_min- The Shannon OR-capacity of the categorical product of two graphs is at most the minimum of their individual Shannon OR-capacities.
- The Shannon OR-capacity is formalized as an iterated supremum: an outer supremum over n : ℕ and an inner supremum over the proof that 1 ≤ n.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
private lemma shannon_or_capacity_categorical_prod_of_min_eq_two_cliqueNum_le_one {V : Type*} [Fintype V] (G : SimpleGraph V) (h : ∀ u v : V, ¬ G.Adj u v) : G.cliqueNum ≤ 1 := by obtain ⟨s, hs, hcard⟩ := G.exists_isNClique_cliqueNum rw [← hcard] by_contra hlt push Not at hlt obtain ⟨a, ha, b, hb, hab⟩ := Finset.one_lt_card.mp hlt exact h a b (hs ha hb hab)private lemma shannon_or_capacity_categorical_prod_of_min_eq_two_le_one_of_no_adj {V : Type*} [Fintype V] [Nonempty V] (G : SimpleGraph V) (h : ∀ u v : V, ¬ G.Adj u v) : shannon_or_capacity G ≤ 1 := by unfold shannon_or_capacity apply ciSup_le intro n by_cases hn : 1 ≤ n · rw [ciSup_pos hn] have hno : ∀ x y : Fin n → V, ¬ (simple_graph_or_power G n).Adj x y := by intro x y hxy obtain ⟨i, hi⟩ := hxy exact h (x i) (y i) hi have hcl : (simple_graph_or_power G n).cliqueNum ≤ 1 := shannon_or_capacity_categorical_prod_of_min_eq_two_cliqueNum_le_one _ hno have hclr : ((simple_graph_or_power G n).cliqueNum : ℝ) ≤ 1 := by exact_mod_cast hcl exact Real.rpow_le_one (by positivity) hclr (by positivity) · simp [hn]private lemma shannon_or_capacity_categorical_prod_of_min_eq_two_two_le_of_adj {V : Type*} [Fintype V] [Nonempty V] (G : SimpleGraph V) {u v : V} (h : G.Adj u v) : 2 ≤ shannon_or_capacity G := by classical have hcl : 2 ≤ (simple_graph_or_power G 1).cliqueNum := by have hc : (simple_graph_or_power G 1).IsClique ({(fun _ : Fin 1 => u), (fun _ : Fin 1 => v)} : Finset (Fin 1 → V)) := by intro a ha b hb hab simp at ha hb rcases ha with rfl | rfl <;> rcases hb with rfl | rfl · exact absurd rfl hab · exact ⟨0, h⟩ · exact ⟨0, (G.adj_comm v u).mpr h⟩ · exact absurd rfl hab have hcard : ({(fun _ : Fin 1 => u), (fun _ : Fin 1 => v)} : Finset (Fin 1 → V)).card = 2 := by rw [Finset.card_pair] intro heq exact G.ne_of_adj h (congrFun heq 0) have := hc.card_le_cliqueNum rwa [hcard] at this unfold shannon_or_capacity have hclr : (2:ℝ) ≤ ((simple_graph_or_power G 1).cliqueNum : ℝ) := by exact_mod_cast hcl have hterm : (2:ℝ) ≤ ⨆ (_ : 1 ≤ (1:ℕ)), ((simple_graph_or_power G 1).cliqueNum : ℝ) ^ ((1:ℝ)/↑(1:ℕ)) := by rw [ciSup_pos (le_refl 1)] rw [show (1:ℝ)/↑(1:ℕ) = 1 by norm_num, Real.rpow_one] exact hclr have hbdd := shannon_or_capacity_categorical_prod_le_min_bddAbove_shannon_range G exact le_trans hterm (le_ciSup hbdd 1)/-- Hedetniemi's identity for Shannon OR-capacity holds when the smaller factor capacity is two. -/theorem shannon_or_capacity_categorical_prod_of_min_eq_two {V W : Type*} [Fintype V] [Nonempty V] [Fintype W] [Nonempty W] (G : SimpleGraph V) (H : SimpleGraph W) (h : min (shannon_or_capacity G) (shannon_or_capacity H) = 2) : shannon_or_capacity (simple_graph_categorical_prod G H) = 2 := by have hG : 2 ≤ shannon_or_capacity G := by rw [← h]; exact min_le_left _ _ have hH : 2 ≤ shannon_or_capacity H := by rw [← h]; exact min_le_right _ _ have hedgeG : ∃ u v : V, G.Adj u v := by by_contra hne push Not at hne have hle := shannon_or_capacity_categorical_prod_of_min_eq_two_le_one_of_no_adj G hne linarith obtain ⟨u, v, huv⟩ := hedgeG have hedgeH : ∃ x y : W, H.Adj x y := by by_contra hne push Not at hne have hle := shannon_or_capacity_categorical_prod_of_min_eq_two_le_one_of_no_adj H hne linarith obtain ⟨x, y, hxy⟩ := hedgeH have hadj : (simple_graph_categorical_prod G H).Adj (u, x) (v, y) := ⟨huv, hxy⟩ have hlower : 2 ≤ shannon_or_capacity (simple_graph_categorical_prod G H) := shannon_or_capacity_categorical_prod_of_min_eq_two_two_le_of_adj _ hadj have hupper : shannon_or_capacity (simple_graph_categorical_prod G H) ≤ 2 := by have hle := shannon_or_capacity_categorical_prod_le_min G H rw [h] at hle exact hle linarith