§2.1, p. 794 — on a c-edge-expander with unit capacities the uniform min-cut is 𝒮 ≥ c/(n − 1)
ProvedLeightonRao.BadExample.min_cut_geexpander-graphp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1sparsest-cut
Let be a graph on nodes with unit edge capacities such that, for a constant , for every . Then the min-cut of the uniform multicommodity flow problem on satisfies
This is the lower bound on the min-cut in Leighton and Rao's example of a gap between max-flow and min-cut.
Formalization Note Regularity is not needed for this inequality and is not assumed. The minimum is over nonempty proper (see the setting).
Preamble
import Mathlib import Definitions.Def_LeightonRao_BadExample_Setting set_option autoImplicit false open scoped BigOperators
Formal statement
namespace LeightonRao.BadExample
/-- §2.1, p. 794: on a graph with `|⟨U, Ū⟩| ≥ c min{|U|, |Ū|}` for all `U`, the uniform
min-cut with unit capacities is at least `c/(n − 1)`. -/
theorem min_cut_ge {V : Type} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) [DecidableRel G.Adj]
(c : ℝ) (hc : 0 < c) (hexp : IsEdgeExpander G c)
(hn : 2 ≤ Fintype.card V) :
c / ((Fintype.card V : ℝ) - 1) ≤ minCut (unitNetwork G) := by sorry
end LeightonRao.BadExample
Source
Leighton and Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, J. ACM 46 (1999), p. 794, §2.1, min-cut display
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.