The Setting
Let be a graph of order whose cut expansion is at least a real number , so that every vertex set has at least edges leaving it, and let be a finite family of demands, pairs of distinct vertices of to be joined by paths. Routing in expanders asks for paths from to , one for each demand, that are short and pairwise edge-disjoint. Lemma 3.1 of the preprint imposes two further constraints: each demand comes with a set of forbidden vertices that must avoid except at its ends, and the demands are grouped into teams whose paths share no internal vertex. The question is how large must be, against the number of demands ending at a vertex, the size of a team and the size of a forbidden set, for all demands to be routed at once.
Expansion, Endpoint Loads and Interiors
A graph on a finite vertex set of order has cut expansion at least a real number if every set satisfies (1)✦ where is the number of edges of with one end in and the other in .
The endpoint load of a vertex of with respect to a set of demands is the number of demands with or .✦
The interior of a walk in from to is the set of vertices of other than and .✦
The Length Bound
Logarithms are to base , and is the least nonnegative integer at least . For real numbers and , the routing parameter is the integer (2)✦ the routing depth of is the integer (3)✦ and the routing length bound is the integer (4)✦
The Claim
Theorem 1. Let be a graph of order whose cut expansion is at least a real number , and let be the routing length bound (4). Let be a finite family of demands in , pairs of distinct vertices, partitioned into teams, and for each let be a set of vertices of . Let , and be real numbers such that every vertex of has endpoint load at most with respect to , every team has at most demands, and for every . If (5)✦ then there are paths in from to , one for each , such that each has length at most and its interior is disjoint from ; for distinct the paths and have no edge in common; and if moreover and are in the same team, the interiors of and are disjoint.
What Is Checked
The claim (5) is stated over the cut expansion (1) of a graph, the endpoint load of a vertex, the interior of a path, and the routing length bound (4), built from the routing parameter (2) and the routing depth (3).