bipartite_poset_le
def
For a graph H on α and subsets A, B of α, the height-2 order relation associated to H with bipartition (A, B) has x ≤ y if and only if x = y or (x ∈ A, y ∈ B, and x and y are adjacent in H).
Statement
def bipartite_poset_le {α : Type*} (H : SimpleGraph α) (A B : Set α) (x y : α) : Prop
- Defined in
- arXiv:2610.24774, Section 4.1; Trotter, Combinatorics and Partially Ordered Sets (1992)
- Verified
- 22 Oct 2026
- Axioms
- none listed
- Used by 3
- bipartite_subgraph_poset_dimension_lower_boundLet V be a finite type with decidable equality, G a simple graph on V with decidable adjacency, and A, B subsets of V covering V such that…
- bipartite_poset_is_partial_orderIf A and B are disjoint subsets of α, then for any simple graph H on α, the relation bipartite_poset_le H A B is a partial order on α.
- bipartite_subgraph_poset_dimension_pow_lower_boundLet V be a finite type with decidable equality, G a simple graph on V with decidable adjacency, and A, B subsets of V covering V such that…
Read back from the Lean
Given a type α, a simple graph H on α, subsets A, B : Set α, and vertices x, y : α, bipartite_poset_le H A B x y is defined to hold if and only if x = y or (x ∈ A, y ∈ B, and x and y are adjacent 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 partial order relation of the height-2 poset associated to a bipartite graph. -/ def bipartite_poset_le {α : Type*} (H : SimpleGraph α) (A B : Set α) (x y : α) : Prop := x = y ∨ (x ∈ A ∧ y ∈ B ∧ H.Adj x y)