Guaranteed indirect delivery: the exact maximum

18 Sep 2026

A messenger has a message at one station of a directed network. A pursuer starts elsewhere. Both see each other and take turns following an arrow or waiting, with the messenger moving first. Which source–recipient pairs can always complete delivery?

We count pairs with different endpoints and no direct arrow between them. Write I(G) for the number that are guaranteed from every permitted pursuer starting position. The central problem is to determine

and give an explicit attaining construction at every pair of resources. This means concrete rules for the vertices and arrows, or a specified composition procedure, with all parameters determined from (n,m). A certified, listed finite graph also qualifies. An existence statement, general graph search, or derandomization procedure alone does not complete this construction requirement. Isolated stations are allowed.

The classification is complete. Every feasible vertex and arrow count has an exact maximum and an explicit attaining graph. Four formulas cover every order from twelve; complete finite tables cover orders one through eleven. The construction inventory identifies the adjacency rules, specified compositions and certified listed graphs that attain the values.

Classification proofs · Paper and evidence · Lean coverage · Delivery-time companion

The rules and the counting bound

The graph is finite and directed, without loops or repeated arcs; opposite arrows are allowed. The messenger observes the pursuer's initial position and may adapt its strategy to it. Receipt wins immediately, even when the pursuer occupies the recipient. Every other collision loses, and evading forever does not count as delivery.

There are L = n(n − 1) possible arrows and h = L − m missing arrows. Each counted pair must be missing, so M(n,m) ≤ h. For n ≥ 3, the additional vertex bound is I(G) ≤ n(n − 3): a recipient with at most one predecessor can be blocked, while one with at least two has at most n − 3 eligible indirect sources.

For n ≥ 5, four consecutive arc-count regimes organize the problem. Orders one through four belong to the complete finite classification described below; the interval boundaries need not have the same order there.

The formula from twelve stations

Let F(m) = M_E(m) be the arrow-only maximum, specified below. For every n ≥ 12, write r = m − n(n − 3) in the third case:

The four sections give the attaining constructions and their proof boundaries. For smaller hosts, use the complete finite tables; the sharp threshold for the main missing-pair formula is twelve, while the dense staircase already holds from eleven.

1. Sparse budgets: fewer than 2n arrows

Here the strongest constructions use a smaller network and add isolated stations to reach the specified order. For every even budget 24 ≤ 2k < 2n,

The attaining network has k stations and two incoming and two outgoing arrows at each. Every pair can deliver. An ordinary composition proof handles every support size from 85, and complete finite certificates supply sizes 12 through 84.

For every odd budget 25 ≤ 2k + 1 < 2n,

The construction uses k + 1 stations, with precisely controlled degree exceptions. A sharper projection now applies the periodic recipe at every support size from 98; listed graphs supply sizes 13–97. The older archive through 144 is retained. These formulas also give F(2k) = k(k − 3) for every k ≥ 12 and F(2k + 1) = k(k − 3) + 2 for every k ≥ 12. The remaining arrow-only values are:

Each value is attained at every host at least as large as its least attaining host, by adding isolates. Thus M(n,22) = 79 for every n ≥ 11 and M(n,23) = 83 for every n ≥ 12. Smaller hosts have their own exact values in the finite tables. The finite sparse-budget proof combines source and sink deletion, live row and column capacities, complete degree families and independently checked literal attainers.

See the proofs of the even construction, the odd construction, the 22-arrow case, and the 23-arrow case.

2. The main interval: every missing pair can win

The whole main interval is settled from twelve stations onward:

Every budget has an explicit attaining graph. The order threshold twelve is sharp for this formula: at eleven stations and 22 arrows, the exact maximum is 79, below the 88 missing pairs. All smaller main-interval cases are settled by their finite values and attaining graphs.

The general hub composition theorem preserves the earlier larger codes and their stronger parameter ranges. Pair codes simplify the classification proof without discarding those results.

The complete missing-pair intervals at smaller orders are 24–34 arrows at eight stations, 24–54 at nine, 25–70 at ten, and 25–88 at eleven. Each budget has an explicit attaining graph. At eleven stations, the three earlier budgets 22, 23 and 24 have exact values 79, 78 and 79. Thus every budget from 22 onward is classified at order eleven, although the uniform missing-pair formula starts at twelve.

The messenger can use arrows installed in earlier stages. A fixed sequence of graphs supplies certified budget intervals. At each stage, the messenger uses the current compulsory arrows while the pursuer is allowed the larger next envelope. Complete finite certificates check both player positions, every possible pursuer reply and a decreasing rank. This closes the formerly missing sparse and small-order intervals.

