Guaranteed indirect delivery in directed networks: The joint extremal function and explicit attaining constructions
math.CO
Submitted: 2026-10-29
Updated: 2026-10-29
Comments: 128 pages, 9 figures. Explicit extremal classification with reproducible computational certificates and partial Lean verification. Companion: https://angelraychev.com/cop-prisoner/
License: http://creativecommons.org/licenses/by/4.0/
The gist: A messenger and a pursuer move alternately on a finite loopless directed graph, with complete information and waiting permitted.
Abstract
A messenger and a pursuer move alternately on a finite loopless directed graph, with complete information and waiting permitted. The messenger moves first and wins upon reaching a designated recipient, before interception there. We determine the maximum number M(n,m) of ordered nonadjacent source--recipient pairs for which delivery is guaranteed against every initial pursuer position, among graphs with n vertices and m arcs. We give the exact value and an explicit attaining graph for every admissible pair (n,m). For n at least12, a piecewise formula describes sparse growth, the interval 2n at most m at most n(n-3) in which every missing pair can be guaranteed, a dense staircase, and the zero range above n(n-2). Complete finite tables cover smaller orders. The proofs combine degree and support bounds, local strategy composition, protected routing, and constructions in the missing-arc graph. Finite exceptional cases use explicit strategy certificates and complete computational exclusions. Reproducible programs and certificates accompany the paper; a Lean development verifies the complete formula for n at least12 and m at least24, the claimed scores of prescribed constructions at every admissible pair, and further finite upper bounds. Its remaining obligations are stated separately.
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality