AFTD Auto-Formalizing Theoretical Domains

bipartite_subgraph_poset_dimension_lower_bound

theoremverifiedformalization

Let V be a finite type with decidable equality, G a simple graph on V with decidable adjacency, and A, B subsets of V covering V such that G is bipartite with parts A and B. Let N = Fintype.card V and M = G.edgeFinset.card, with 2 ≤ N. Then there exists a spanning subgraph H ≤ G such that (M : ℝ) / Real.logb 2 (N.factorial : ℝ) ≤ (poset_dimension (bipartite_poset_le H A B) : ℝ).

Statement

theorem bipartite_subgraph_poset_dimension_lower_bound
    {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj]
    (A B : Set V) (h_cov : A ∪ B = Set.univ) (h_bip : G.IsBipartiteWith A B)
    (N M : ℕ) (hN : Fintype.card V = N) (hM : G.edgeFinset.card = M)
    (hN2 : 2 ≤ N) :
    ∃ H : SimpleGraph V, H ≤ G ∧
      (M : ℝ) / Real.logb 2 (N.factorial : ℝ) ≤ (poset_dimension (bipartite_poset_le H A B) : ℝ)
Formalizes
arXiv:2610.24774 Section 4.1, Lemma 4.2
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • bipartite_poset_leFor a graph H on α and subsets A, B of α, the height-2 order relation associated to H with bipartition (A, B) has x ≤ y if and only if x =…
  • poset_dimensionFor a relation r : α → α → Prop on α, poset_dimension r is the infimum in ℕ of the set of natural numbers d such that there exists a…
  • bipartite_subgraph_poset_dimension_pow_lower_boundLet V be a finite type with decidable equality, G a simple graph on V with decidable adjacency, and A, B subsets of V covering V such that…

Read back from the Lean

Let V be a finite type with decidable equality, and let G be a simple graph on V with decidable adjacency. Let A, B ⊆ V such that A ∪ B = V and G is bipartite with parts A and B (every edge of G has one endpoint in A and the other in B). Let N, M ∈ ℕ such that |V| = N, the number of edges of G is M, and N ≥ 2. Then there exists a subgraph H of G (H ≤ G) such that M / log₂(N!) ≤ poset_dimension(bipartite_poset_le H A B) (in ℝ).

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 proof deduces the lower bound on the poset dimension by taking logarithms of an existing exponential bound. It first invokes `bipartite_subgraph_poset_dimension_pow_lower_bound` to obtain a subgraph H ≤ G with 2^M ≤ (N!)^d, where d is the poset dimension of H. Taking natural logarithms of both sides and applying power laws produces M * ln 2 ≤ d * ln(N!). Finally, dividing by ln 2 expresses the bound in terms of the base-2 logarithm, M ≤ d * logb 2 (N!), which upon dividing by logb 2 (N!) > 0 gives M / logb 2 (N!) ≤ d.

  1. There exists a spanning subgraph H ≤ G satisfying 2^M ≤ (N!)^(poset_dimension H), reducing the goal to showing M / logb 2 (N!) ≤ poset_dimension H.

    We invoke the previously proved combinatorial lower bound `bipartite_subgraph_poset_dimension_pow_lower_bound`, which supplies a subgraph H ≤ G satisfying 2^M ≤ (N!)^d. We provide this H as the existential witness.

    lines 10–12

    uses bipartite_subgraph_poset_dimension_pow_lower_bound

      obtain ⟨H, hHG, hineq⟩ :=
        bipartite_subgraph_poset_dimension_pow_lower_bound G A B h_cov h_bip N M hN hM hN2
      refine ⟨H, hHG, ?_⟩
  2. Letting d denote the poset dimension of H, the inequality 2^M ≤ (N!)^d holds in ℝ.

    We abbreviate d = poset_dimension(bipartite_poset_le H A B), restate the inequality 2^M ≤ (N!)^d in terms of d, and cast it from ℕ to ℝ.

    lines 13–17

      set d : ℕ := poset_dimension (bipartite_poset_le H A B) with hd
      have hineq' : 2 ^ M ≤ N.factorial ^ d := by
        rw [hd]; exact hineq
      have hineqR : (2 : ℝ) ^ M ≤ (N.factorial : ℝ) ^ d := by
        exact_mod_cast hineq'
  3. Both 1 < N! (in ℝ) and 0 < ln 2 hold.

    Since N ≥ 2, we have 1 < N, and `Nat.one_lt_factorial.mpr` gives 1 < N!, which casts to 1 < N! in ℝ. Because 1 < 2, its natural logarithm is strictly positive by `Real.log_pos`.

    lines 18–21

    uses Nat.one_lt_factorial.mpr, Real.log_pos

      have hx1 : (1 : ℝ) < (N.factorial : ℝ) := by
        have h : 1 < N.factorial := Nat.one_lt_factorial.mpr (by omega)
        exact_mod_cast h
      have hlog2 : 0 < Real.log 2 := Real.log_pos (by norm_num)
  4. M * ln 2 ≤ d * ln(N!).

    Because 2^M > 0, taking the natural logarithm preserves the inequality (`Real.log_le_log`). Expanding powers via ln(x^k) = k * ln x (`Real.log_pow`) transforms ln(2^M) ≤ ln((N!)^d) into M * ln 2 ≤ d * ln(N!).

    lines 22–24

    uses Real.log_le_log, Real.log_pow

      have hlog : (M : ℝ) * Real.log 2 ≤ (d : ℝ) * Real.log (N.factorial : ℝ) := by
        have h := Real.log_le_log (by positivity : (0 : ℝ) < (2 : ℝ) ^ M) hineqR
        simpa only [Real.log_pow] using h
  5. M ≤ d * logb 2 (N!).

    By definition of `Real.logb`, logb 2 (N!) = ln(N!) / ln 2. Rewriting with associativity of multiplication and division (`mul_div_assoc`) gives d * logb 2 (N!) = (d * ln(N!)) / ln 2. Since ln 2 > 0, clearing the denominator via `le_div_iff₀` shows this is equivalent to the established inequality M * ln 2 ≤ d * ln(N!).

    lines 25–28

    uses Real.logb, mul_div_assoc, le_div_iff₀

      have hMle : (M : ℝ) ≤ (d : ℝ) * Real.logb 2 (N.factorial : ℝ) := by
        rw [Real.logb]
        rw [← mul_div_assoc]
        exact (le_div_iff₀ hlog2).mpr hlog
  6. Dividing by logb 2 (N!) yields M / logb 2 (N!) ≤ d.

    Since 1 < 2 and 1 < N!, the base-2 logarithm logb 2 (N!) is strictly positive (`Real.logb_pos`). Dividing both sides of M ≤ d * logb 2 (N!) by logb 2 (N!) using `div_le_iff₀` concludes the proof.

    lines 29–31

    uses Real.logb_pos, div_le_iff₀

      have hLpos : 0 < Real.logb 2 (N.factorial : ℝ) :=
        Real.logb_pos (by norm_num) hx1
      exact (div_le_iff₀ hLpos).mpr hMle
