digraph_both_cuts_ge_ceil_div_six_of_two_partitions
If two vertex partitions have combined crossing count at least m and combined absolute directed-cut imbalance at most m/3, one partition has both directed cut counts at least the natural ceiling of m/6.
Statement
theorem digraph_both_cuts_ge_ceil_div_six_of_two_partitions {V : Type*} [Fintype V] [DecidableEq V] (G : Digraph V) [DecidableRel G.Adj] (A₀ A₁ : Finset V) (htotal : (digraph_edge_count G : ℚ) ≤ (digraph_cut_count G A₀ A₀ᶜ : ℚ) + digraph_cut_count G A₀ᶜ A₀ + digraph_cut_count G A₁ A₁ᶜ + digraph_cut_count G A₁ᶜ A₁) (hbalance : |(digraph_cut_count G A₀ A₀ᶜ : ℚ) - digraph_cut_count G A₀ᶜ A₀| + |(digraph_cut_count G A₁ A₁ᶜ : ℚ) - digraph_cut_count G A₁ᶜ A₁| ≤ (digraph_edge_count G : ℚ) / 3) : ∃ A : Finset V, ⌈(digraph_edge_count G : ℚ) / 6⌉₊ ≤ digraph_cut_count G A Aᶜ ∧ ⌈(digraph_edge_count G : ℚ) / 6⌉₊ ≤ digraph_cut_count G Aᶜ A
- Source
- Helper for digraph_both_cuts_ge_ceil_div_six_of_indegree_lt, arXiv:2610.21381, proof of Theorem 1.4, Case 2. The two-partition certificate and paired-outcome inequality are a deterministic formulation of the paper's averaging argument; no research advance is claimed.
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- digraph_cut_counte_G(A, B): the number of edges of the digraph G from a vertex of A to a vertex of B.
- digraph_edge_countThe number m of edges (arcs) of a finite digraph G.
The proof, explained
The proof establishes the algebraic identity 2 * min(a, b) = a + b - |a - b| to express the smaller directed cut of a partition in terms of its total cut size and imbalance. Summing this identity over both partitions gives 2 * min(x, y) + 2 * min(u, v) = (x + y + u + v) - (|x - y| + |u - v|) ≥ m - m/3 = 2m/3. Consequently, at least one of the two partitions must satisfy min(cut₁, cut₂) ≥ m/6, which immediately implies that both directed cuts for that partition are at least ⌈m/6⌉₊.
Introduce shorthand notation for the four directed cut counts.
Define the rational numbers x and y as the directed cut counts between A₀ and its complement in each direction, and u and v as the corresponding directed cut counts for A₁.
let x : ℚ := digraph_cut_count G A₀ A₀ᶜ let y : ℚ := digraph_cut_count G A₀ᶜ A₀ let u : ℚ := digraph_cut_count G A₁ A₁ᶜ let v : ℚ := digraph_cut_count G A₁ᶜ A₁
For any two rational numbers a and b, 2 * min(a, b) = a + b - |a - b|.
By totality of the order (le_total), either a ≤ b or b ≤ a. If a ≤ b, the minimum is a (min_eq_left), and because a - b ≤ 0 (sub_nonpos.mpr), its absolute value is -(a - b) (abs_of_nonpos); ring arithmetic then simplifies a + b - -(a - b) to 2 * a. The symmetric case b ≤ a follows identically using min_eq_right, sub_nonneg.mpr, and abs_of_nonneg.
uses
le_total,min_eq_left,abs_of_nonpos,sub_nonpos.mpr,min_eq_right,abs_of_nonneg,sub_nonneg.mprhave hmin (a b : ℚ) : 2 * min a b = a + b - |a-b| := by rcases le_total a b with h | h · rw [min_eq_left h, abs_of_nonpos (sub_nonpos.mpr h)] ring · rw [min_eq_right h, abs_of_nonneg (sub_nonneg.mpr h)] ring
At least one of the two partitions satisfies m/6 ≤ min(cut₁, cut₂), where m is the edge count of G.
Assume for contradiction that both min(x, y) < m/6 and min(u, v) < m/6. Then 2 * min(x, y) + 2 * min(u, v) < 2 * (m/3). Using the identity from the previous step, this sum equals (x + y + u + v) - (|x - y| + |u - v|). Since the total crossing edges satisfy x + y + u + v ≥ m and the total imbalance satisfies |x - y| + |u - v| ≤ m/3, the sum must be at least m - m/3 = 2m/3, producing a contradiction via linear arithmetic (linarith).
have hgood : (digraph_edge_count G : ℚ) / 6 ≤ min x y ∨ (digraph_edge_count G : ℚ) / 6 ≤ min u v := by by_contra h push_neg at h have h₀ := hmin x y have h₁ := hmin u v change (digraph_edge_count G : ℚ) ≤ x+y+u+v at htotal change |x-y| + |u-v| ≤ (digraph_edge_count G : ℚ)/3 at hbalance linarith
There exists a vertex partition with both directed cut counts at least ⌈m/6⌉₊.
Case split on which partition achieves the lower bound. If m/6 ≤ min(x, y), choose A₀; since the minimum is bounded above by each component (min_le_left, min_le_right), m/6 ≤ x and m/6 ≤ y, so by the ceiling property (Nat.ceil_le.mpr), ⌈m/6⌉₊ ≤ x and ⌈m/6⌉₊ ≤ y. If instead m/6 ≤ min(u, v), the identical argument applied to A₁ shows both u and v are at least ⌈m/6⌉₊.
uses
Nat.ceil_le.mpr,min_le_left,min_le_rightrcases hgood with h | h · refine ⟨A₀, Nat.ceil_le.mpr ?_, Nat.ceil_le.mpr ?_⟩ · exact h.trans (min_le_left x y) · exact h.trans (min_le_right x y) · refine ⟨A₁, Nat.ceil_le.mpr ?_, Nat.ceil_le.mpr ?_⟩ · exact h.trans (min_le_left u v) · exact h.trans (min_le_right u v)
le_total- In a linear order, any two elements are comparable: a ≤ b or b ≤ a.
min_eq_left- If a ≤ b, then min(a, b) = a.
abs_of_nonpos- If a ≤ 0, then |a| = -a.
sub_nonpos.mpr- If a ≤ b, then a - b ≤ 0.
min_eq_right- If b ≤ a, then min(a, b) = b.
abs_of_nonneg- If 0 ≤ a, then |a| = a.
sub_nonneg.mpr- If b ≤ a, then 0 ≤ a - b.
Nat.ceil_le.mpr- For a rational q and a natural number n, if q ≤ n then ⌈q⌉₊ ≤ n.
min_le_left- For any elements a and b, min(a, b) ≤ a.
min_le_right- For any elements a and b, min(a, b) ≤ b.
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.
theorem digraph_both_cuts_ge_ceil_div_six_of_two_partitions {V : Type*} [Fintype V] [DecidableEq V] (G : Digraph V) [DecidableRel G.Adj] (A₀ A₁ : Finset V) (htotal : (digraph_edge_count G : ℚ) ≤ (digraph_cut_count G A₀ A₀ᶜ : ℚ) + digraph_cut_count G A₀ᶜ A₀ + digraph_cut_count G A₁ A₁ᶜ + digraph_cut_count G A₁ᶜ A₁) (hbalance : |(digraph_cut_count G A₀ A₀ᶜ : ℚ) - digraph_cut_count G A₀ᶜ A₀| + |(digraph_cut_count G A₁ A₁ᶜ : ℚ) - digraph_cut_count G A₁ᶜ A₁| ≤ (digraph_edge_count G : ℚ) / 3) : ∃ A : Finset V, ⌈(digraph_edge_count G : ℚ) / 6⌉₊ ≤ digraph_cut_count G A Aᶜ ∧ ⌈(digraph_edge_count G : ℚ) / 6⌉₊ ≤ digraph_cut_count G Aᶜ A := by let x : ℚ := digraph_cut_count G A₀ A₀ᶜ let y : ℚ := digraph_cut_count G A₀ᶜ A₀ let u : ℚ := digraph_cut_count G A₁ A₁ᶜ let v : ℚ := digraph_cut_count G A₁ᶜ A₁ have hmin (a b : ℚ) : 2 * min a b = a + b - |a-b| := by rcases le_total a b with h | h · rw [min_eq_left h, abs_of_nonpos (sub_nonpos.mpr h)] ring · rw [min_eq_right h, abs_of_nonneg (sub_nonneg.mpr h)] ring have hgood : (digraph_edge_count G : ℚ) / 6 ≤ min x y ∨ (digraph_edge_count G : ℚ) / 6 ≤ min u v := by by_contra h push_neg at h have h₀ := hmin x y have h₁ := hmin u v change (digraph_edge_count G : ℚ) ≤ x+y+u+v at htotal change |x-y| + |u-v| ≤ (digraph_edge_count G : ℚ)/3 at hbalance linarith rcases hgood with h | h · refine ⟨A₀, Nat.ceil_le.mpr ?_, Nat.ceil_le.mpr ?_⟩ · exact h.trans (min_le_left x y) · exact h.trans (min_le_right x y) · refine ⟨A₁, Nat.ceil_le.mpr ?_, Nat.ceil_le.mpr ?_⟩ · exact h.trans (min_le_left u v) · exact h.trans (min_le_right u v)