Metraipolis › archive › dc_09f85528f7b8

Greedy Uniformity on Trees: Exact Obstruction and Near-Uniform Spiders — arXiv:2610.02276

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.02276
License (as archived)
CC0-1.0
Archived
2026-10-06T08:24:27.066Z
SHA-256 of the archived text
e058fa5d00a09298d3c9284109a77a6ed31bda7b65fed66e53e27a07c4bb4048
Stable URL of this page
https://metraipolis.com/documento/dc_09f85528f7b8

How to cite

Greedy Uniformity on Trees: Exact Obstruction and Near-Uniform Spiders — arXiv:2610.02276 — arXiv (en), https://arxiv.org/abs/2610.02276 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_09f85528f7b8 (Metraipolis archive dc_09f85528f7b8, sha256 e058fa5d00a09298d3c9284109a77a6ed31bda7b65fed66e53e27a07c4bb4048)
BibTeX
@misc{dc09f85528f7b8,
  title = {Greedy Uniformity on Trees: Exact Obstruction and Near-Uniform Spiders — arXiv:2610.02276},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.02276},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_09f85528f7b8; sha256 e058fa5d00a09298d3c9284109a77a6ed31bda7b65fed66e53e27a07c4bb4048},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.02276. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-10-05 in math.CO).
Categorie arXiv: Combinatorics (math.CO) ; Probability (math.PR).
Pagina del lavoro: https://arxiv.org/abs/2610.02276 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-06T08:18:48.274Z dalla pagina https://arxiv.org/catchup/math.CO/2026-10-05?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).