order_graph_serves
An order graph G serves requirement (S, x) where S is a finite set of Fin d and x : Fin d if there exists a nonempty list of edges p all in G.E, chaining by e2.1 = order_move_to_front e1.2 e1.1, such that p has length |S| + 1, the set of edge labels in p is insert x S, and either the first edge of p or the last edge of p has label x.
Statement
def order_graph_serves {d : ℕ} (G : OrderGraph d) (S : Finset (Fin d)) (x : Fin d) : Prop
- Defined in
- arXiv:2610.39311 Definition 2
- Verified
- 31 Oct 2026
- Axioms
- none listed
- Built on 3
- OrderGraphAn order graph of dimension d is a structure consisting of a finite set V of orders of Fin d and a finite set E of edges (π, a) where π :…
- order_move_to_frontThe order obtained by moving attribute a to the front of order π, preserving the relative order of the remaining attributes.
- OrderAn order of dimension d is a permutation of the attribute set {0, ..., d-1}, represented as a list without duplicates containing all…
- Used by 4
- complete_order_graph_dim_six_lower_boundEvery complete order graph of dimension 6 has at least 40 edges.
- order_graph_is_complete_of_complete_uniIf an order graph G of dimension d is complete in the unidirectional model, then G is complete in the bidirectional model.
- complete_order_graph_dim_six_upper_boundThere exists a complete order graph of dimension 6 with exactly 40 edges.
- order_graph_is_completeAn order graph G is complete in the bidirectional model if for every subset S ⊆ Fin d and every element x : Fin d with x ∉ S, G serves…
Read back from the Lean
For a natural number d, an order graph G on Fin d, a finite set S ⊆ Fin d, and an element x ∈ Fin d, order_graph_serves G S x asserts the existence of a non-empty list p of edges (each edge being a pair (π, a) of a permutation π of Fin d and a label a ∈ Fin d) such that:
1. Every edge in p belongs to G.E;
2. p forms a directed path/walk: for any two consecutive edges e₁, e₂ in p, the source permutation of e₂ is obtained from the source permutation of e₁ by moving the label of e₁ to the front (e₂.1 = order_move_to_front e₁.2 e₁.1);
3. The number of edges in p is |S| + 1;
4. The set of edge labels appearing in p is equal to {x} ∪ S;
5. The label of either the first edge in p or the last edge in p is x.
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
/-- G serves requirement (S, x) in the bidirectional model. -/ def order_graph_serves {d : ℕ} (G : OrderGraph d) (S : Finset (Fin d)) (x : Fin d) : Prop := ∃ (p : List (Order d × Fin d)) (hp : p ≠ []), (∀ e ∈ p, e ∈ G.E) ∧ p.IsChain (fun e1 e2 => e2.1 = order_move_to_front e1.2 e1.1) ∧ p.length = S.card + 1 ∧ (p.map Prod.snd).toFinset = insert x S ∧ ((p.head hp).2 = x ∨ (p.getLast hp).2 = x)