bipartite_subgraph_poset_dimension_lower_bound
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.
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.
uses
bipartite_subgraph_poset_dimension_pow_lower_boundobtain ⟨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, ?_⟩
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 ℝ.
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'
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`.
uses
Nat.one_lt_factorial.mpr,Real.log_poshave 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)
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!).
uses
Real.log_le_log,Real.log_powhave 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
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!).
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
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.
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.
- The theorem relies on the exponential lower bound `bipartite_subgraph_poset_dimension_pow_lower_bound`, which encapsulates the underlying combinatorial argument; this proof handles the algebraic conversion to base-2 logarithmic form.
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.
/-- 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