complete_order_graph_dim_six_lower_bound
Every complete order graph of dimension 6 has at least 40 edges.
Statement
theorem complete_order_graph_dim_six_lower_bound (G : OrderGraph 6)
(hG : order_graph_is_complete G) : 40 ≤ G.E.card- Source
- arXiv:2610.39311 Corollary 8 -- Tight Asymptotic Bounds on the Size of Order Graphs
- Verified
- 08 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- 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_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 ≤…
- 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_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 ν.
- order_posThe 1-based position of attribute a in order π, taking values in {1, ..., d}.
- 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…
- 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_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…
- Used by 1
- 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,…
Read back from the Lean
For any order graph G of dimension 6 (an OrderGraph 6), if G is complete (order_graph_is_complete G), then the number of edges in G (G.E.card) is at least 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 theorem is proved by a double-counting / fiber argument over all 3-element subsets U ⊆ Fin 6. Each such subset U defines a fiber of edges e = (π, a) with order position at least 3 whose top-3 elements are U. By completeness of the graph, for each x ∈ U there is a serving path for U \ {x} that yields an edge in the fiber having x either as its label or at the second position of its source order. Because at most two elements can occupy these two positions in any single edge, no single edge can serve all three elements of U, so every fiber contains at least 2 edges. Summing over all (6 choose 3) = 20 subsets of size 3 shows that G has at least 2 * 20 = 40 edges.
Every element of Fin d belongs to the list π.elems of any order π.
Since π.elems has length d and contains no duplicate elements, its elements form the full universe Finset.univ of Fin d. Therefore any a ∈ Fin d belongs to π.elems.
uses
Finset.eq_univ_of_card,List.toFinset_card_of_nodup,List.mem_toFinset,Finset.mem_univprivate lemma complete_order_graph_dim_six_lower_bound_order_mem_elems {d : ℕ} (π : Order d) (a : Fin d) : a ∈ π.elems := by have h : π.elems.toFinset = Finset.univ := by apply Finset.eq_univ_of_card rw [List.toFinset_card_of_nodup π.nodup, π.length_eq] simp rw [← List.mem_toFinset, h] exact Finset.mem_univ a
Moving an element a to the front of π produces the list a :: π.elems.erase a.
By definition, order_move_to_front tests whether a ∈ π.elems. Since this holds unconditionally by the previous lemma, the positive branch of the definition applies.
uses
complete_order_graph_dim_six_lower_bound_order_mem_elems,dif_posprivate lemma complete_order_graph_dim_six_lower_bound_omf_elems {d : ℕ} (a : Fin d) (π : Order d) : (order_move_to_front a π).elems = a :: π.elems.erase a := by unfold order_move_to_front rw [dif_pos (complete_order_graph_dim_six_lower_bound_order_mem_elems π a)]
For distinct a1 ≠ a2, moving a1 then a2 to the front yields a2 :: a1 :: (π1.elems.erase a1).erase a2.
Unfolding the two move-to-front operations and applying list erasure, the condition a1 ≠ a2 ensures that erasing a2 from a1 :: ... does not remove the leading element a1.
uses
complete_order_graph_dim_six_lower_bound_omf_elems,List.erase_cons,if_negprivate lemma complete_order_graph_dim_six_lower_bound_chain3_elems {d : ℕ} {a1 a2 : Fin d} (h : a1 ≠ a2) (π1 : Order d) : (order_move_to_front a2 (order_move_to_front a1 π1)).elems = a2 :: a1 :: (π1.elems.erase a1).erase a2 := by rw [complete_order_graph_dim_six_lower_bound_omf_elems, complete_order_graph_dim_six_lower_bound_omf_elems, List.erase_cons] rw [if_neg (by simpa using h)]
The first two elements after moving a1 then a2 to the front (with a1 ≠ a2) are [a2, a1].
Taking the first two elements of the list a2 :: a1 :: ... gives [a2, a1] by definition.
uses
complete_order_graph_dim_six_lower_bound_chain3_elemsprivate lemma complete_order_graph_dim_six_lower_bound_chain3_take_two {d : ℕ} {a1 a2 : Fin d} (h : a1 ≠ a2) (π1 : Order d) : (order_move_to_front a2 (order_move_to_front a1 π1)).elems.take 2 = [a2, a1] := by rw [complete_order_graph_dim_six_lower_bound_chain3_elems h] rfl
The element at index 1 after moving a1 then a2 to the front (with a1 ≠ a2) is a1.
In the list a2 :: a1 :: ..., the element at 0-based index 1 is a1 by definition.
uses
complete_order_graph_dim_six_lower_bound_chain3_elemsprivate lemma complete_order_graph_dim_six_lower_bound_chain3_get_one {d : ℕ} {a1 a2 : Fin d} (h : a1 ≠ a2) (π1 : Order d) : (order_move_to_front a2 (order_move_to_front a1 π1)).elems[1]? = some a1 := by rw [complete_order_graph_dim_six_lower_bound_chain3_elems h] rfl
For pairwise distinct a1, a2, a3, the index of a3 in the list after moving a1 then a2 to the front is at least 2.
Since a3 is distinct from the first element a2 and the second element a1, each cons adds 1 to its index, so its 0-based index is at least 2.
uses
complete_order_graph_dim_six_lower_bound_chain3_elems,List.idxOf_cons_neprivate lemma complete_order_graph_dim_six_lower_bound_chain3_idxOf_ge {d : ℕ} {a1 a2 a3 : Fin d} (h12 : a1 ≠ a2) (h13 : a1 ≠ a3) (h23 : a2 ≠ a3) (π1 : Order d) : 2 ≤ List.idxOf a3 (order_move_to_front a2 (order_move_to_front a1 π1)).elems := by rw [complete_order_graph_dim_six_lower_bound_chain3_elems h12, List.idxOf_cons_ne _ h23, List.idxOf_cons_ne _ h13] omega
A list whose deduplicated set has cardinality equal to its length has no duplicates.
A multiset has no duplicate elements if and only if converting it to a finite set preserves its cardinality.
uses
Multiset.toFinset_card_eq_card_iff_nodupprivate lemma complete_order_graph_dim_six_lower_bound_nodup_of_toFinset_card {α : Type} [DecidableEq α] {l : List α} (h : l.toFinset.card = l.length) : l.Nodup := by have := (Multiset.toFinset_card_eq_card_iff_nodup (m := (l : Multiset α))).mp (by simpa using h) simpa using this
A path serving a 2-element set S has length 3, consisting of three consecutive edges e1, e2, e3.
From the definition of order_graph_serves, the serving path p has length |S| + 1 = 3, so p decomposes as [e1, e2, e3] where each source order is obtained from the previous by moving the transition label to the front.
uses
List.length_eq_threeprivate lemma complete_order_graph_dim_six_lower_bound_serves_three {G : OrderGraph 6} {S : Finset (Fin 6)} {x : Fin 6} (hx : x ∉ S) (hcard : S.card = 2) (hserv : order_graph_serves G S x) : ∃ e ∈ G.E, 3 ≤ order_pos e.1 e.2 ∧ order_graph_top_set 3 e = insert x S ∧ (x = e.2 ∨ e.1.elems[1]? = some x) := by rcases hserv with ⟨p, hp, hEdges, hChain, hLen, hLabels, hHL⟩ have hlen3 : p.length = 3 := by rw [hLen, hcard] obtain ⟨e1, e2, e3, rfl⟩ := List.length_eq_three.mp hlen3 have hstep : (e2.1 = order_move_to_front e1.2 e1.1) ∧ (e3.1 = order_move_to_front e2.2 e2.1) := by simpa [List.IsChain] using hChain obtain ⟨hstep12, hstep23⟩ := hstep
The three edge labels e1.2, e2.2, e3.2 are pairwise distinct, their set is insert x S, and either e1.2 = x or e3.2 = x.
Because x ∉ S and |S| = 2, the set insert x S has size 3. The labels form this set, so the list [e1.2, e2.2, e3.2] has length 3 and set size 3, meaning its elements are distinct. The boundary condition of a serving path forces x to be either the head label e1.2 or the tail label e3.2.
uses
Finset.card_insert_of_notMem,complete_order_graph_dim_six_lower_bound_nodup_of_toFinset_cardhave hmem3 : e3 ∈ G.E := hEdges e3 (by simp) have hset : ({e1.2, e2.2, e3.2} : Finset (Fin 6)) = insert x S := by simpa using hLabels have hcardU : (insert x S).card = 3 := by rw [Finset.card_insert_of_notMem hx, hcard] have hnod : ([e1.2, e2.2, e3.2] : List (Fin 6)).Nodup := by apply complete_order_graph_dim_six_lower_bound_nodup_of_toFinset_card simp [hset, hcardU] simp at hnod obtain ⟨⟨h12, h13⟩, h23⟩ := hnod have hHL' : e1.2 = x ∨ e3.2 = x := by simpa using hHL
The third edge e3 has order position at least 3, top set insert x S, and either x = e3.2 or x is at index 1 of e3.1.elems.
Because the three labels are pairwise distinct, e3.2 is at index at least 2 in e3.1, so its position is at least 3. Its top 3 elements are e3.2 together with the first two elements of e3.1 (which are e2.2 and e1.2), giving insert x S. Since x is either e1.2 or e3.2, either x = e3.2 or x sits at index 1 of e3.1.elems.
uses
complete_order_graph_dim_six_lower_bound_chain3_idxOf_ge,complete_order_graph_dim_six_lower_bound_chain3_take_two,complete_order_graph_dim_six_lower_bound_chain3_get_onehave hpos : 3 ≤ order_pos e3.1 e3.2 := by unfold order_pos rw [hstep23, hstep12] have := complete_order_graph_dim_six_lower_bound_chain3_idxOf_ge h12 h13 h23 e1.1 omega have h1 : order_graph_top_set 3 e3 = insert e3.2 ({e2.2, e1.2} : Finset (Fin 6)) := by simp only [order_graph_top_set, Nat.reduceSub, hstep23, hstep12, complete_order_graph_dim_six_lower_bound_chain3_take_two h12] simp have htop : order_graph_top_set 3 e3 = insert x S := by rw [h1, ← hset] ext y simp only [Finset.mem_insert, Finset.mem_singleton] tauto refine ⟨e3, hmem3, hpos, htop, ?_⟩ rcases hHL' with h | h · right rw [hstep23, hstep12, complete_order_graph_dim_six_lower_bound_chain3_get_one h12 e1.1, h] · left; exact h.symm
An edge e belongs to order_graph_edges_ge G m if and only if e ∈ G.E and m ≤ order_pos e.1 e.2. automation
This unfolds the definition of order_graph_edges_ge as a filter on G.E.
private lemma complete_order_graph_dim_six_lower_bound_mem_edges_ge {G : OrderGraph 6} {m : ℕ} {e : Order 6 × Fin 6} : e ∈ order_graph_edges_ge G m ↔ e ∈ G.E ∧ m ≤ order_pos e.1 e.2 := by simp [order_graph_edges_ge]
An edge belongs to the fiber of U under top set restricted to edges of position at least 3 iff e ∈ G.E, order_pos e.1 e.2 ≥ 3, and order_graph_top_set 3 e = U.
This rewrites membership in the filtered finset using the characterization of edges with position at least 3.
uses
Finset.mem_filter,complete_order_graph_dim_six_lower_bound_mem_edges_geprivate lemma complete_order_graph_dim_six_lower_bound_mem_fiber {G : OrderGraph 6} {U : Finset (Fin 6)} {e : Order 6 × Fin 6} : e ∈ (order_graph_edges_ge G 3).filter (fun e => order_graph_top_set 3 e = U) ↔ e ∈ G.E ∧ 3 ≤ order_pos e.1 e.2 ∧ order_graph_top_set 3 e = U := by rw [Finset.mem_filter, complete_order_graph_dim_six_lower_bound_mem_edges_ge] tauto
For any edge e, the set {e.2} ∪ {y | e.1.elems[1]? = some y} has cardinality at most 2.
A list can have at most one element at index 1, so the set of such y has cardinality at most 1. Inserting e.2 yields a set of cardinality at most 2.
uses
Finset.card_le_one,Option.some.inj,Finset.card_insert_leprivate lemma complete_order_graph_dim_six_lower_bound_head_set_card_le_two (e : Order 6 × Fin 6) : (insert e.2 (Finset.univ.filter (fun y : Fin 6 => e.1.elems[1]? = some y))).card ≤ 2 := by have h1 : (Finset.univ.filter (fun y : Fin 6 => e.1.elems[1]? = some y)).card ≤ 1 := by rw [Finset.card_le_one] intro a ha b hb simp only [Finset.mem_filter, Finset.mem_univ, true_and] at ha hb rw [ha] at hb exact Option.some.inj hb have h2 := Finset.card_insert_le e.2 (Finset.univ.filter (fun y : Fin 6 => e.1.elems[1]? = some y)) omega
For each 3-element set U = {p, q, r}, there exist edges ep, eq, er in the fiber of U corresponding to p, q, and r.
For each element x in {p, q, r}, the complement U \ {x} has cardinality 2. Since G is complete, it serves U \ {x} with x. The serving lemma yields an edge in the fiber of U where x is either the edge label or at index 1 of the source order. Specialized to p, q, r, this gives three edges ep, eq, er in the fiber.
uses
Finset.card_eq_three,Finset.notMem_erase,Finset.card_erase_of_mem,complete_order_graph_dim_six_lower_bound_serves_three,Finset.insert_erase,complete_order_graph_dim_six_lower_bound_mem_fiberprivate lemma complete_order_graph_dim_six_lower_bound_fiber_two {G : OrderGraph 6} (hG : order_graph_is_complete G) (U : Finset (Fin 6)) (hU : U.card = 3) : 2 ≤ ((order_graph_edges_ge G 3).filter (fun e => order_graph_top_set 3 e = U)).card := by classical obtain ⟨p, q, r, hpq, hpr, hqr, rfl⟩ := Finset.card_eq_three.mp hU have hU3 : ({p, q, r} : Finset (Fin 6)).card = 3 := by rw [Finset.card_eq_three]; exact ⟨p, q, r, hpq, hpr, hqr, rfl⟩ have hserve : ∀ x ∈ ({p, q, r} : Finset (Fin 6)), ∃ e : Order 6 × Fin 6, e ∈ G.E ∧ 3 ≤ order_pos e.1 e.2 ∧ order_graph_top_set 3 e = ({p, q, r} : Finset (Fin 6)) ∧ (x = e.2 ∨ e.1.elems[1]? = some x) := by intro x hx have hxnot : x ∉ ({p, q, r} : Finset (Fin 6)).erase x := Finset.notMem_erase x _ have hcard2 : (({p, q, r} : Finset (Fin 6)).erase x).card = 2 := by rw [Finset.card_erase_of_mem hx, hU3] obtain ⟨e, he, hpos, htop, hhl⟩ := complete_order_graph_dim_six_lower_bound_serves_three hxnot hcard2 (hG _ x hxnot) exact ⟨e, he, hpos, by rwa [Finset.insert_erase hx] at htop, hhl⟩ obtain ⟨ep, hep_mem, hep_pos, hep_top, hep_hl⟩ := hserve p (by simp) obtain ⟨eq, heq_mem, heq_pos, heq_top, heq_hl⟩ := hserve q (by simp) obtain ⟨er, her_mem, her_pos, her_top, her_hl⟩ := hserve r (by simp) have hFep : ep ∈ (order_graph_edges_ge G 3).filter (fun e => order_graph_top_set 3 e = {p,q,r}) := by rw [complete_order_graph_dim_six_lower_bound_mem_fiber]; exact ⟨hep_mem, hep_pos, hep_top⟩ have hFeq : eq ∈ (order_graph_edges_ge G 3).filter (fun e => order_graph_top_set 3 e = {p,q,r}) := by rw [complete_order_graph_dim_six_lower_bound_mem_fiber]; exact ⟨heq_mem, heq_pos, heq_top⟩ have hFer : er ∈ (order_graph_edges_ge G 3).filter (fun e => order_graph_top_set 3 e = {p,q,r}) := by rw [complete_order_graph_dim_six_lower_bound_mem_fiber]; exact ⟨her_mem, her_pos, her_top⟩
The fiber of U has cardinality at least 2.
Suppose for contradiction that the fiber has cardinality at most 1. Then ep, eq, and er must all be the same edge ep. This implies that all three elements p, q, r belong to the head set {ep.2} ∪ {y | ep.1.elems[1]? = some y}. But this set has cardinality at least 3 (containing {p, q, r}) and at most 2 (by the head set bound), a contradiction.
uses
Finset.card_le_one,Finset.mem_insert,Or.inl,Or.inr,Finset.mem_filter,Finset.mem_univ,Finset.card_le_card,complete_order_graph_dim_six_lower_bound_head_set_card_le_twoby_contra hcon have hcard1 : ((order_graph_edges_ge G 3).filter (fun e => order_graph_top_set 3 e = {p,q,r})).card ≤ 1 := by omega have hepq : ep = eq := Finset.card_le_one.mp hcard1 ep hFep eq hFeq have hepr : ep = er := Finset.card_le_one.mp hcard1 ep hFep er hFer let S := insert ep.2 (Finset.univ.filter (fun y : Fin 6 => ep.1.elems[1]? = some y)) have hpS : p ∈ S := by rcases hep_hl with h | h · exact Finset.mem_insert.mpr (Or.inl h) · exact Finset.mem_insert.mpr (Or.inr (Finset.mem_filter.mpr ⟨Finset.mem_univ _, h⟩)) have hqS : q ∈ S := by rcases heq_hl with h | h · exact Finset.mem_insert.mpr (Or.inl (by rw [hepq]; exact h)) · exact Finset.mem_insert.mpr (Or.inr (Finset.mem_filter.mpr ⟨Finset.mem_univ _, by rw [hepq]; exact h⟩)) have hrS : r ∈ S := by rcases her_hl with h | h · exact Finset.mem_insert.mpr (Or.inl (by rw [hepr]; exact h)) · exact Finset.mem_insert.mpr (Or.inr (Finset.mem_filter.mpr ⟨Finset.mem_univ _, by rw [hepr]; exact h⟩)) have hsub : ({p, q, r} : Finset (Fin 6)) ⊆ S := by intro x hx simp only [Finset.mem_insert, Finset.mem_singleton] at hx rcases hx with rfl | rfl | rfl · exact hpS · exact hqS · exact hrS have h3 : 3 ≤ S.card := by have := Finset.card_le_card hsub rwa [hU3] at this have h2 : S.card ≤ 2 := complete_order_graph_dim_six_lower_bound_head_set_card_le_two ep omega
The fibers F(U) over all 3-subsets U are pairwise disjoint and contained in the edges of position at least 3.
Two edges with different top sets cannot belong to the same fiber, so the fibers are pairwise disjoint. The cardinality of their union is the sum of their cardinalities, and their union is a subset of the edges with position at least 3.
uses
Finset.disjoint_left,Finset.card_biUnion,Finset.biUnion_subset,Finset.filter_subset/-- Lower bound on the number of edges of a complete order graph of dimension 6. -/ theorem complete_order_graph_dim_six_lower_bound (G : OrderGraph 6) (hG : order_graph_is_complete G) : 40 ≤ G.E.card := by classical let S := Finset.powersetCard 3 (Finset.univ : Finset (Fin 6)) let F : Finset (Fin 6) → Finset (Order 6 × Fin 6) := fun U => (order_graph_edges_ge G 3).filter (fun e => order_graph_top_set 3 e = U) have hdisj : (S : Set (Finset (Fin 6))).PairwiseDisjoint F := by intro U _ U' _ hne change Disjoint (F U) (F U') rw [Finset.disjoint_left] intro e he he' simp only [F, Finset.mem_filter] at he he' exact hne (he.2.symm.trans he'.2) have hcard : (S.biUnion F).card = ∑ U ∈ S, (F U).card := Finset.card_biUnion hdisj have hsub : S.biUnion F ⊆ order_graph_edges_ge G 3 := Finset.biUnion_subset.mpr (fun U _ => Finset.filter_subset _ _)
The sum of the fiber cardinalities over all 3-subsets of Fin 6 is at least 40.
Since every 3-subset U has fiber size at least 2, and there are (6 choose 3) = 20 such subsets, the sum of all fiber cardinalities is at least 2 * 20 = 40.
uses
Finset.mem_powersetCard,complete_order_graph_dim_six_lower_bound_fiber_two,Finset.card_powersetCard,Finset.card_univ,Fintype.card_fin,Finset.sum_le_sum,Finset.sum_const_nathave hfiber : ∀ U ∈ S, 2 ≤ (F U).card := by intro U hU rw [Finset.mem_powersetCard] at hU exact complete_order_graph_dim_six_lower_bound_fiber_two hG U hU.2 have h2 : (2 : ℕ) * S.card = 40 := by simp only [S, Finset.card_powersetCard, Finset.card_univ, Fintype.card_fin] decide have hsum : 40 ≤ ∑ U ∈ S, (F U).card := by have h1 : ∑ U ∈ S, 2 ≤ ∑ U ∈ S, (F U).card := Finset.sum_le_sum hfiber rw [Finset.sum_const_nat (fun _ _ => rfl)] at h1 omega
The graph G has at least 40 edges: 40 ≤ G.E.card.
By chaining inequalities: 40 ≤ ∑ |F(U)| = |⋃ F(U)| ≤ |order_graph_edges_ge G 3| ≤ |G.E|.
uses
Finset.card_le_card,complete_order_graph_dim_six_lower_bound_mem_edges_gecalc 40 ≤ ∑ U ∈ S, (F U).card := hsum _ = (S.biUnion F).card := hcard.symm _ ≤ (order_graph_edges_ge G 3).card := Finset.card_le_card hsub _ ≤ G.E.card := Finset.card_le_card (fun e he => (complete_order_graph_dim_six_lower_bound_mem_edges_ge.mp he).1)
complete_order_graph_dim_six_lower_bound_order_mem_elems- Every element of Fin d is present in the underlying list of any order π.
complete_order_graph_dim_six_lower_bound_omf_elems- Moving an element a to the front of π results in the list a :: π.elems.erase a.
complete_order_graph_dim_six_lower_bound_chain3_elems- For distinct a1 ≠ a2, successively moving a1 then a2 to the front yields a2 :: a1 :: (π.elems.erase a1).erase a2.
complete_order_graph_dim_six_lower_bound_chain3_take_two- Taking the first two elements after moving a1 then a2 to the front gives [a2, a1].
complete_order_graph_dim_six_lower_bound_chain3_get_one- The element at index 1 after moving a1 then a2 to the front is a1.
complete_order_graph_dim_six_lower_bound_chain3_idxOf_ge- For pairwise distinct a1, a2, a3, the index of a3 in the list after moving a1 then a2 to the front is at least 2.
complete_order_graph_dim_six_lower_bound_nodup_of_toFinset_card- A list whose finite set of elements has cardinality equal to its length has no duplicates.
complete_order_graph_dim_six_lower_bound_serves_three- If G serves S and x with |S| = 2 and x ∉ S, there is an edge in G.E with order position at least 3, top set S ∪ {x}, and x either as its label or at index 1 of its source order.
complete_order_graph_dim_six_lower_bound_mem_edges_ge- An edge belongs to order_graph_edges_ge G m if and only if it is in G.E and has order position at least m.
complete_order_graph_dim_six_lower_bound_mem_fiber- An edge belongs to the fiber of U under top set restricted to edges of position at least 3 if and only if it is in G.E, has position at least 3, and top set U.
complete_order_graph_dim_six_lower_bound_head_set_card_le_two- The set consisting of the label of an edge and its element at index 1 has cardinality at most 2.
complete_order_graph_dim_six_lower_bound_fiber_two- In a complete order graph on 6 vertices, every 3-element subset has at least 2 edges in its fiber.
Finset.eq_univ_of_card- A subset of a finite type whose cardinality equals the cardinality of the type is the entire universe.
List.toFinset_card_of_nodup- Converting a list without duplicates to a finite set preserves its length as cardinality.
List.mem_toFinset- An element belongs to the finset conversion of a list if and only if it belongs to the list.
Finset.mem_univ- Every element of a finite type belongs to the universal finset.
dif_pos- A dependent if-then-else evaluates to its first branch when the condition holds.
List.erase_cons- Erasing an element from a non-empty list removes the head if it matches, or else erases from the tail.
if_neg- An if-then-else evaluates to the else-branch when the condition is false.
List.idxOf_cons_ne- Prepending an element different from the target increases its list index by 1.
Multiset.toFinset_card_eq_card_iff_nodup- A multiset is duplicate-free if and only if its deduplicated finset has the same cardinality.
List.length_eq_three- A list has length 3 if and only if it consists of three elements.
Finset.card_insert_of_notMem- Inserting an element not in a finite set increases its cardinality by 1.
Finset.mem_filter- An element belongs to a filtered finset if and only if it belongs to the set and satisfies the predicate.
Finset.card_le_one- A finite set has cardinality at most 1 if and only if any two of its elements are equal.
Option.some.inj- The some constructor of Option is injective.
Finset.card_insert_le- Inserting an element into a finite set increases its cardinality by at most 1.
Finset.card_eq_three- A finite set has cardinality 3 if and only if it consists of three distinct elements.
Finset.notMem_erase- An element is not in the set obtained by erasing that element.
Finset.card_erase_of_mem- Erasing an element from a finite set decreases its cardinality by 1.
Finset.insert_erase- Inserting an element back into a set from which it was erased restores the set.
Finset.mem_insert- An element belongs to insert a s if and only if it equals a or belongs to s.
Or.inl- From a proof of P, one obtains a proof of P ∨ Q.
Or.inr- From a proof of Q, one obtains a proof of P ∨ Q.
Finset.card_le_card- A subset has cardinality at most that of the superset.
Finset.disjoint_left- Two finite sets are disjoint if and only if no element belongs to both.
Finset.card_biUnion- The cardinality of a pairwise disjoint union of finite sets is the sum of their cardinalities.
Finset.biUnion_subset- A union of indexed sets is a subset of a target set if each member set is a subset.
Finset.filter_subset- A filtered finset is a subset of the original set.
Finset.mem_powersetCard- A set belongs to powersetCard n t if and only if it is a subset of t of cardinality n.
Finset.card_powersetCard- The number of subsets of size n of a finite set s is |s|.choose n.
Finset.card_univ- The universal finset of a finite type has cardinality equal to that type's cardinality.
Fintype.card_fin- The cardinality of Fin n is n.
Finset.sum_le_sum- If f i ≤ g i for all elements of a finite set, then ∑ i, f i ≤ ∑ i, g i.
Finset.sum_const_nat- Summing a constant natural number c over a finite set s yields |s| * c.
- The proof relies on helper lemmas establishing the concrete effect of repeated `order_move_to_front` operations on lists, which on paper is immediate from the definition of the move-to-front operation.
- Counting and arithmetic bounds, including the evaluation of 2 * (6 choose 3) = 40, are closed by Lean's `decide` and `omega` decision procedures.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
private lemma complete_order_graph_dim_six_lower_bound_order_mem_elems {d : ℕ} (π : Order d) (a : Fin d) : a ∈ π.elems := by have h : π.elems.toFinset = Finset.univ := by apply Finset.eq_univ_of_card rw [List.toFinset_card_of_nodup π.nodup, π.length_eq] simp rw [← List.mem_toFinset, h] exact Finset.mem_univ aprivate lemma complete_order_graph_dim_six_lower_bound_omf_elems {d : ℕ} (a : Fin d) (π : Order d) : (order_move_to_front a π).elems = a :: π.elems.erase a := by unfold order_move_to_front rw [dif_pos (complete_order_graph_dim_six_lower_bound_order_mem_elems π a)]private lemma complete_order_graph_dim_six_lower_bound_chain3_elems {d : ℕ} {a1 a2 : Fin d} (h : a1 ≠ a2) (π1 : Order d) : (order_move_to_front a2 (order_move_to_front a1 π1)).elems = a2 :: a1 :: (π1.elems.erase a1).erase a2 := by rw [complete_order_graph_dim_six_lower_bound_omf_elems, complete_order_graph_dim_six_lower_bound_omf_elems, List.erase_cons] rw [if_neg (by simpa using h)]private lemma complete_order_graph_dim_six_lower_bound_chain3_take_two {d : ℕ} {a1 a2 : Fin d} (h : a1 ≠ a2) (π1 : Order d) : (order_move_to_front a2 (order_move_to_front a1 π1)).elems.take 2 = [a2, a1] := by rw [complete_order_graph_dim_six_lower_bound_chain3_elems h] rflprivate lemma complete_order_graph_dim_six_lower_bound_chain3_get_one {d : ℕ} {a1 a2 : Fin d} (h : a1 ≠ a2) (π1 : Order d) : (order_move_to_front a2 (order_move_to_front a1 π1)).elems[1]? = some a1 := by rw [complete_order_graph_dim_six_lower_bound_chain3_elems h] rflprivate lemma complete_order_graph_dim_six_lower_bound_chain3_idxOf_ge {d : ℕ} {a1 a2 a3 : Fin d} (h12 : a1 ≠ a2) (h13 : a1 ≠ a3) (h23 : a2 ≠ a3) (π1 : Order d) : 2 ≤ List.idxOf a3 (order_move_to_front a2 (order_move_to_front a1 π1)).elems := by rw [complete_order_graph_dim_six_lower_bound_chain3_elems h12, List.idxOf_cons_ne _ h23, List.idxOf_cons_ne _ h13] omegaprivate lemma complete_order_graph_dim_six_lower_bound_nodup_of_toFinset_card {α : Type} [DecidableEq α] {l : List α} (h : l.toFinset.card = l.length) : l.Nodup := by have := (Multiset.toFinset_card_eq_card_iff_nodup (m := (l : Multiset α))).mp (by simpa using h) simpa using thisprivate lemma complete_order_graph_dim_six_lower_bound_serves_three {G : OrderGraph 6} {S : Finset (Fin 6)} {x : Fin 6} (hx : x ∉ S) (hcard : S.card = 2) (hserv : order_graph_serves G S x) : ∃ e ∈ G.E, 3 ≤ order_pos e.1 e.2 ∧ order_graph_top_set 3 e = insert x S ∧ (x = e.2 ∨ e.1.elems[1]? = some x) := by rcases hserv with ⟨p, hp, hEdges, hChain, hLen, hLabels, hHL⟩ have hlen3 : p.length = 3 := by rw [hLen, hcard] obtain ⟨e1, e2, e3, rfl⟩ := List.length_eq_three.mp hlen3 have hstep : (e2.1 = order_move_to_front e1.2 e1.1) ∧ (e3.1 = order_move_to_front e2.2 e2.1) := by simpa [List.IsChain] using hChain obtain ⟨hstep12, hstep23⟩ := hstep have hmem3 : e3 ∈ G.E := hEdges e3 (by simp) have hset : ({e1.2, e2.2, e3.2} : Finset (Fin 6)) = insert x S := by simpa using hLabels have hcardU : (insert x S).card = 3 := by rw [Finset.card_insert_of_notMem hx, hcard] have hnod : ([e1.2, e2.2, e3.2] : List (Fin 6)).Nodup := by apply complete_order_graph_dim_six_lower_bound_nodup_of_toFinset_card simp [hset, hcardU] simp at hnod obtain ⟨⟨h12, h13⟩, h23⟩ := hnod have hHL' : e1.2 = x ∨ e3.2 = x := by simpa using hHL have hpos : 3 ≤ order_pos e3.1 e3.2 := by unfold order_pos rw [hstep23, hstep12] have := complete_order_graph_dim_six_lower_bound_chain3_idxOf_ge h12 h13 h23 e1.1 omega have h1 : order_graph_top_set 3 e3 = insert e3.2 ({e2.2, e1.2} : Finset (Fin 6)) := by simp only [order_graph_top_set, Nat.reduceSub, hstep23, hstep12, complete_order_graph_dim_six_lower_bound_chain3_take_two h12] simp have htop : order_graph_top_set 3 e3 = insert x S := by rw [h1, ← hset] ext y simp only [Finset.mem_insert, Finset.mem_singleton] tauto refine ⟨e3, hmem3, hpos, htop, ?_⟩ rcases hHL' with h | h · right rw [hstep23, hstep12, complete_order_graph_dim_six_lower_bound_chain3_get_one h12 e1.1, h] · left; exact h.symmprivate lemma complete_order_graph_dim_six_lower_bound_mem_edges_ge {G : OrderGraph 6} {m : ℕ} {e : Order 6 × Fin 6} : e ∈ order_graph_edges_ge G m ↔ e ∈ G.E ∧ m ≤ order_pos e.1 e.2 := by simp [order_graph_edges_ge]private lemma complete_order_graph_dim_six_lower_bound_mem_fiber {G : OrderGraph 6} {U : Finset (Fin 6)} {e : Order 6 × Fin 6} : e ∈ (order_graph_edges_ge G 3).filter (fun e => order_graph_top_set 3 e = U) ↔ e ∈ G.E ∧ 3 ≤ order_pos e.1 e.2 ∧ order_graph_top_set 3 e = U := by rw [Finset.mem_filter, complete_order_graph_dim_six_lower_bound_mem_edges_ge] tautoprivate lemma complete_order_graph_dim_six_lower_bound_head_set_card_le_two (e : Order 6 × Fin 6) : (insert e.2 (Finset.univ.filter (fun y : Fin 6 => e.1.elems[1]? = some y))).card ≤ 2 := by have h1 : (Finset.univ.filter (fun y : Fin 6 => e.1.elems[1]? = some y)).card ≤ 1 := by rw [Finset.card_le_one] intro a ha b hb simp only [Finset.mem_filter, Finset.mem_univ, true_and] at ha hb rw [ha] at hb exact Option.some.inj hb have h2 := Finset.card_insert_le e.2 (Finset.univ.filter (fun y : Fin 6 => e.1.elems[1]? = some y)) omegaprivate lemma complete_order_graph_dim_six_lower_bound_fiber_two {G : OrderGraph 6} (hG : order_graph_is_complete G) (U : Finset (Fin 6)) (hU : U.card = 3) : 2 ≤ ((order_graph_edges_ge G 3).filter (fun e => order_graph_top_set 3 e = U)).card := by classical obtain ⟨p, q, r, hpq, hpr, hqr, rfl⟩ := Finset.card_eq_three.mp hU have hU3 : ({p, q, r} : Finset (Fin 6)).card = 3 := by rw [Finset.card_eq_three]; exact ⟨p, q, r, hpq, hpr, hqr, rfl⟩ have hserve : ∀ x ∈ ({p, q, r} : Finset (Fin 6)), ∃ e : Order 6 × Fin 6, e ∈ G.E ∧ 3 ≤ order_pos e.1 e.2 ∧ order_graph_top_set 3 e = ({p, q, r} : Finset (Fin 6)) ∧ (x = e.2 ∨ e.1.elems[1]? = some x) := by intro x hx have hxnot : x ∉ ({p, q, r} : Finset (Fin 6)).erase x := Finset.notMem_erase x _ have hcard2 : (({p, q, r} : Finset (Fin 6)).erase x).card = 2 := by rw [Finset.card_erase_of_mem hx, hU3] obtain ⟨e, he, hpos, htop, hhl⟩ := complete_order_graph_dim_six_lower_bound_serves_three hxnot hcard2 (hG _ x hxnot) exact ⟨e, he, hpos, by rwa [Finset.insert_erase hx] at htop, hhl⟩ obtain ⟨ep, hep_mem, hep_pos, hep_top, hep_hl⟩ := hserve p (by simp) obtain ⟨eq, heq_mem, heq_pos, heq_top, heq_hl⟩ := hserve q (by simp) obtain ⟨er, her_mem, her_pos, her_top, her_hl⟩ := hserve r (by simp) have hFep : ep ∈ (order_graph_edges_ge G 3).filter (fun e => order_graph_top_set 3 e = {p,q,r}) := by rw [complete_order_graph_dim_six_lower_bound_mem_fiber]; exact ⟨hep_mem, hep_pos, hep_top⟩ have hFeq : eq ∈ (order_graph_edges_ge G 3).filter (fun e => order_graph_top_set 3 e = {p,q,r}) := by rw [complete_order_graph_dim_six_lower_bound_mem_fiber]; exact ⟨heq_mem, heq_pos, heq_top⟩ have hFer : er ∈ (order_graph_edges_ge G 3).filter (fun e => order_graph_top_set 3 e = {p,q,r}) := by rw [complete_order_graph_dim_six_lower_bound_mem_fiber]; exact ⟨her_mem, her_pos, her_top⟩ by_contra hcon have hcard1 : ((order_graph_edges_ge G 3).filter (fun e => order_graph_top_set 3 e = {p,q,r})).card ≤ 1 := by omega have hepq : ep = eq := Finset.card_le_one.mp hcard1 ep hFep eq hFeq have hepr : ep = er := Finset.card_le_one.mp hcard1 ep hFep er hFer let S := insert ep.2 (Finset.univ.filter (fun y : Fin 6 => ep.1.elems[1]? = some y)) have hpS : p ∈ S := by rcases hep_hl with h | h · exact Finset.mem_insert.mpr (Or.inl h) · exact Finset.mem_insert.mpr (Or.inr (Finset.mem_filter.mpr ⟨Finset.mem_univ _, h⟩)) have hqS : q ∈ S := by rcases heq_hl with h | h · exact Finset.mem_insert.mpr (Or.inl (by rw [hepq]; exact h)) · exact Finset.mem_insert.mpr (Or.inr (Finset.mem_filter.mpr ⟨Finset.mem_univ _, by rw [hepq]; exact h⟩)) have hrS : r ∈ S := by rcases her_hl with h | h · exact Finset.mem_insert.mpr (Or.inl (by rw [hepr]; exact h)) · exact Finset.mem_insert.mpr (Or.inr (Finset.mem_filter.mpr ⟨Finset.mem_univ _, by rw [hepr]; exact h⟩)) have hsub : ({p, q, r} : Finset (Fin 6)) ⊆ S := by intro x hx simp only [Finset.mem_insert, Finset.mem_singleton] at hx rcases hx with rfl | rfl | rfl · exact hpS · exact hqS · exact hrS have h3 : 3 ≤ S.card := by have := Finset.card_le_card hsub rwa [hU3] at this have h2 : S.card ≤ 2 := complete_order_graph_dim_six_lower_bound_head_set_card_le_two ep omega/-- Lower bound on the number of edges of a complete order graph of dimension 6. -/theorem complete_order_graph_dim_six_lower_bound (G : OrderGraph 6) (hG : order_graph_is_complete G) : 40 ≤ G.E.card := by classical let S := Finset.powersetCard 3 (Finset.univ : Finset (Fin 6)) let F : Finset (Fin 6) → Finset (Order 6 × Fin 6) := fun U => (order_graph_edges_ge G 3).filter (fun e => order_graph_top_set 3 e = U) have hdisj : (S : Set (Finset (Fin 6))).PairwiseDisjoint F := by intro U _ U' _ hne change Disjoint (F U) (F U') rw [Finset.disjoint_left] intro e he he' simp only [F, Finset.mem_filter] at he he' exact hne (he.2.symm.trans he'.2) have hcard : (S.biUnion F).card = ∑ U ∈ S, (F U).card := Finset.card_biUnion hdisj have hsub : S.biUnion F ⊆ order_graph_edges_ge G 3 := Finset.biUnion_subset.mpr (fun U _ => Finset.filter_subset _ _) have hfiber : ∀ U ∈ S, 2 ≤ (F U).card := by intro U hU rw [Finset.mem_powersetCard] at hU exact complete_order_graph_dim_six_lower_bound_fiber_two hG U hU.2 have h2 : (2 : ℕ) * S.card = 40 := by simp only [S, Finset.card_powersetCard, Finset.card_univ, Fintype.card_fin] decide have hsum : 40 ≤ ∑ U ∈ S, (F U).card := by have h1 : ∑ U ∈ S, 2 ≤ ∑ U ∈ S, (F U).card := Finset.sum_le_sum hfiber rw [Finset.sum_const_nat (fun _ _ => rfl)] at h1 omega calc 40 ≤ ∑ U ∈ S, (F U).card := hsum _ = (S.biUnion F).card := hcard.symm _ ≤ (order_graph_edges_ge G 3).card := Finset.card_le_card hsub _ ≤ G.E.card := Finset.card_le_card (fun e he => (complete_order_graph_dim_six_lower_bound_mem_edges_ge.mp he).1)