§2.1, pp. 794–795 — on a 3-regular c-expander the uniform max-flow is f ≤ 6𝒮/(c(⌊log n⌋ − 2))
ProvedLeightonRao.BadExample.flow_le_of_expanderLet be a 3-regular graph on nodes with unit edge capacities, and suppose that for a constant
Write for , and let and be the max-flow and the min-cut of the uniform multicommodity flow problem on . Then
Since is the min-cut and always holds, this shows that on bounded-degree expanders the max-flow is a factor smaller than the min-cut, so the gap of Theorem 2 is tight.
Formalization Note The paper's display has ; the argument (a ball of radius in a 3-regular graph has fewer than nodes) proves the bound with , which is what is stated: the same , a different constant. The hypothesis makes . Commodities are ordered pairs of demand (footnote 2, p. 791); the min-cut ranges over nonempty proper cuts; the max-flow is the supremum of feasible concurrent fractions.
import Mathlib import Definitions.Def_LeightonRao_BadExample_Setting set_option autoImplicit false open scoped BigOperators
namespace LeightonRao.BadExample
/-- §2.1 display, pp. 794–795: on a 3-regular `n`-node graph with unit capacities and
`|⟨U, Ū⟩| ≥ c min{|U|, |Ū|}` for all `U`, with `n ≥ 8`, the uniform max-flow satisfies
`f ≤ 6𝒮/(c(⌊log₂ n⌋ − 2))`. -/
theorem flow_le_of_expander {V : Type} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) [DecidableRel G.Adj]
(h3 : G.IsRegularOfDegree 3)
(c : ℝ) (hc : 0 < c) (hexp : IsEdgeExpander G c)
(hn : 8 ≤ Fintype.card V) :
maxFlow (unitNetwork G) uniformDemand ≤
6 * minCut (unitNetwork G) /
(c * ((Nat.log 2 (Fintype.card V) : ℝ) - 2)) := by sorry
end LeightonRao.BadExample
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.