OctoInformBeta

OpenAI preprint, September 2026 · §3. Routing with team constraints · §3

Lemma 3.1: A graph whose cut expansion is large against endpoint loads, team sizes and forbidden sets routes all demands at once

Short edge-disjoint routing in an expander under team constraints.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Let PP be a graph of order rr whose cut expansion is at least a real number h>0h > 0, so that every vertex set UU has at least hmin⁡{|U|,r−|U|}h \min\{|U|, r - |U|\} edges leaving it, and let (xi,yi)i∈I(x_i, y_i)_{i \in I} be a finite family of demands, pairs of distinct vertices of PP to be joined by paths. Routing in expanders asks for paths QiQ_i from xix_i to yiy_i, one for each demand, that are short and pairwise edge-disjoint. Lemma 3.1 of the preprint imposes two further constraints: each demand ii comes with a set ZiZ_i of forbidden vertices that QiQ_i must avoid except at its ends, and the demands are grouped into teams whose paths share no internal vertex. The question is how large hh 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 PP on a finite vertex set VV of order rr has cut expansion at least a real number hh if every set U⊆VU \subseteq V satisfies |∂PU|≥hmin⁡{|U|,r−|U|},|\partial_P U| \ge h \min\{|U|,\, r - |U|\},(1)✦ where |∂PU||\partial_P U| is the number of edges of PP with one end in UU and the other in V\UV \setminus U.

The endpoint load of a vertex vv of PP with respect to a set A⊆IA \subseteq I of demands is the number of demands i∈Ai \in A with xi=vx_i = v or yi=vy_i = v.✦

The interior of a walk WW in PP from ss to tt is the set of vertices of WW other than ss and tt.✦

The Length Bound

Logarithms are to base 22, and ⌈t⌉\lceil t \rceil is the least nonnegative integer at least tt. For real numbers rr and hh, the routing parameter is the integer g(r,h)=⌈8rhlog⁡(2r)⌉,g(r,h) = \Bigl\lceil 8\,\frac{r}{h}\,\log(2r) \Bigr\rceil,(2)✦ the routing depth of rr is the integer d(r)=⌈log⁡r⌉,d(r) = \lceil \log r \rceil,(3)✦ and the routing length bound is the integer ℓ(r,h)=2g(r,h)(1+d(r)).\ell(r,h) = 2\, g(r,h)\, \bigl(1 + d(r)\bigr).(4)✦

The Claim

Theorem 1. Let PP be a graph of order r≥2r \ge 2 whose cut expansion is at least a real number h>0h > 0, and let ℓ=ℓ(r,h)\ell = \ell(r,h) be the routing length bound (4). Let (xi,yi)i∈I(x_i, y_i)_{i \in I} be a finite family of demands in PP, pairs of distinct vertices, partitioned into teams, and for each i∈Ii \in I let ZiZ_i be a set of vertices of PP. Let k≥1k \ge 1, b≥1b \ge 1 and z≥0z \ge 0 be real numbers such that every vertex of PP has endpoint load at most kk with respect to II, every team has at most bb demands, and |Zi|≤z|Z_i| \le z for every i∈Ii \in I. If h≥64(ℓ2(k+b)+z),h \ge 64\bigl(\ell^2 (k + b) + z\bigr),(5)✦ then there are paths QiQ_i in PP from xix_i to yiy_i, one for each i∈Ii \in I, such that each QiQ_i has length at most ℓ\ell and its interior is disjoint from ZiZ_i; for distinct i,j∈Ii, j \in I the paths QiQ_i and QjQ_j have no edge in common; and if moreover ii and jj are in the same team, the interiors of QiQ_i and QjQ_j 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).