Keyboard shortcuts

Press ← or → to navigate between chapters

Press ? to show this help

Press Esc to hide this help

Rainbow Rank Descent with a Reserved Final Edge

Abstract

Fixed sampled counts on actual robust layers give simple directed rainbow connectors after every allowed deletion, including exceptional targets.

Paths are ordinary quiver paths whose arrows are proofs of the directed adjacency relation. Their vertex lists must have no repetitions. Their colour words multiply singleton words containing the original colour of each ordered edge, so rainbowness means that this literal ordered list has no repetitions. Allowed paths restrict only internal vertices to the selected set R outside a forbidden vertex set A, while every colour lies in the selected colour set S outside a forbidden colour set D. Endpoints may lie anywhere and may themselves belong to A.

Theorem 1.1 (Connect All Targets after the Reservoirs Are Selected).

Lean statement: D5/S3/Combinatorics/Graph/Rainbow/RankDescent.robust_connector

Proof. Machine-checked in Lean as D5/S3/Combinatorics/Graph/Rainbow/RankDescent.robust_connector (✓ std3). ∎

Source. Repository-derived.

Commentary.

Let V be finite, C any colour type, G a loopless directed relation on V, and c its literal edge-colour function. At each vertex c is injective separately on the outgoing and on the incoming star. Let nu and tau be positive real numbers, let p be positive and at most one, and let alpha and b be real numbers. Assume nu+tau at most alpha, p cubed times nu squared times n at least 144 log n, exterior robust expansion and both minimum semidegrees at least alpha n. Let R and S be arbitrary finite selected vertex and colour sets. For each root u, define B(u) as the endpoints w with more than nu n/16 intermediate vertices x for which u to x to w has equal colours. Outgoing properness bounds the total number of these repetitions by n, giving size strictly below 16/nu for B(u).

The following three sampled counts are required, simultaneously before the forbidden sets are chosen. For every distinct u,w with w outside B(u) and at least nu n/4 predecessors in L_u(0), at least 3b+5/nu middle vertices x give actual edges u to x to w, two different colours, x in R, and both colours in S. For every root u, natural index i with i+2 at most floor(1/nu), and vertex w with at least nu n/4 predecessors in L_u(i) outside L_u(0), at least 2b+20/nu of these predecessors x lie in R and have c(x,w) in S. Finally every vertex w has at least 2b+20/nu incoming predecessors x in R whose incoming edge colour lies in S.

Then for every ordered pair u,v of distinct vertices and every pair of finite forbidden sets A and D, each of size at most b, there is an allowed simple directed rainbow path from u to v of edge length at most 1/nu+1. No containment or independence assumption on the forbidden sets is needed. In the random-reservoir application b equals p cubed times nu n divided by one hundred; the three simultaneous sampled counts are the remaining probabilistic inputs.

First derive the strict parameter bounds and the early covering index m from exterior expansion. For a nonexceptional target at robust rank i, recursively allow A and D to grow by one element for each rank unit spent. The invariant bounds their cardinalities plus i by their original budgets plus m. If the target has enough initial-star predecessors, deletion removes at most the current vertex budget plus twice the current colour budget from the sampled rainbow two-edge choices. Otherwise use the sampled incoming count outside the initial star. Incoming properness bounds the number removed by each forbidden colour, and the layer-entry property gives a strictly earlier rank for a surviving predecessor. Reserve the present target and the new edge colour in the recursive forbidden sets, then append that edge. This proves simplicity and literal rainbowness together, with length at most i+2.

For an exceptional final target v, choose a selected predecessor x outside B(u), A and the root, with allowed incoming colour. Use the nonexceptional construction with v and that colour added to the forbidden sets. Its bounds allow these extra one-element deletions. Appending x to v gives a simple rainbow path of length at most m+3, hence at most floor(1/nu)+1. The strict early-stop bound and the extra forbidden budgets pay for precisely this final edge.

References