bipartite_subgraph_poset_dimension_pow_lower_bound
For a bipartite graph G with parts A and B covering V, with |V| = N (N ≥ 2) and |E(G)| = M, there exists a spanning subgraph H ≤ G such that 2^M ≤ (N!)^(poset_dimension H).
Nat.one_lt_factorial.mpr
If 1 < n, then 1 < n!.
Real.log_pos
If 1 < x, then 0 < ln x.
Real.log_le_log
If 0 < x and x ≤ y, then ln x ≤ ln y.
Real.log_pow
For real x and natural n, ln(x^n) = n * ln x.
Real.logb
The base-b logarithm of x is defined as ln x / ln b.
mul_div_assoc
In any division-inversion monoid, (a * b) / c = a * (b / c).
le_div_iff₀
For c > 0, a ≤ b / c holds if and only if a * c ≤ b.
Real.logb_pos
If 1 < b and 1 < x, then 0 < log_b x.
div_le_iff₀
For c > 0, b / c ≤ a holds if and only if b ≤ a * 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

/-- Dimension lower bound for subgraphs of a bipartite graph (arXiv:2610.24774 Lemma 4.2). -/theorem bipartite_subgraph_poset_dimension_lower_bound    {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj]    (A B : Set V) (h_cov : A ∪ B = Set.univ) (h_bip : G.IsBipartiteWith A B)    (N M : ℕ) (hN : Fintype.card V = N) (hM : G.edgeFinset.card = M)    (hN2 : 2 ≤ N) :    ∃ H : SimpleGraph V, H ≤ G ∧      (M : ℝ) / Real.logb 2 (N.factorial : ℝ) ≤ (poset_dimension (bipartite_poset_le H A B) : ℝ) := by  obtain ⟨H, hHG, hineq⟩ :=    bipartite_subgraph_poset_dimension_pow_lower_bound G A B h_cov h_bip N M hN hM hN2  refine ⟨H, hHG, ?_⟩  set d : ℕ := poset_dimension (bipartite_poset_le H A B) with hd  have hineq' : 2 ^ M ≤ N.factorial ^ d := by    rw [hd]; exact hineq  have hineqR : (2 : ℝ) ^ M ≤ (N.factorial : ℝ) ^ d := by    exact_mod_cast hineq'  have hx1 : (1 : ℝ) < (N.factorial : ℝ) := by    have h : 1 < N.factorial := Nat.one_lt_factorial.mpr (by omega)    exact_mod_cast h  have hlog2 : 0 < Real.log 2 := Real.log_pos (by norm_num)  have hlog : (M : ℝ) * Real.log 2 ≤ (d : ℝ) * Real.log (N.factorial : ℝ) := by    have h := Real.log_le_log (by positivity : (0 : ℝ) < (2 : ℝ) ^ M) hineqR    simpa only [Real.log_pow] using h  have hMle : (M : ℝ) ≤ (d : ℝ) * Real.logb 2 (N.factorial : ℝ) := by    rw [Real.logb]    rw [← mul_div_assoc]    exact (le_div_iff₀ hlog2).mpr hlog  have hLpos : 0 < Real.logb 2 (N.factorial : ℝ) :=    Real.logb_pos (by norm_num) hx1  exact (div_le_iff₀ hLpos).mpr hMle
See it in the graphDiscuss this resultChallenge it