{"id":"palomar/PALOMAR-2026-10-01-000003","url":"https://github.com/jfairfaxball-348/Greedy-Uniformity-on-Trees/tree/1733c29a5165148d71a2f0bd1ed2dcd7c35309ce","json":"https://data.palomar-registry.org/entries/PALOMAR-2026-10-01-000003-v1.json","repo":"https://github.com/jfairfaxball-348/Greedy-Uniformity-on-Trees","tags":["math.CO","math.PR","msc:05C05","msc:05C69","random-permutations","independent-sets","trees","probability"],"score":0,"title":"Greedy Uniformity on Trees","trust":"high","domain":"math.CO","source":"palomar","authors":["John Fairfax-Ball"],"reviews":0,"subject":"math.CO","summary":"Formalization of exact distributional results for the random-permutation greedy maximal-independent-set process on finite trees. For every finite nonempty tree, the complete greedy output law is uniform over maximal independent sets exactly for K1 and K2. For the mixed-spider family T_{k,l}, the development counts maximal independent sets, proves exact output probabilities, and for l=2^k-k proves positive total-variation bias with decay O(sqrt(k)/4^k), equivalently O(sqrt(log n_k)/n_k^2) along n_k=2^k+k+1. The Stage-4 novelty classification is \"plausibly new with bounded uncertainty\"; no…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"verified":true,"discussed":0,"published":"2026-10-01","reactions":{},"formalized":true}