Order
An order of dimension d is a permutation of the attribute set {0, ..., d-1}, represented as a list without duplicates containing all elements.
Statement
structure Order (d : ℕ)- Defined in
- arXiv:2610.39311 Definition 1
- Verified
- 31 Oct 2026
- Axioms
- none listed
- Used by 27
- complete_order_graph_dim_six_lower_boundEvery complete order graph of dimension 6 has at least 40 edges.
- 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 π :…
- bipartite_ravindra_matching_power_two_well_covered_diam_le_twoIf a finite connected bipartite simple graph G admits a perfect matching M with complete bipartite neighborhoods and its second power G^2…
- ordered_ramsey_monotone_cycle_alternating_path_twoFor all integers k ≥ 3, the ordered Ramsey number of the monotone cycle MC_k and the alternating path AP_2 is equal to k.
- connected_graph_129_independence_three_edge_boundEvery connected simple graph on 129 vertices with no independent set of size four has at least 2710 edges.
- exists_strictly_ordered_intervalsFor every countable linearly ordered type A, there exists a family of strictly separated intervals [l(a), r(a)] in (0, 1/2] such that a <…
- order_graph_serves_uniAn order graph G of dimension d serves requirement (S, x) where S is a finite set of Fin d and x : Fin d in the unidirectional model if…
- graph_125_high_degree_delete_complement_coloringIf a graph on 125 vertices has independence number at most three and at most 2583 edges, deleting a vertex of degree at least 46 leaves a…
- digraph_127_regular_independence_small_overlapA seven-outregular digraph on 127 vertices whose common-predecessor graph has independence number at most three satisfies the strict 3z…
- order_graph_edges_geGiven an order graph G of dimension d and a natural number m, order_graph_edges_ge G m is the subset of edges e ∈ G.E such that m ≤…
- le_of_not_set_coloring_ramsey_property_p3If there exists an (a, b)-set-coloring of the complete graph K_N without a monochromatic two-edge path P_3 in any single color, then b *…
- digraph_128_regular_independence_small_overlapA seven-outregular digraph on 128 vertices whose common-predecessor graph has independence number at most three satisfies the strict 3z…
- 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.
- digraph_129_regular_independence_small_overlapA seven-outregular digraph on 129 vertices whose common-predecessor graph has independence number at most three satisfies the strict 3z…
- order_posThe 1-based position of attribute a in order π, taking values in {1, ..., d}.
- regular_bipartite_decompose_perfect_matchingsEvery d-regular finite bipartite simple graph decomposes into d spanning one-regular subgraphs: every edge appears in exactly one of them.
- supertoken_graph_bipartiteLet G be a finite bipartite simple graph on vertex type V with decidable equality (satisfying G.IsBipartite). Let s ≥ 1 and 1 ≤ k ≤ s *…
- triangle_free_card_le_four_isBipartiteEvery finite simple graph on at most 4 vertices that is triangle-free is bipartite (2-colorable).
- hash_probe_tail_two_eq_adjacent_meanThe second probe-cost tail equals the expected number of occupied adjacent pairs, divided by the table size.
- complete_order_graph_dim_six_upper_boundThere exists a complete order graph of dimension 6 with exactly 40 edges.
- boxProd_completeGraph_all_powers_well_coveredLet G be a finite connected nontrivial graph, and let t be an integer with t > |V(G)|. If every positive power G^d (d ≥ 1) is…
- complete_order_graph_dim_six_min_sizeThe minimum size of a complete order graph of dimension 6 is exactly 40: every complete order graph of dimension 6 has at least 40 edges,…
- order_move_to_frontThe order obtained by moving attribute a to the front of order π, preserving the relative order of the remaining attributes.
- order_graph_top_setFor an edge e = (ν, a) and a level m, the top set U_m(e) is the set consisting of a together with the first m-1 labels of ν.
- digraph_126_four_cycles_under_extremal_and_cycle_criteriaA loopless oriented seven-outregular digraph on 126 vertices whose arcs have common predecessors and whose every in-neighborhood contains…
- order_graph_servesAn 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…
- digraph_125_no_four_cycles_overlap_windowFor a loopless oriented seven-outregular digraph on 125 vertices with dominated arcs, a cycle in each in-neighborhood, and no four…
Read back from the Lean
A structure Order d, parameterized by a natural number d : ℕ, consisting of:
1. elems: a list of elements of Fin d,
2. nodup: a proof that elems contains no duplicate elements (elems.Nodup),
3. length_eq: a proof that the length of elems is equal to d (elems.length = d).
The structure also derives decidable equality (DecidableEq). (Effectively, an Order d is a permutation / linear ordering of the d elements of Fin d represented as a list without duplicates containing all elements of Fin d).
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
/-- An order of dimension d is a permutation of Fin d, represented as a list of length d without duplicates. -/ structure Order (d : ℕ) where elems : List (Fin d) nodup : elems.Nodup length_eq : elems.length = d deriving DecidableEq