§2.1, p. 794 — in a 3-regular n-node graph at least half of the source–sink pairs are at distance ≥ ⌊log n⌋ − 2
ProvedLeightonRao.BadExample.half_pairs_farexpander-graphgraph-distancep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1regular-graph
Let be a 3-regular graph on nodes and write for . Then at least of the ordered pairs of nodes have graph distance
In particular at least half of the commodities of the uniform multicommodity flow problem on have a shortest source–sink path with at least edges.
This is the step that forces every routing of the uniform flow on to use long paths.
Formalization Note Pairs are counted as ordered pairs over ; a pair with has distance and is never counted, and ordered pairs give at least unordered ones. The paper's is stated with the floor , which is what the ball bound yields (a printed slip for non-integer ). Distances are extended graph distances ( across components).
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: in a 3-regular graph on `n ≥ 8` nodes, at least `n²/2` ordered pairs
`(s, t)` are at graph distance at least `⌊log₂ n⌋ − 2`. -/
theorem half_pairs_far {V : Type} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) [DecidableRel G.Adj]
(h3 : G.IsRegularOfDegree 3)
(hn : 8 ≤ Fintype.card V) :
(Fintype.card V : ℝ) ^ 2 / 2 ≤
((Finset.univ.filter (fun p : V × V =>
((Nat.log 2 (Fintype.card V) - 2 : ℕ) : ℕ∞) ≤ G.edist p.1 p.2)).card : ℝ) := 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, second paragraph after the min-cut display
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.