Two inaccessible hubs are enough. Assign each outside station a different permitted pair of hubs that it cannot reach. The permitted pairs avoid short cyclic differences. Every other hub arrow is fixed, while arrows between outside stations can be chosen freely. This construction guarantees delivery in two moves and reaches the dense endpoint directly. From order 79, it joins the circle constructions to cover every budget from 3n through n(n − 3). The sparser interval and smaller orders retain their explicit periodic constructions and finite certificates.

An earlier bridge at sixty stations

Each proved envelope permits every subset of its own optional arrows. Taking the required number gives the exact budget. This freedom applies within that envelope; arbitrary arrow additions, or arbitrary subsets across different stages, are not automatically covered.

The earlier results retain their full domains and stronger guarantees. The sparse endpoint M(n,2n) = n(n − 3) holds at every n ≥ 12 with its earlier delivery bound. The dense endpoint M(n,n(n − 3)) = 2n holds at every n ≥ 9. The earlier three-move guide family and two-move dense and hub families remain available in their stated intervals. The complete constructions from orders 104 and 106 remain valid alternatives.

The complete main-interval theorem, six-offset circle proof, and reduced hub proof give the precise recipes and proof boundaries. The finite bridge, periodic sparse family, circles and pair-code family establish the result; a single repeatable vertex-attachment rule is not a required premise. The complete interval has no uniform two-move deadline.

3. The final dense band: some missing pairs must fail

Past n(n − 3) arrows, some missing pairs must fail. Every admissible cell in this final dense band is now exact. For every n ≥ 11, put m = n(n − 3) + r. A single staircase formula covers the whole band:

Each value has an explicit attaining construction. At the first step, one added arrow leaves 2n − 3 guarantees. At the last step,

An exact attachment identity combines safely rooted cores with functional blocks; root-colored cycles complete the constructions. These attain the staircase within four moves at every order from eleven. The threshold eleven is sharp: at ten stations and 74 arrows, the exact value is 12 rather than the staircase's 13. Complete finite proofs settle the smaller dense values; the graph at nine stations and 55 arrows attains 14 and uses at most five moves. These finite exceptions retain their own delivery bounds. The earlier uniform two-move guarantee still covers the entire band at every order from sixteen.

See the staircase theorem and the root-colored cycle and block constructions.

4. Above the final boundary: no indirect guarantee

This range is completely settled. Every graph at these resources has no guaranteed indirect pair, so any graph with the specified number of arrows attains zero. The only graph at order one also has value zero. The dense-boundary proof explains the obstruction.

The completed finite cases

The full tables through eleven stations supply every admissible budget below the universal order threshold. Their proofs combine structural upper bounds, complete finite exclusions and literal attaining graphs. In particular, the entire eight-station row is classified.

Some sparse maxima require a larger host: M(9,17) = 24, while its global maximum 28 first appears at ten stations. At nineteen arrows, the host values are M(9,19) = 35, M(10,19) = 38 and M(n,19) = 40 for every n ≥ 11. At twenty-one arrows, M(10,21) = 56, M(11,21) = 58 and M(n,21) = 60 for every n ≥ 12.

Both numerical coverage and the separate construction audit are complete: every resource pair has an upper proof and an explicit optimal graph. The construction claim comes from inspecting the actual families, their parameters and the listed finite graphs.

Maximizing over one resource gives M_V(n) = max_m M(n,m) and M_E(m) = max_n M(n,m). The vertex maxima are M_V(7) = 21, M_V(8) = 32, M_V(9) = 48, M_V(10) = 65 and M_V(11) = 85; for every n ≥ 12, M_V(n) = n(n − 3).

The combined theorem, the finite sparse-budget completion and the complete finite tables provide the full classification.

Try the game and inspect the evidence

The general counting and construction theorems have ordinary proofs. The finite classification and main-interval bridges also use independently replayed certificates and complete exclusions. The approved registry separates literal graphs, stage intervals, upper proofs and support reductions. The evidence guide identifies those dependencies and distinguishes independent game replay from a second graph enumeration. The Lean development formalizes the game, selected structural implications, and explicit sparse and dense examples; the complete classification remains outside Lean as a concrete theorem.

Optimizing the delivery time is a separate, parked companion problem. Its proved two-move bounds and partial fast constructions remain available without enlarging the scope of the exact-count classification.

Where the work comes from

Alexandra Ignatova developed the original problem and layered construction in 2023 under Angel Raychev's mentorship; the retained manuscript is dated February 2024. The 2023 student research abstracts, page 27 record that provenance. Ignatova and Raychev had already established the n(n − 3) upper bound and investigated two-in/two-out constructions.

The September 2026 work corrects the layered counting argument and develops attaining families, extremal bounds, computational evidence, and formalization with assistance from Astra 6 through Codex. The paper page preserves that credit and the unresolved publication status.