Greedy Uniformity on Trees: Exact Obstruction and Near-Uniform Spiders
Abstract
Choose a uniformly random ordering of the vertices of a finite tree and run the usual greedy maximal-independent-set algorithm. We compare the resulting law on maximal independent sets with the uniform law. We prove that exact uniformity occurs only for the one-vertex tree and the single edge. The proof is structural: a diameter endpoint exposes a pendant star, and the remaining one-pendant-leaf case is resolved by a strict injection between exact permutation fibres obtained by swapping the pendant leaf with its support vertex. Exact uniformity is therefore rigid, but it can be approached closely. For an explicit mixed-spider family Tk,l we count the maximal independent sets and compute the exact probability of every output. With l=2k−k the total-variation bias is positive and satisfies [ b(T_{k,2^k-k})=O!\left(\frac{\sqrt{k}}{4^k}\right) =O!\left(\frac{\sqrt{\log n_k}}{n_k^2}\right), \qquad n_k=2^k+k+1. ] The theorem package has also been formalised in Lean and registered with Palomar. These records document machine-checked formal verification and the checked axiom boundary; they are not peer review or a certificate of novelty.
Related
- Greedy sampling designs via reduced basis methods: optimal recovery in the uniform norm
- Uniform integrability of the distance to the nearest leaf in random trees
- An algorithm for uniform generation of unlabeled (Pólya) trees
- On the largest common subtree of uniform attachment trees
- Product approximations for uniform spanning trees and determinantal processes
BibTeX
@misc{fairfaxball2026greedy,
title = {{Greedy Uniformity on Trees: Exact Obstruction and Near-Uniform Spiders}},
author = {John Fairfax-Ball},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.02276},
eprint = {2610.02276},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.02276},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Greedy Uniformity on Trees: Exact Obstruction and Near-Uniform Spiders
AU - John Fairfax-Ball
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.02276
UR - https://arxiv.org/abs/2610.02276
AB - Choose a uniformly random ordering of the vertices of a finite tree and run the usual greedy maximal-independent-set algorithm. We compare the resulting law on maximal independent sets with the uniform law. We prove that exact uniformity occurs only for the one-vertex tree and the single edge. The proof is structural: a diameter endpoint exposes a pendant star, and the remaining one-pendant-leaf case is resolved by a strict injection between exact permutation fibres obtained by swapping the pendant leaf with its support vertex. Exact uniformity is therefore rigid, but it can be approached closely. For an explicit mixed-spider family T_k,l we count the maximal independent sets and compute the exact probability of every output. With l=2^k−k the total-variation bias is positive and satisfies [ b(T_{k,2^k-k})=O!\left(\frac{\sqrt{k}}{4^k}\right) =O!\left(\frac{\sqrt{\log n_k}}{n_k^2}\right), \qquad n_k=2^k+k+1. ] The theorem package has also been formalised in Lean and registered with Palomar. These records document machine-checked formal verification and the checked axiom boundary; they are not peer review or a certificate of novelty.
ER -