simple_graph_categorical_prod
The 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 (u₂, v₂) if and only if u₁ is adjacent to u₂ in G and v₁ is adjacent to v₂ in H.
Statement
def simple_graph_categorical_prod {V W : Type*} (G : SimpleGraph V) (H : SimpleGraph W) : SimpleGraph (V × W)
- Defined in
- arXiv:2610.41977 Sec. 1
- Verified
- 03 Nov 2026
- Axioms
- none listed
- Used by 5
- 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…
- random_switching_distinguishability_graphFor any discrete memoryless channels W_G and W_H and switching parameter p ∈ (0, 1), the distinguishability graph of the random switching…
- 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…
- proposition_5_1_random_switching_channel_realizationFor any discrete memoryless channels W_G and W_H and any switching probability p ∈ (0, 1), the distinguishability graph of the switched…
- 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
Definition of the categorical (tensor/direct) product of two simple graphs. Given arbitrary types V and W (implicit), and simple graphs G : SimpleGraph V and H : SimpleGraph W (explicit), simple_graph_categorical_prod G H is the simple graph on the product type V × W whose adjacency relation Adj is defined by: two vertices x, y : V × W are adjacent if and only if x.1 is adjacent to y.1 in G and x.2 is adjacent to y.2 in H.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The categorical (tensor) product of two simple graphs. -/ def simple_graph_categorical_prod {V W : Type*} (G : SimpleGraph V) (H : SimpleGraph W) : SimpleGraph (V × W) := { Adj := fun x y => G.Adj x.1 y.1 ∧ H.Adj x.2 y.2 symm.symm := fun x y => by simp [SimpleGraph.adj_comm] }