complete_order_graph_dim_six_min_size
The 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, and there exists a complete order graph of dimension 6 with exactly 40 edges.
Statement
theorem complete_order_graph_dim_six_min_size :
(∀ G : OrderGraph 6, order_graph_is_complete G → 40 ≤ G.E.card) ∧
(∃ G : OrderGraph 6, order_graph_is_complete G ∧ G.E.card = 40)- Formalizes
- arXiv:2610.39311 Corollary 8 -- Tight Asymptotic Bounds on the Size of Order Graphs
- Verified
- 08 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- complete_order_graph_dim_six_lower_boundEvery complete order graph of dimension 6 has at least 40 edges.
- complete_order_graph_dim_six_upper_boundThere exists a complete order graph of dimension 6 with exactly 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 π :…
- OrderAn order of dimension d is a permutation of the attribute set {0, ..., d-1}, represented as a list without duplicates containing all…
- 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
The declaration asserts that the minimum number of edges in a complete order graph of dimension 6 is 40. Specifically, it asserts the conjunction of two statements:
1. For every order graph G of dimension 6, if G is complete, then the cardinality of its edge set G.E is at least 40.
2. There exists an order graph G of dimension 6 such that G is complete and the cardinality of its edge set G.E is exactly 40.
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 minimum size of a complete order graph of dimension 6 is established by combining two companion results: a lower bound showing that any complete order graph of dimension 6 has at least 40 edges, and an upper bound showing the existence of one with exactly 40 edges. The proof simply pairs these two theorems into a conjunction.
The minimum edge count of a complete order graph of dimension 6 is 40: any such graph has at least 40 edges, and there exists one with exactly 40 edges.
The statement is a conjunction of a lower bound and an upper bound. The proof pairs the lower bound theorem (complete_order_graph_dim_six_lower_bound), which states that every complete order graph on 6 vertices has at least 40 edges, with the upper bound theorem (complete_order_graph_dim_six_upper_bound), which constructs a complete order graph with exactly 40 edges.
uses
complete_order_graph_dim_six_lower_bound,complete_order_graph_dim_six_upper_bound(∃ G : OrderGraph 6, order_graph_is_complete G ∧ G.E.card = 40) := ⟨complete_order_graph_dim_six_lower_bound, complete_order_graph_dim_six_upper_bound⟩
complete_order_graph_dim_six_lower_bound- Every complete order graph of dimension 6 contains at least 40 edges.
complete_order_graph_dim_six_upper_bound- There exists a complete order graph of dimension 6 containing exactly 40 edges.
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
/-- The minimum size of a complete order graph of dimension 6 is exactly 40 (arXiv:2610.39311 Corollary 8). -/theorem complete_order_graph_dim_six_min_size : (∀ G : OrderGraph 6, order_graph_is_complete G → 40 ≤ G.E.card) ∧ (∃ G : OrderGraph 6, order_graph_is_complete G ∧ G.E.card = 40) := ⟨complete_order_graph_dim_six_lower_bound, complete_order_graph_dim_six_upper_bound⟩