AFTD Auto-Formalizing Theoretical Domains

complete_order_graph_dim_six_lower_bound

theoremverified

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

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.

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

    lines 1–9

    uses Finset.eq_univ_of_card, List.toFinset_card_of_nodup, List.mem_toFinset, Finset.mem_univ

    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 a
    
  2. 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.

    lines 10–14

    uses complete_order_graph_dim_six_lower_bound_order_mem_elems, dif_pos

    private 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)]
    
  3. 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.

    lines 15–22

    uses complete_order_graph_dim_six_lower_bound_omf_elems, List.erase_cons, if_neg

    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)]
    
  4. 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.

    lines 23–28

    uses complete_order_graph_dim_six_lower_bound_chain3_elems

    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]
      rfl
    
  5. 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.

    lines 29–34

    uses complete_order_graph_dim_six_lower_bound_chain3_elems

    private 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
    
  6. 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.

    lines 35–41

    uses complete_order_graph_dim_six_lower_bound_chain3_elems, List.idxOf_cons_ne

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

    lines 42–46

    uses Multiset.toFinset_card_eq_card_iff_nodup

    private 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
    
  8. 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.

    lines 47–57

    uses List.length_eq_three

    private 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
  9. 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.

    lines 58–67

    uses Finset.card_insert_of_notMem, complete_order_graph_dim_six_lower_bound_nodup_of_toFinset_card

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

    lines 68–87

    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_one

      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.symm
    
  11. 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.

    lines 88–92

    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]
    
  12. 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.

    lines 93–99

    uses Finset.mem_filter, complete_order_graph_dim_six_lower_bound_mem_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]
      tauto
    
  13. 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.

    lines 100–110

    uses Finset.card_le_one, Option.some.inj, Finset.card_insert_le

    private 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
    
  14. 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.

    lines 111–136

    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_fiber

    private 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⟩
  15. 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.

    lines 137–169

    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_two

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

    lines 170–186

    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 _ _)
  17. 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.

    lines 187–197

    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_nat

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

    lines 198–202

    uses Finset.card_le_card, complete_order_graph_dim_six_lower_bound_mem_edges_ge

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

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

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