§2.1, pp. 794–795 — the uniform max-flow on a 3-regular unit-capacity graph is f ≤ 6/((n − 1)(⌊log n⌋ − 2))
ProvedLeightonRao.BadExample.max_flow_leconcurrent-flowmulticommodity-flowp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1regular-graph
Let be a 3-regular graph on nodes with unit edge capacities, and write for . The max-flow of the uniform multicommodity flow problem on satisfies
Together with the lower bound on the min-cut of an expander, this gives the gap of the example.
Formalization Note The max-flow is the supremum of the feasible concurrent fractions. The paper's is stated with the floor (printed slip; the argument proves the floor version), and makes it at least . The text just before the argument says "at most "; the display, which is what is formalized, has .
Preamble
import Mathlib import Definitions.Def_LeightonRao_BadExample_Setting set_option autoImplicit false open scoped BigOperators
Formal statement
namespace LeightonRao.BadExample
/-- §2.1, pp. 794–795: the uniform max-flow of a 3-regular unit-capacity network with
`n ≥ 8` nodes is at most `3n/((n choose 2)(⌊log₂ n⌋ − 2)) = 6/((n − 1)(⌊log₂ n⌋ − 2))`. -/
theorem max_flow_le {V : Type} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) [DecidableRel G.Adj]
(h3 : G.IsRegularOfDegree 3)
(hn : 8 ≤ Fintype.card V) :
maxFlow (unitNetwork G) uniformDemand ≤
6 / (((Fintype.card V : ℝ) - 1) * ((Nat.log 2 (Fintype.card V) : ℝ) - 2)) := 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), pp. 794–795, §2.1, final display, first two lines
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.