Introduction
Motivation
The cops-and-robbers game is a pursuit-evasion game on a graph in which k cops attempt to capture a single robber. The minimum k for which the cops have a winning strategy is the cop number c(G). Meyniel’s conjecture (Frankl, 1987) asserts that c(G) = O(\sqrt{n}) for every connected graph on n vertices, and remains the central open problem in the area. The current best upper bound is c(G) \leq n / 2^{(1-o(1))\sqrt{\log n}} (Lu–Peng; Scott–Sudakov; Frieze–Krivelevich–Loh).
A natural approach toward Meyniel’s conjecture, in the spirit of Prałat–Wormald’s resolution for random graphs and recent partial progress on expanders and high-girth graphs[1,2], is to combine random cop placement with a deterministic local chase. The bottleneck of this approach is the local team-chase problem: assuming several cops have been placed within a small distance r of the robber, can they coordinate their gradient-descent moves to capture the robber within O(r \log n) rounds?
In high-girth regular graphs, where the local geometry is tree-like, the difficulty of this problem is structural: a single cop is always evaded (Aigner–Fromme), so capture requires multi-cop coordination, and the right coordination invariant is not obvious. In this paper, we work in the cleanest possible local geometry — a d-regular tree-ball — and identify the right invariant, prove that it works for one round, prove that it generalizes to t rounds, and prove a matching barrier.
Setup
Throughout, G denotes a d-regular graph with d \geq 3. We fix a vertex v_0 \in V(G) and a radius R \geq 1. The fundamental hypothesis is:
Definition 1.1 Tree-ball
The ball B_R(v_0) is a tree-ball if the induced subgraph on B_R(v_0) is a tree. Equivalently, \mathrm{girth}(G) > 2R.
In a tree-ball, v_0 has d children (its neighbors), and every interior vertex has exactly one parent and d-1 children. We write S_j(v) = \{x : \operatorname{dist}(x, v) = j\} for the depth-j shell at v.
Definition 1.2 Geodesic cone
For v \in V(G) with B_r(v) a tree-ball and u \in N(v), the geodesic cone through u at radius r is
C_u(v, r) := \{x \in B_r(v) \setminus \{v\} : \text{the unique geodesic from } x \text{ to } v \text{ has penultimate vertex } u\}.
The truncated cone at depth \geq k is
C_u^{\geq k}(v, r) := \{x \in C_u(v, r) : \operatorname{dist}(x, v) \geq k\}.
Definition 1.3 Path tube
For v_0 \in V(G) with B_R(v_0) a tree-ball, and a nonbacktracking path \sigma = (v_0, v_1, \ldots, v_t) from v_0, and a depth threshold k, the t-tube at depth \geq k is
\begin{gathered} T_\sigma^{\geq k}(R) := \bigl\{x \in B_R(v_0) : \operatorname{dist}(x, v_0) \geq k, \\ \text{the unique geodesic from } x \text{ to } v_0 \text{ visits } v_t, v_{t-1}, \ldots, v_1 \text{ in order}\bigr\}. \end{gathered}
The cops execute gradient descent: at each cop turn, every cop moves to a neighbor minimizing distance to the current robber position, breaking ties by an arbitrary rule (deterministic or randomized). The order of play is: cops move, then robber moves. A robber move to w \in N(v(t)) is safe if no cop occupies w at the start of the robber’s turn (i.e., after the cops’ move).
For the robber’s position v and a neighbor u' \in N(v), we say a cop c contributes to branch u' at v if c \neq v and the geodesic from c to v has penultimate vertex u'. The branch-load support at v is the set of u' \in N(v) that receive at least one contributing cop.
Results
The paper has four main results, prefaced by a sharp counting lemma.
Lemma 1.4 Sharp shell and cone counts
Let G be d-regular with d \geq 3, and suppose B_r(v) is a tree-ball. Then for every u \in N(v) and 1 \leq j \leq r,
|C_u(v, r) \cap S_j(v)| = (d-1)^{j-1}, \qquad |S_j(v)| = d(d-1)^{j-1}.
Hence
|C_u(v, r)| = \sum_{j=1}^{r} (d-1)^{j-1} = \frac{(d-1)^r - 1}{d-2}, \quad |B_r(v)| = 1 + d \cdot \frac{(d-1)^r - 1}{d - 2}.
For the truncated cone,
|C_u^{\geq k}(v, r)| = \sum_{j=k}^{r} (d-1)^{j-1}, \quad 1 \leq k \leq r.
The first main result is a probabilistic deep-load corollary.
Corollary 1.5 Deep-load occupancy
Let G be d-regular with B_r(v) a tree-ball, and let X_1, \ldots, X_m be i.i.d. uniform samples from B_r(v). Set
p_{d,r}^{\geq k} := \frac{|C_u^{\geq k}(v, r)|}{|B_r(v)|},
which by Lemma 1.4 does not depend on the choice of u \in N(v), since all branches in a tree-ball have equal size. Then
\Pr[\exists u \in N(v): C_u^{\geq k}(v, r) \text{ receives no sample}] \leq d \cdot (1 - p_{d,r}^{\geq k})^m.
The second is the universal t-round persistence theorem with the correct depth budget.
Theorem 1.6 Universal t-round deep-load persistence
Let G be d-regular with d \geq 3, v_0 \in V(G), and assume B_R(v_0) is a tree-ball for some R \geq 2t+1. Suppose that for every nonbacktracking path \sigma = (v_0, v_1, \ldots, v_t) of length t from v_0, there exists at least one cop in T_\sigma^{\geq 2t+1}(R).
Then for every nonbacktracking robber path (v_0, v_1, \ldots, v_t) and every s \in \{1, \ldots, t\}, after the cops’ gradient-descent step at round s, exactly one of the following holds:
- (a) a cop occupies v_s, so the robber’s intended move to v_s is illegal; or
- (b) the move to v_s is legal, and after the robber moves to v_s, the branch-load support at v_s has size at least 2.
The third is the sampling barrier.
Theorem 1.7 Barrier on branch-tube certificates
Fix d \geq 3. In the d-regular tree-ball model, any argument that places m cops by uniform sampling from B_R(v_0) and relies on occupancy of every length-t deep tube T_\sigma^{\geq 2t+1}(R) requires
m = \Omega\!\left((d-1)^{t-1} \cdot t\right)
cops. In particular, for m = \mathrm{polylog}(n) and fixed d, this method certifies only t = O(\log\log n) rounds, not t = \Theta(\log n).
The fourth is a complementary degeneration barrier showing that bounded-order compressions of the path-tube data are themselves insufficient. Theorem 4.6 (stated and proved in Section 4.5) constructs, for every r \geq 1, two cop configurations X and Y that agree on all order-r tube data but differ in their post-(r+1)-round branch-load support: X has support \geq 2 while Y has support exactly 1. Hence no certificate depending only on order-r data can certify universal (r+1)-round persistence.
Strategic significance
Theorems 1.6, 1.7, and 4.6 together capture the precise reach of branch-tube methods. The natural iteration of the one-round argument extends to t rounds with the correct depth budget 2t+1 (Theorem 1.6), but the path-entropy cost is exponential in t (Theorem 1.7), and any compression to bounded-order data fails dynamically (Theorem 4.6). Together, the two barriers tighten this trade-off: certifying t-round persistence by an order-r local invariant requires r \geq t, and order-t resolution requires \Omega((d-1)^{t-1}) cops to occupy.
The barriers rule out a substantial family of proof techniques but are silent on what could replace them. The pivots in Section 5 sketch the most natural escape routes: epoch refresh (which probably needs a global progress measure to succeed), soft potentials that necessarily break locality or symmetry, and a non-local spectral approach via nonbacktracking-walk concentration.
Sharp Counts
Proof of Lemma 1.4
Since B_r(v) is a tree-ball and G is d-regular, v has exactly d children in the rooted tree (one per neighbor in N(v)), and every non-root vertex at depth < r has exactly d-1 children. Fix u \in N(v). The branch rooted at u is a (d-1)-ary rooted tree of depth r - 1; its level j-1 has (d-1)^{j-1} vertices, so the depth-j shell of the branch (relative to v) has (d-1)^{j-1} vertices.
Hence |C_u(v, r) \cap S_j(v)| = (d-1)^{j-1} for 1 \leq j \leq r. Summing over the d branches gives |S_j(v)| = d(d-1)^{j-1}, and summing j from 1 to r gives the cone size. Including v itself yields the ball size, and restricting j \geq k yields the truncated cone count. □
Remark 2.1 Asymptotic branch ratio
The ratio |C_u^{\geq k}(v, r)| / |B_r(v)| tends to 1/d as r \to \infty for fixed k. Thus each branch asymptotically owns a 1/d fraction of the ball, and depth-k truncation costs only O(d^k) vertices out of \Theta(d^r), which is negligible at large r.
Proof of Corollary 1.5
For a fixed branch u \in N(v), the probability that no X_i lies in C_u^{\geq k}(v, r) is (1 - p_{d,r}^{\geq k})^m. Union bounding over the d choices of u gives the claim. □
For k = 3 and r large, p_{d,r}^{\geq 3} \to 1/d - O(d^{-r}), so m = \Theta(d \log d) samples suffice to hit every truncated branch with high probability. For fixed d, m = O(\log n) drives the failure probability polynomially small in n.
One-Round and t-Round Persistence
The one-round case
We first prove the case t = 1 separately, both for clarity and because the argument is the model for the multi-round induction. Lemma 3.1 below is the t = 1 specialization of Theorem 1.6, presented here in self-contained form.
Lemma 3.1 One-round persistence
Let G be d-regular with d \geq 3, v_0 \in V(G), and assume B_3(v_0) is a tree-ball. Suppose that for every u \in N(v_0), there is at least one cop in C_u^{\geq 3}(v_0, R) for some R \geq 3.
Then for every w \in N(v_0), after the cop gradient-descent step, exactly one of the following holds:
- (a) a cop occupies w, so the robber’s intended move to w is illegal; or
- (b) the move to w is legal, and after the robber moves to w, the branch-load support at w has size at least 2.
Fix w \in N(v_0). After the cop gradient-descent step, if some cop occupies w then case (a) holds and we are done. Otherwise we exhibit both a descendant witness and a parent witness at w, establishing case (b).
Descendant witness. By hypothesis there is a cop c^\downarrow \in C_w^{\geq 3}(v_0, R). Then \operatorname{dist}(c^\downarrow, v_0) = j \geq 3 with the geodesic from c^\downarrow to v_0 passing through w. Gradient descent toward v_0 moves c^\downarrow to its parent in the tree rooted at v_0, which is at depth j - 1 \geq 2, still in the w-subtree. After this move, c^\downarrow is at distance j - 1 - 1 = j - 2 \geq 1 from w. The geodesic from this new position to w passes through some child of w in the tree, so c^\downarrow contributes to a descendant branch at w.
Parent witness. Pick u \in N(v_0) with u \neq w (possible since d \geq 3 \geq 2). By hypothesis there is a cop c^\uparrow \in C_u^{\geq 3}(v_0, R). After gradient descent, c^\uparrow remains in the u-subtree at depth \geq 2 from v_0. Relative to w, the geodesic from c^\uparrow to w passes through v_0 (the unique tree path between distinct subtrees), so c^\uparrow contributes to the parent branch at w through v_0.
Combining witnesses. The descendant and parent witnesses lie in distinct branches at w, so the branch-load support at w has size at least 2, establishing case (b). □
Proof of Theorem 1.6
We now extend the one-round argument to general t, with depth budget 2t+1. The reason this budget is necessary, not merely sufficient, is illustrated in the sharpness remark of Section 3.3.
Fix any nonbacktracking robber path (v_0, v_1, \ldots, v_t) and any s \in \{1, \ldots, t\}. We analyze round s on the assumption that no cop landed on v_{s'} during the round-s' gradient-descent step, for each 1 \leq s' < s; otherwise case (a) holds at the first such s', establishing the dichotomy there. Under this assumption the robber is at v_{s-1} at the start of round s. After the cops’ gradient-descent step, if some cop occupies v_s then case (a) holds and we are done. Otherwise we exhibit both a descendant-branch witness and a parent-branch witness at v_s, establishing case (b).
Descendant witness at v_s. Let \sigma_s = (v_0, v_1, \ldots, v_s) be the robber’s trajectory through time s. Extend \sigma_s to any nonbacktracking length-t path \sigma (e.g., by appending t - s steps in any nonbacktracking way). By hypothesis there is a cop c_\sigma^\downarrow \in T_\sigma^{\geq 2t+1}(R) with initial depth j_0 \geq 2t+1, and the unique geodesic from c_\sigma^\downarrow to v_0 visits v_t, v_{t-1}, \ldots, v_1 in order.
In a tree-ball, gradient descent toward any vertex on the cop’s geodesic to v_0 is forced: the unique distance-decreasing neighbor is the cop’s parent in the v_0-rooted tree. Therefore each round the cop moves exactly one step upward along its geodesic to v_0. After s rounds, the cop has moved s steps up its geodesic to v_0, so its current geodesic to v_0 visits v_s, v_{s-1}, \ldots, v_1 in order, and its depth from v_0 is j_0 - s.
Since j_0 \geq 2t+1 and s \leq t, we have j_0 - s \geq t + 1 > s, so the cop remains strictly below v_s: it is in the v_s-subtree at depth \geq s + 1 from v_0, equivalently at distance \geq 1 from v_s within that subtree. Hence the geodesic from the cop’s current position to v_s has penultimate vertex equal to some child of v_s, and the cop contributes to a descendant branch at v_s.
Parent witness at v_s. Choose any neighbor u_0 \in N(v_0) with u_0 \neq v_1 (possible since d \geq 3). Extend u_0 to any nonbacktracking length-t path \sigma' = (v_0, u_0, \ldots). By hypothesis there is a cop c^\uparrow \in T_{\sigma'}^{\geq 2t+1}(R).
Initially c^\uparrow is in the u_0-subtree at depth \geq 2t+1. At round 1, gradient descent toward v_0 moves c^\uparrow to depth 2t, still in the u_0-subtree. At round 2, gradient descent toward v_1 has target in a different subtree from c^\uparrow, so the cop’s geodesic to v_1 goes up through v_0. The unique distance-decreasing neighbor is the cop’s parent in the v_0-rooted tree, so the cop moves to depth 2t - 1, still in the u_0-subtree. The same argument applies at every round k with 1 \leq k \leq s: from the cop’s position in the u_0-subtree at depth 2t + 2 - k, the robber’s current position v_{k-1} is reached only via v_0 (since u_0 \neq v_1), so the unique distance-decreasing direction is up to the parent.
By induction, after s rounds, c^\uparrow is at depth 2t + 1 - s from v_0, still in the u_0-subtree. Since u_0 \neq v_1, the entire u_0-subtree is disjoint from the v_1-subtree, and since each v_j for j \geq 1 lies in the v_1-subtree, the cop c^\uparrow at depth 2t + 1 - s \geq t + 1 \geq 1 from v_0 in the u_0-subtree is on the parent side of v_s. For s \geq 1, the geodesic from c^\uparrow to v_s passes through v_0, so the penultimate vertex of that geodesic (the one adjacent to v_s) is v_{s-1}. So c^\uparrow contributes to the parent branch of v_s through v_{s-1}.
Combining witnesses. The descendant witness contributes to a non-parent branch at v_s, and the parent witness contributes to the parent branch at v_s. These are distinct branches, so the branch-load support at v_s is at least 2, establishing case (b). □
The depth budget is sharp
The hypothesis j_0 \geq 2t + 1 in Theorem 1.6 is necessary, not merely sufficient. We illustrate.
Remark 3.2 Sharpness of the depth budget
Consider j_0 = 2t. After s = t rounds, the cop is at depth j_0 - t = t from v_0, with the robber at v_t (also depth t). The cop’s geodesic to v_0 contains v_t, v_{t-1}, \ldots, v_1, so the cop is at v_t itself, not at a strict descendant. This blocks the robber’s move (case (a)) but does not provide a descendant branch at v_t for the post-move analysis. Reducing further to j_0 < 2t would place the cop on an ancestor of v_t, and the cop would contribute to the parent branch only — destroying the support-2 claim.
The Barrier
Tube density
Lemma 4.1 Asymptotic tube density
For fixed d \geq 3 and a length-t nonbacktracking prefix \sigma in a d-regular tree-ball B_R(v_0) with R \geq 2t+1,
|T_\sigma^{\geq 2t+1}(R)| = \sum_{j = 2t+1}^{R} (d-1)^{j-t} = \sum_{\ell = t+1}^{R-t} (d-1)^\ell = (d-1)^{t+1} \cdot \frac{(d-1)^{R-2t} - 1}{d - 2}.
The tube density
q_t(R) := \frac{|T_\sigma^{\geq 2t+1}(R)|}{|B_R(v_0)|}
satisfies, as R \to \infty,
q_t(R) \to \frac{1}{d (d-1)^{t-1}}.
Each vertex in T_\sigma^{\geq 2t+1}(R) \cap S_j(v_0) is a descendant of v_t at depth j from v_0, hence at depth j - t within the v_t-rooted subtree. The latter is a (d-1)-ary tree (since v_t has d - 1 children in the tree-ball), so its depth-(j - t) shell has (d-1)^{j-t} vertices for j \geq t + 1. Restricting to j \geq 2t + 1, summing, and substituting \ell = j - t gives the closed form above.
For the asymptotic density: both |T_\sigma^{\geq 2t+1}(R)| and |B_R(v_0)| are geometric sums dominated by their top shells. The top shell of the tube at j = R has (d-1)^{R-t} vertices; the top shell of the ball at j = R has d(d-1)^{R-1} vertices. Hence the ratio tends to
\frac{(d-1)^{R-t}}{d(d-1)^{R-1}} = \frac{1}{d(d-1)^{t-1}},
as claimed. □
Number of length-t prefixes
Lemma 4.2 Number of length-t prefixes
The number of nonbacktracking length-t paths from v_0 in a d-regular tree-ball is
N_t = d(d-1)^{t-1}.
The first step has d choices (any neighbor of v_0). Each subsequent step has d - 1 choices (any neighbor of the current vertex except the immediately previous one). So N_t = d(d-1)^{t-1}. □
Proof of Theorem 1.7
Suppose m cops are sampled i.i.d. uniformly from B_R(v_0), and the proof relies on every length-t tube being occupied. By Lemma 4.1, for each fixed prefix \sigma,
\Pr\!\left[T_\sigma^{\geq 2t+1}(R) \text{ is empty}\right] = (1 - q_t(R))^m \leq \exp(-m \cdot q_t(R)).
Union bounding over the N_t prefixes,
\Pr[\exists \sigma : T_\sigma \text{ empty}] \leq N_t \cdot \exp(-m \cdot q_t(R)).
For this to be o(1), we require
m \geq \frac{\log N_t + \omega(1)}{q_t(R)}.
Using N_t = d(d-1)^{t-1} and q_t(R) \sim 1/[d(d-1)^{t-1}] from Lemmas 4.2 and 4.1,
m \gtrsim d(d-1)^{t-1} \cdot \log\!\bigl[d(d-1)^{t-1}\bigr].
For fixed d, this is m = \Omega((d-1)^{t-1} \cdot t).
Inverting. Suppose m = \mathrm{polylog}(n). From (d-1)^{t-1} \leq m, taking logarithms gives
t - 1 \leq \frac{\log m}{\log(d-1)} = \frac{O(\log\log n)}{\log(d-1)},
so t = O(\log\log n).
In particular, the certificate cannot certify t = \Theta(\log n) rounds with m = \mathrm{polylog}(n) cops. To certify t = \Theta(\log n) rounds, the certificate requires m = (d-1)^{\Theta(\log n)} \cdot \Theta(\log n) = n^{\Theta(\log(d-1))} \cdot \Theta(\log n) cops, which is polynomial in n with exponent depending on d. □
What the barrier says, precisely
The barrier rules out a specific proof technique: it does not say that the \Theta(\log n)-round local team-chase is impossible, only that it cannot be obtained by occupying every length-t deep tube uniformly. The barrier identifies the cost as exponential in t, with the exponent base d - 1 — the local branching factor of the tree-ball.
Remark 4.3 Robustness of the barrier
The barrier is robust to mild relaxations of the certificate. For example, requiring most (rather than all) tubes to be occupied still requires \Omega((d-1)^{t-1}) cops in expectation: the expected number of empty tubes is N_t (1 - q_t)^m, and bounding this even by 1 gives m \geq \log N_t / q_t, which is the same order. Similarly, weakening the depth threshold from 2t + 1 to any \Theta(t) does not change the exponential dependence on t, only the constant in the exponent.
A finite-order potential-degeneration barrier
Theorem 1.7 shows that occupying every length-t deep tube is exponentially expensive in t under uniform local sampling. A natural response is to compress the local state: instead of tracking every length-t tube, one might try to use an invariant that remembers only bounded-order tube data, aggregating all information below a fixed depth. The next theorem shows that this cannot certify persistence beyond one additional round.
Definition 4.4 Order-r tube profile
Fix a rooted tree-ball B_R(v_0) in a d-regular graph. For a cop configuration X and an integer r \geq 1, the order-r tube profile of X is the family
\Pi_r(X) := \bigl\{N_X(\sigma, j)\bigr\}_{\sigma, j},
where \sigma = (v_0, v_1, \ldots, v_r) ranges over all nonbacktracking paths of length r from v_0, and j \geq r + 1, and
N_X(\sigma, j) := \#\bigl\{x \in X : \operatorname{dist}(x, v_0) = j, \text{ and the unique geodesic from } x \text{ to } v_0 \text{ begins with } \sigma\bigr\}.
Thus \Pi_r(X) records the exact depth histogram inside every length-r tube, but forgets how the mass in that tube splits below level r.
Definition 4.5 Order-r invariant
A local invariant F on cop configurations in a rooted tree-ball is order-r if it factors through \Pi_r, i.e. if F(X) = F(Y) whenever \Pi_r(X) = \Pi_r(Y). It is neighbor-symmetric if it is invariant under rooted automorphisms of the tree-ball fixing v_0.
Theorem 4.6 Finite-order potential-degeneration barrier
Fix d \geq 3 and r \geq 1. Let B_R(v_0) be a d-regular tree-ball with R \geq 2r + 3. Then there exist two cop configurations X and Y in B_R(v_0) such that:
(i) \Pi_r(X) = \Pi_r(Y); in particular, every order-r invariant takes the same value on X and Y.
(ii) There exists a nonbacktracking path
(v_0, v_1, \ldots, v_{r+1})
such that this robber path is safe in both configurations, but after r+1 rounds of cop gradient descent followed by robber motion along that path:
- in configuration X, the branch-load support at v_{r+1} has size at least 2;
- in configuration Y, the branch-load support at v_{r+1} has size exactly 1.
Consequently, no certificate whose hypotheses depend only on order-r data can correctly distinguish \geq 2-branch support from 1-branch support after r+1 rounds.
Fix any nonbacktracking path
(v_0, v_1, \ldots, v_{r+1})
inside the tree-ball. Since d \geq 3, the vertex v_{r+1} has at least two distinct children in the rooted tree. Choose two such children and call them a and b.
We now define two cop configurations, each consisting of exactly two cops, both at depth 2r + 3 from v_0.
Configuration X. Place one cop in the subtree rooted at a and one cop in the subtree rooted at b, both at total depth 2r + 3 from v_0.
Configuration Y. Place both cops in the subtree rooted at a, at distinct vertices, again at total depth 2r + 3 from v_0. (Since the depth-(r+1) shell of the a-subtree has (d-1)^{r+1} \geq 2 vertices, this is possible.)
In both configurations, every cop lies in the same length-r tube determined by the prefix
\sigma_0 = (v_0, v_1, \ldots, v_r),
and every cop lies at the same total depth 2r + 3 from v_0. Therefore the order-r tube counts are identical:
N_X(\sigma_0, 2r+3) = N_Y(\sigma_0, 2r+3) = 2,
and N_X(\sigma, j) = N_Y(\sigma, j) = 0 for all other (\sigma, j). Hence \Pi_r(X) = \Pi_r(Y). The order-r invariant cannot see how the two cops in \sigma_0 split between the children a and b of v_{r+1}.
Now consider the robber path
(v_0, v_1, \ldots, v_{r+1}).
We claim it is safe in both configurations. Each cop starts at depth 2r + 3 from v_0. In a tree-ball, gradient descent toward any robber position on the cop’s geodesic to v_0 is forced: each round the cop moves exactly one step upward toward v_0. Hence after s rounds, each cop is at depth 2r + 3 - s from v_0. After the cop’s move at round s, the robber moves v_{s-1} \to v_s. The cop’s distance to the robber’s destination v_s is
(2r + 3 - s) - s = 2r + 3 - 2s.
For every 1 \leq s \leq r + 1 this is at least 1, so no cop ever lands on v_s during these r + 1 rounds. Thus the robber path is safe in both configurations.
Finally, inspect the cop locations after r + 1 rounds. Each cop has moved upward by exactly r + 1 steps, so each is now at depth
2r + 3 - (r + 1) = r + 2
from v_0, while v_{r+1} has depth r + 1. Hence each cop is now a child of v_{r+1}.
In configuration X, the two cops lie on two distinct children of v_{r+1}, namely a and b. Therefore the branch-load support at v_{r+1} has size at least 2.
In configuration Y, both cops climbed within the a-subtree and now sit on its root, namely a itself (since gradient descent in a tree-ball is forced upward). Therefore both cops contribute to the same branch at v_{r+1}, and the branch-load support has size exactly 1.
This proves (ii). Since \Pi_r(X) = \Pi_r(Y) but the outcomes differ, no certificate depending only on order-r data can correctly classify both configurations. □
Corollary 4.7 First-order data is insufficient
Any invariant depending only on first-level branch data, even with exact depth histograms inside each first-level branch, cannot certify universal 2-round persistence in the tree-ball model.
Take r = 1 in Theorem 4.6. □
Remark 4.8 Complementarity of the two barriers
Theorems 1.7 and 4.6 are complementary. Theorem 1.7 shows that full order-t path information is sufficient but exponentially expensive to certify by uniform random local sampling. Theorem 4.6 shows that any bounded-order compression of that information is dynamically insufficient beyond one additional round. Together they imply that, in the tree-ball model, there is no bounded-order shortcut around path entropy: certifying t-round persistence by a local invariant requires at least order-t resolution, and order-t resolution requires \Omega((d-1)^{t-1}) cops to occupy. Together they rule out order-r branch-aggregated potentials for every fixed r as a route to \Theta(\log n)-round chase from polylogarithmic cops.
Discussion: Pivots and Open Directions
The barriers of Theorems 1.7 and 4.6 together rule out a substantial family of approaches but leave several escape routes open.
Pivot A: Epoch refresh
Run epochs of length t_0 = O(\log\log n), for which the tube certificate is affordable with \mathrm{polylog}(n) cops, then re-randomize and restart. The barrier does not preclude this: it constrains a single epoch but not a sequence of epochs.
The crucial open question is whether one t_0-round epoch produces permanent progress (a coarser robber freedom parameter shrinks by a constant factor). In a tree-ball, no such parameter is obvious: the robber’s territory is unbounded by hypothesis, and after one epoch the robber can simply retreat to a fresh subtree. This suggests that epoch refresh in the pure tree-ball model is unlikely to succeed, and the program must combine the local tree-ball analysis with a global structural bound that limits the robber’s total territory.
Pivot B: Soft potentials must break locality or symmetry
Theorem 4.6 rules out any order-r potential as a route to (r+1)-round persistence. To escape the barrier via a soft potential, the potential must therefore depend on at least one of:
- Unbounded local order: information that depends on tube data of order growing with t. This re-introduces path-entropy costs and hits Theorem 1.7.
- Non-local data: information that depends on the global graph structure beyond the local tree-ball, such as cycle structure at radius > R, or spectral data of the full graph.
- Asymmetric data: information that breaks the rooted-tree symmetry, such as a fixed orientation, an external labeling, or a privileged subset of vertices not invariant under tree automorphisms.
The most promising candidate among these is the second: nonbacktracking-walk concentration of cop mass on the full graph. If cops are placed by a global averaging that respects the nonbacktracking spectrum, the resulting cop distribution at time t may concentrate on the robber’s location at exponential rate \rho(B)^{-1}, where B is the Hashimoto nonbacktracking transition matrix of the full graph. The local tree-ball view of such a placement is no longer order-r for any fixed r; it inherits global spectral information that is invisible to any local invariant. This suggests that purely local tree-ball analysis is fundamentally insufficient.
Pivot C: Hierarchical packets
Use cop packets at multiple depth scales. A packet at scale j guarantees persistence for 2^j rounds inside a tube of depth \Theta(2^j). Packets are activated sequentially, with later packets covering longer ranges. This is a multiscale variant of refresh.
A naive cost analysis is discouraging: each scale costs (d-1)^{2^j} cops by the barrier of Theorem 1.7, and at the top scale j = \log\log n this is already (d-1)^{\log n} = n^{\log_2(d-1)}, which is polynomial in n. So the straightforward hierarchical-packet scheme does not deliver polylogarithmic cop count. This matches the cost of Theorem 1.7 inverted at t = \Theta(\log n): the multi-scale scheme inherits the same fundamental cost as the single-scale scheme it tries to circumvent. To salvage the idea one would need a sub-exponential variant in which packets at scale j exploit structure (epoch refresh between scales, partial coverage of tubes, or shared cops across scales) to evade the barrier. We do not pursue this here.
Beyond the tree-ball model
The deepest limitation of the present results is the tree-ball hypothesis. Real expanders — including Ramanujan graphs of girth \Theta(\log n) — are tree-balls only up to radius \Theta(\log n), but a chase argument typically needs to reason about radii r \approx \log n / \gamma where \gamma is the spectral gap. For \gamma bounded below by a constant, these match up to constants; but for \gamma small, the chase exits the tree-ball and must contend with cycles. In the cyclic regime, the geodesic cone C_u(v, r) is no longer a clean object (vertices may have multiple shortest paths to v), and the entire branch decomposition becomes ill-defined.
A full local team-chase theorem on expanders likely requires either (i) a generalization of the present analysis to graphs with bounded but nontrivial girth, where “tubes” become equivalence classes of approximately-tree-like geodesics, or (ii) a fundamentally different invariant — spectral, fence-based, or potential-theoretic — that does not rely on tree branch decomposition at all.
Conclusion
We have proved a sharp local persistence theorem in the tree-ball model and two matching barriers: a sampling barrier showing that the natural iteration of the one-round argument is exponentially expensive in time, and a finite-order potential-degeneration barrier showing that any bounded-order compression of the path-tube certificate is dynamically insufficient. Together they tighten the trade-off: certifying t-round persistence by an order-r local invariant requires r \geq t, and order-t resolution requires \Omega((d-1)^{t-1}) cops to occupy by uniform sampling. Together, they rule out order-r branch-aggregated potentials (for any fixed r) as a route to \Theta(\log n)-round chase from polylogarithmic cops in the tree-ball model. A structural new ingredient — non-local information, broken symmetry, or escape from the tree-ball regime entirely — is required.
The four main results — deep-load occupancy, t-round persistence with depth budget 2t+1, the sampling barrier, and the finite-order potential-degeneration barrier — together with the supporting tube-counting lemma form a self-contained module that we hope will be useful as one block in any future proof of Meyniel’s conjecture via local chase arguments. The pivots in Section 5 suggest several directions in which the program could be continued, though we leave their analysis to future work.
Acknowledgments
I warmly thank Eric Jovinelly, who led me through Graph Theory at Brown and greatly assisted me in building both graph theoretic and broader mathematical skills and intuition. I also thank my peers in the Spring 2026 S02 of Graph Theory at Brown.