shannon_or_capacity_categorical_prod_le_min
For 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-capacities of G and H.
Statement
theorem shannon_or_capacity_categorical_prod_le_min {V W : Type*} [Fintype V] [Nonempty V] [Fintype W] [Nonempty W] (G : SimpleGraph V) (H : SimpleGraph W) : shannon_or_capacity (simple_graph_categorical_prod G H) ≤ min (shannon_or_capacity G) (shannon_or_capacity H)
- Formalizes
- arXiv:2610.41977 Sec. 1
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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…
- 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…
- 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…
- Used by 2
- shannon_or_capacity_categorical_prod_of_min_eq_oneFor any finite nonempty simple graphs G and H, if the minimum of their Shannon OR-capacities is 1, then the Shannon OR-capacity of their…
- shannon_or_capacity_categorical_prod_of_min_eq_twoFor 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…
Read back from the Lean
For any types $V$ and $W$ equipped with Fintype and Nonempty instances, and for any simple graphs $G$ on $V$ and $H$ on $W$, the Shannon OR capacity of the categorical product of $G$ and $H$ is less than or equal to the minimum of the Shannon OR capacity of $G$ and the Shannon OR capacity of $H$.
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 Shannon OR-capacity of a graph product is bounded by projecting maximum cliques of the OR power to each factor. Because an edge in the categorical product requires adjacency in both factors, the projection of any clique is injective and its image is a clique in the factor. Taking the n-th roots and suprema over all n bounds the capacity by both factor capacities, hence by their minimum.
The clique number of a finite graph G is bounded by the cardinality of its vertex set.
Let s be a maximum clique of G, so |s| = cliqueNum(G). Since s is a subset of the finite vertex type α, |s| ≤ |α|.
uses
SimpleGraph.exists_isNClique_cliqueNumlemma shannon_or_capacity_categorical_prod_le_min_cliqueNum_le_card {α : Type*} [Fintype α] (G : SimpleGraph α) : G.cliqueNum ≤ Fintype.card α := by obtain ⟨s, hs⟩ := G.exists_isNClique_cliqueNum rw [← hs.card_eq] exact s.card_le_univ
The Shannon OR-capacity of the categorical product is bounded by the minimum of the capacities.
The remaining lemmas show that the clique number of the n-th OR power of G × H is bounded by both G and H, hence their Shannon capacities satisfy the same bound, yielding the minimum.
lemma shannon_or_capacity_categorical_prod_le_min_power_cliqueNum_rpow_le {V : Type*} [Fintype V] (G : SimpleGraph V) (n : ℕ) (hn : 1 ≤ n) : ((simple_graph_or_power G n).cliqueNum : ℝ) ^ ((1 : ℝ) / n) ≤ (Fintype.card V : ℝ) := by have hcard : (simple_graph_or_power G n).cliqueNum ≤ (Fintype.card V) ^ n := by have hle := shannon_or_capacity_categorical_prod_le_min_cliqueNum_le_card (simple_graph_or_power G n) simp only [Fintype.card_fun, Fintype.card_fin] at hle exact hle have hcard_r : ((simple_graph_or_power G n).cliqueNum : ℝ) ≤ ((Fintype.card V : ℝ) ^ n) := by exact_mod_cast hcard have hn_pos : 0 < (n : ℝ) := Nat.cast_pos.mpr hn have h_exp_pos : 0 ≤ (1 : ℝ) / n := one_div_nonneg.mpr (le_of_lt hn_pos) have h_rpow := Real.rpow_le_rpow (by positivity) hcard_r h_exp_pos have h_pow_rpow : (((Fintype.card V : ℝ) ^ n) ^ ((1 : ℝ) / n)) = (Fintype.card V : ℝ) := by have h_card_nonneg : 0 ≤ (Fintype.card V : ℝ) := by positivity rw [← Real.rpow_natCast, ← Real.rpow_mul h_card_nonneg] have : (n : ℝ) * ((1 : ℝ) / n) = 1 := mul_one_div_cancel (ne_of_gt hn_pos) rw [this, Real.rpow_one] rwa [h_pow_rpow] at h_rpow lemma shannon_or_capacity_categorical_prod_le_min_bddAbove_shannon_range {V : Type*} [Fintype V] [Nonempty V] (G : SimpleGraph V) : BddAbove (Set.range (fun n => ⨆ (_ : 1 ≤ n), (((simple_graph_or_power G n).cliqueNum : ℝ) ^ ((1 : ℝ) / n)))) := by use (Fintype.card V : ℝ) rintro x ⟨n, rfl⟩ dsimp only by_cases hn : 1 ≤ n · rw [ciSup_pos hn] exact shannon_or_capacity_categorical_prod_le_min_power_cliqueNum_rpow_le G n hn · rw [ciSup_neg hn, Real.sSup_empty] positivity theorem shannon_or_capacity_categorical_prod_le_min_cliqueNum_le_fst {V W : Type*} [Fintype V] [Fintype W] (G : SimpleGraph V) (H : SimpleGraph W) (n : ℕ) : (simple_graph_or_power (simple_graph_categorical_prod G H) n).cliqueNum ≤ (simple_graph_or_power G n).cliqueNum := by classical obtain ⟨s, hs⟩ := (simple_graph_or_power (simple_graph_categorical_prod G H) n).exists_isNClique_cliqueNum rw [SimpleGraph.isNClique_iff] at hs rcases hs with ⟨hs_clique, hs_card⟩ let f : (Fin n → V × W) → (Fin n → V) := fun x => fun i => (x i).1 have hinj : ∀ x ∈ s, ∀ y ∈ s, f x = f y → x = y := by intro x hx y hy hxy by_contra hne have hadj := hs_clique hx hy hne simp only [simple_graph_or_power, simple_graph_categorical_prod] at hadj rcases hadj with ⟨i, hiG, _⟩ have hfi : f x i = f y i := congr_fun hxy i dsimp [f] at hfi exact G.ne_of_adj hiG hfi have hcard : s.card = (s.image f).card := by rw [Finset.card_image_of_injOn] intro x hx y hy hxy exact hinj x hx y hy hxy have hclique : (simple_graph_or_power G n).IsClique (s.image f : Set (Fin n → V)) := by intro u hu v hv huv rw [Finset.mem_coe, Finset.mem_image] at hu hv rcases hu with ⟨x, hx, rfl⟩ rcases hv with ⟨y, hy, rfl⟩ have hne : x ≠ y := by rintro rfl exact huv rfl have hadj := hs_clique hx hy hne simp only [simple_graph_or_power, simple_graph_categorical_prod] at hadj rcases hadj with ⟨i, hiG, _⟩ exact ⟨i, hiG⟩ have hle := SimpleGraph.IsClique.card_le_cliqueNum (tc := hclique) rw [← hs_card, hcard] exact hle theorem shannon_or_capacity_categorical_prod_le_min_cliqueNum_le_snd {V W : Type*} [Fintype V] [Fintype W] (G : SimpleGraph V) (H : SimpleGraph W) (n : ℕ) : (simple_graph_or_power (simple_graph_categorical_prod G H) n).cliqueNum ≤ (simple_graph_or_power H n).cliqueNum := by classical obtain ⟨s, hs⟩ := (simple_graph_or_power (simple_graph_categorical_prod G H) n).exists_isNClique_cliqueNum rw [SimpleGraph.isNClique_iff] at hs rcases hs with ⟨hs_clique, hs_card⟩ let f : (Fin n → V × W) → (Fin n → W) := fun x => fun i => (x i).2 have hinj : ∀ x ∈ s, ∀ y ∈ s, f x = f y → x = y := by intro x hx y hy hxy by_contra hne have hadj := hs_clique hx hy hne simp only [simple_graph_or_power, simple_graph_categorical_prod] at hadj rcases hadj with ⟨i, _, hiH⟩ have hfi : f x i = f y i := congr_fun hxy i dsimp [f] at hfi exact H.ne_of_adj hiH hfi have hcard : s.card = (s.image f).card := by rw [Finset.card_image_of_injOn] intro x hx y hy hxy exact hinj x hx y hy hxy have hclique : (simple_graph_or_power H n).IsClique (s.image f : Set (Fin n → W)) := by intro u hu v hv huv rw [Finset.mem_coe, Finset.mem_image] at hu hv rcases hu with ⟨x, hx, rfl⟩ rcases hv with ⟨y, hy, rfl⟩ have hne : x ≠ y := by rintro rfl exact huv rfl have hadj := hs_clique hx hy hne simp only [simple_graph_or_power, simple_graph_categorical_prod] at hadj rcases hadj with ⟨i, _, hiH⟩ exact ⟨i, hiH⟩ have hle := SimpleGraph.IsClique.card_le_cliqueNum (tc := hclique) rw [← hs_card, hcard] exact hle theorem shannon_or_capacity_categorical_prod_le_min_le_fst {V W : Type*} [Fintype V] [Nonempty V] [Fintype W] [Nonempty W] (G : SimpleGraph V) (H : SimpleGraph W) : shannon_or_capacity (simple_graph_categorical_prod G H) ≤ shannon_or_capacity G := by dsimp only [shannon_or_capacity] apply ciSup_le intro n by_cases hn : 1 ≤ n · rw [ciSup_pos hn] have hclique := shannon_or_capacity_categorical_prod_le_min_cliqueNum_le_fst G H n have hn_pos : 0 < (n : ℝ) := Nat.cast_pos.mpr hn have h_exp_pos : 0 ≤ (1 : ℝ) / n := one_div_nonneg.mpr (le_of_lt hn_pos) have h_rpow : ((simple_graph_or_power (simple_graph_categorical_prod G H) n).cliqueNum : ℝ) ^ ((1 : ℝ) / n) ≤ ((simple_graph_or_power G n).cliqueNum : ℝ) ^ ((1 : ℝ) / n) := by exact Real.rpow_le_rpow (by positivity) (by exact_mod_cast hclique) h_exp_pos have h_le_sup := le_ciSup (shannon_or_capacity_categorical_prod_le_min_bddAbove_shannon_range G) n rw [ciSup_pos hn] at h_le_sup exact h_rpow.trans h_le_sup · rw [ciSup_neg hn, Real.sSup_empty] have h1 : 1 ≤ 1 := le_refl 1 have h_pos : 0 ≤ ((simple_graph_or_power G 1).cliqueNum : ℝ) ^ ((1 : ℝ) / ↑(1 : ℕ)) := by positivity have h_le_sup := le_ciSup (shannon_or_capacity_categorical_prod_le_min_bddAbove_shannon_range G) 1 rw [ciSup_pos h1] at h_le_sup exact h_pos.trans h_le_sup theorem shannon_or_capacity_categorical_prod_le_min_le_snd {V W : Type*} [Fintype V] [Nonempty V] [Fintype W] [Nonempty W] (G : SimpleGraph V) (H : SimpleGraph W) : shannon_or_capacity (simple_graph_categorical_prod G H) ≤ shannon_or_capacity H := by dsimp only [shannon_or_capacity] apply ciSup_le intro n by_cases hn : 1 ≤ n · rw [ciSup_pos hn] have hclique := shannon_or_capacity_categorical_prod_le_min_cliqueNum_le_snd G H n have hn_pos : 0 < (n : ℝ) := Nat.cast_pos.mpr hn have h_exp_pos : 0 ≤ (1 : ℝ) / n := one_div_nonneg.mpr (le_of_lt hn_pos) have h_rpow : ((simple_graph_or_power (simple_graph_categorical_prod G H) n).cliqueNum : ℝ) ^ ((1 : ℝ) / n) ≤ ((simple_graph_or_power H n).cliqueNum : ℝ) ^ ((1 : ℝ) / n) := by exact Real.rpow_le_rpow (by positivity) (by exact_mod_cast hclique) h_exp_pos have h_le_sup := le_ciSup (shannon_or_capacity_categorical_prod_le_min_bddAbove_shannon_range H) n rw [ciSup_pos hn] at h_le_sup exact h_rpow.trans h_le_sup · rw [ciSup_neg hn, Real.sSup_empty] have h1 : 1 ≤ 1 := le_refl 1 have h_pos : 0 ≤ ((simple_graph_or_power H 1).cliqueNum : ℝ) ^ ((1 : ℝ) / ↑(1 : ℕ)) := by positivity have h_le_sup := le_ciSup (shannon_or_capacity_categorical_prod_le_min_bddAbove_shannon_range H) 1 rw [ciSup_pos h1] at h_le_sup exact h_pos.trans h_le_sup /-- The Shannon OR-capacity of a categorical product is at most the minimum of the factor capacities. -/ theorem shannon_or_capacity_categorical_prod_le_min {V W : Type*} [Fintype V] [Nonempty V] [Fintype W] [Nonempty W] (G : SimpleGraph V) (H : SimpleGraph W) : shannon_or_capacity (simple_graph_categorical_prod G H) ≤ min (shannon_or_capacity G) (shannon_or_capacity H) := le_min (shannon_or_capacity_categorical_prod_le_min_le_fst G H) (shannon_or_capacity_categorical_prod_le_min_le_snd G H)
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.
lemma shannon_or_capacity_categorical_prod_le_min_cliqueNum_le_card {α : Type*} [Fintype α] (G : SimpleGraph α) : G.cliqueNum ≤ Fintype.card α := by obtain ⟨s, hs⟩ := G.exists_isNClique_cliqueNum rw [← hs.card_eq] exact s.card_le_univlemma shannon_or_capacity_categorical_prod_le_min_power_cliqueNum_rpow_le {V : Type*} [Fintype V] (G : SimpleGraph V) (n : ℕ) (hn : 1 ≤ n) : ((simple_graph_or_power G n).cliqueNum : ℝ) ^ ((1 : ℝ) / n) ≤ (Fintype.card V : ℝ) := by have hcard : (simple_graph_or_power G n).cliqueNum ≤ (Fintype.card V) ^ n := by have hle := shannon_or_capacity_categorical_prod_le_min_cliqueNum_le_card (simple_graph_or_power G n) simp only [Fintype.card_fun, Fintype.card_fin] at hle exact hle have hcard_r : ((simple_graph_or_power G n).cliqueNum : ℝ) ≤ ((Fintype.card V : ℝ) ^ n) := by exact_mod_cast hcard have hn_pos : 0 < (n : ℝ) := Nat.cast_pos.mpr hn have h_exp_pos : 0 ≤ (1 : ℝ) / n := one_div_nonneg.mpr (le_of_lt hn_pos) have h_rpow := Real.rpow_le_rpow (by positivity) hcard_r h_exp_pos have h_pow_rpow : (((Fintype.card V : ℝ) ^ n) ^ ((1 : ℝ) / n)) = (Fintype.card V : ℝ) := by have h_card_nonneg : 0 ≤ (Fintype.card V : ℝ) := by positivity rw [← Real.rpow_natCast, ← Real.rpow_mul h_card_nonneg] have : (n : ℝ) * ((1 : ℝ) / n) = 1 := mul_one_div_cancel (ne_of_gt hn_pos) rw [this, Real.rpow_one] rwa [h_pow_rpow] at h_rpowlemma shannon_or_capacity_categorical_prod_le_min_bddAbove_shannon_range {V : Type*} [Fintype V] [Nonempty V] (G : SimpleGraph V) : BddAbove (Set.range (fun n => ⨆ (_ : 1 ≤ n), (((simple_graph_or_power G n).cliqueNum : ℝ) ^ ((1 : ℝ) / n)))) := by use (Fintype.card V : ℝ) rintro x ⟨n, rfl⟩ dsimp only by_cases hn : 1 ≤ n · rw [ciSup_pos hn] exact shannon_or_capacity_categorical_prod_le_min_power_cliqueNum_rpow_le G n hn · rw [ciSup_neg hn, Real.sSup_empty] positivitytheorem shannon_or_capacity_categorical_prod_le_min_cliqueNum_le_fst {V W : Type*} [Fintype V] [Fintype W] (G : SimpleGraph V) (H : SimpleGraph W) (n : ℕ) : (simple_graph_or_power (simple_graph_categorical_prod G H) n).cliqueNum ≤ (simple_graph_or_power G n).cliqueNum := by classical obtain ⟨s, hs⟩ := (simple_graph_or_power (simple_graph_categorical_prod G H) n).exists_isNClique_cliqueNum rw [SimpleGraph.isNClique_iff] at hs rcases hs with ⟨hs_clique, hs_card⟩ let f : (Fin n → V × W) → (Fin n → V) := fun x => fun i => (x i).1 have hinj : ∀ x ∈ s, ∀ y ∈ s, f x = f y → x = y := by intro x hx y hy hxy by_contra hne have hadj := hs_clique hx hy hne simp only [simple_graph_or_power, simple_graph_categorical_prod] at hadj rcases hadj with ⟨i, hiG, _⟩ have hfi : f x i = f y i := congr_fun hxy i dsimp [f] at hfi exact G.ne_of_adj hiG hfi have hcard : s.card = (s.image f).card := by rw [Finset.card_image_of_injOn] intro x hx y hy hxy exact hinj x hx y hy hxy have hclique : (simple_graph_or_power G n).IsClique (s.image f : Set (Fin n → V)) := by intro u hu v hv huv rw [Finset.mem_coe, Finset.mem_image] at hu hv rcases hu with ⟨x, hx, rfl⟩ rcases hv with ⟨y, hy, rfl⟩ have hne : x ≠ y := by rintro rfl exact huv rfl have hadj := hs_clique hx hy hne simp only [simple_graph_or_power, simple_graph_categorical_prod] at hadj rcases hadj with ⟨i, hiG, _⟩ exact ⟨i, hiG⟩ have hle := SimpleGraph.IsClique.card_le_cliqueNum (tc := hclique) rw [← hs_card, hcard] exact hletheorem shannon_or_capacity_categorical_prod_le_min_cliqueNum_le_snd {V W : Type*} [Fintype V] [Fintype W] (G : SimpleGraph V) (H : SimpleGraph W) (n : ℕ) : (simple_graph_or_power (simple_graph_categorical_prod G H) n).cliqueNum ≤ (simple_graph_or_power H n).cliqueNum := by classical obtain ⟨s, hs⟩ := (simple_graph_or_power (simple_graph_categorical_prod G H) n).exists_isNClique_cliqueNum rw [SimpleGraph.isNClique_iff] at hs rcases hs with ⟨hs_clique, hs_card⟩ let f : (Fin n → V × W) → (Fin n → W) := fun x => fun i => (x i).2 have hinj : ∀ x ∈ s, ∀ y ∈ s, f x = f y → x = y := by intro x hx y hy hxy by_contra hne have hadj := hs_clique hx hy hne simp only [simple_graph_or_power, simple_graph_categorical_prod] at hadj rcases hadj with ⟨i, _, hiH⟩ have hfi : f x i = f y i := congr_fun hxy i dsimp [f] at hfi exact H.ne_of_adj hiH hfi have hcard : s.card = (s.image f).card := by rw [Finset.card_image_of_injOn] intro x hx y hy hxy exact hinj x hx y hy hxy have hclique : (simple_graph_or_power H n).IsClique (s.image f : Set (Fin n → W)) := by intro u hu v hv huv rw [Finset.mem_coe, Finset.mem_image] at hu hv rcases hu with ⟨x, hx, rfl⟩ rcases hv with ⟨y, hy, rfl⟩ have hne : x ≠ y := by rintro rfl exact huv rfl have hadj := hs_clique hx hy hne simp only [simple_graph_or_power, simple_graph_categorical_prod] at hadj rcases hadj with ⟨i, _, hiH⟩ exact ⟨i, hiH⟩ have hle := SimpleGraph.IsClique.card_le_cliqueNum (tc := hclique) rw [← hs_card, hcard] exact hletheorem shannon_or_capacity_categorical_prod_le_min_le_fst {V W : Type*} [Fintype V] [Nonempty V] [Fintype W] [Nonempty W] (G : SimpleGraph V) (H : SimpleGraph W) : shannon_or_capacity (simple_graph_categorical_prod G H) ≤ shannon_or_capacity G := by dsimp only [shannon_or_capacity] apply ciSup_le intro n by_cases hn : 1 ≤ n · rw [ciSup_pos hn] have hclique := shannon_or_capacity_categorical_prod_le_min_cliqueNum_le_fst G H n have hn_pos : 0 < (n : ℝ) := Nat.cast_pos.mpr hn have h_exp_pos : 0 ≤ (1 : ℝ) / n := one_div_nonneg.mpr (le_of_lt hn_pos) have h_rpow : ((simple_graph_or_power (simple_graph_categorical_prod G H) n).cliqueNum : ℝ) ^ ((1 : ℝ) / n) ≤ ((simple_graph_or_power G n).cliqueNum : ℝ) ^ ((1 : ℝ) / n) := by exact Real.rpow_le_rpow (by positivity) (by exact_mod_cast hclique) h_exp_pos have h_le_sup := le_ciSup (shannon_or_capacity_categorical_prod_le_min_bddAbove_shannon_range G) n rw [ciSup_pos hn] at h_le_sup exact h_rpow.trans h_le_sup · rw [ciSup_neg hn, Real.sSup_empty] have h1 : 1 ≤ 1 := le_refl 1 have h_pos : 0 ≤ ((simple_graph_or_power G 1).cliqueNum : ℝ) ^ ((1 : ℝ) / ↑(1 : ℕ)) := by positivity have h_le_sup := le_ciSup (shannon_or_capacity_categorical_prod_le_min_bddAbove_shannon_range G) 1 rw [ciSup_pos h1] at h_le_sup exact h_pos.trans h_le_suptheorem shannon_or_capacity_categorical_prod_le_min_le_snd {V W : Type*} [Fintype V] [Nonempty V] [Fintype W] [Nonempty W] (G : SimpleGraph V) (H : SimpleGraph W) : shannon_or_capacity (simple_graph_categorical_prod G H) ≤ shannon_or_capacity H := by dsimp only [shannon_or_capacity] apply ciSup_le intro n by_cases hn : 1 ≤ n · rw [ciSup_pos hn] have hclique := shannon_or_capacity_categorical_prod_le_min_cliqueNum_le_snd G H n have hn_pos : 0 < (n : ℝ) := Nat.cast_pos.mpr hn have h_exp_pos : 0 ≤ (1 : ℝ) / n := one_div_nonneg.mpr (le_of_lt hn_pos) have h_rpow : ((simple_graph_or_power (simple_graph_categorical_prod G H) n).cliqueNum : ℝ) ^ ((1 : ℝ) / n) ≤ ((simple_graph_or_power H n).cliqueNum : ℝ) ^ ((1 : ℝ) / n) := by exact Real.rpow_le_rpow (by positivity) (by exact_mod_cast hclique) h_exp_pos have h_le_sup := le_ciSup (shannon_or_capacity_categorical_prod_le_min_bddAbove_shannon_range H) n rw [ciSup_pos hn] at h_le_sup exact h_rpow.trans h_le_sup · rw [ciSup_neg hn, Real.sSup_empty] have h1 : 1 ≤ 1 := le_refl 1 have h_pos : 0 ≤ ((simple_graph_or_power H 1).cliqueNum : ℝ) ^ ((1 : ℝ) / ↑(1 : ℕ)) := by positivity have h_le_sup := le_ciSup (shannon_or_capacity_categorical_prod_le_min_bddAbove_shannon_range H) 1 rw [ciSup_pos h1] at h_le_sup exact h_pos.trans h_le_sup/-- The Shannon OR-capacity of a categorical product is at most the minimum of the factor capacities. -/theorem shannon_or_capacity_categorical_prod_le_min {V W : Type*} [Fintype V] [Nonempty V] [Fintype W] [Nonempty W] (G : SimpleGraph V) (H : SimpleGraph W) : shannon_or_capacity (simple_graph_categorical_prod G H) ≤ min (shannon_or_capacity G) (shannon_or_capacity H) := le_min (shannon_or_capacity_categorical_prod_le_min_le_fst G H) (shannon_or_capacity_categorical_prod_le_min_le_snd G H)