AFTD Auto-Formalizing Theoretical Domains

complete_order_graph_dim_six_min_size

theoremverifiedformalization

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.

  1. 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.

    line 4

    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⟩
See it in the graphDiscuss this resultChallenge it