Metraipolis › archive › dc_5cfda4f4e61f
Subtree Counts and the Maximum Mean Subtree Order — arXiv:2609.14355
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.14355
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T01:25:18.096Z
- SHA-256 of the archived text
85020ed99801cc23856bcf269fec8aa284bdf34c5f5bd22730bf04c1bbe17815- Stable URL of this page
https://metraipolis.com/documento/dc_5cfda4f4e61f
How to cite
Subtree Counts and the Maximum Mean Subtree Order — arXiv:2609.14355 — arXiv (en), https://arxiv.org/abs/2609.14355 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_5cfda4f4e61f (Metraipolis archive dc_5cfda4f4e61f, sha256 85020ed99801cc23856bcf269fec8aa284bdf34c5f5bd22730bf04c1bbe17815)
BibTeX
@misc{dc5cfda4f4e61f,
title = {Subtree Counts and the Maximum Mean Subtree Order — arXiv:2609.14355},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.14355},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_5cfda4f4e61f; sha256 85020ed99801cc23856bcf269fec8aa284bdf34c5f5bd22730bf04c1bbe17815},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.14355. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
For a finite simple graph $G$ of positive order, let $s_k(G)$ be the number of its $k$-vertex tree subgraphs. We prove that, among graphs of a fixed order $n$, the ratios $s_k(G)/s_k(K_n)$ form a nonincreasing sequence in $k$. It follows that the complete graph maximizes the mean subtree order: $\mu(G)\leq\mu(K_n)$, with equality if and only if $G$ is complete. This monotonicity theorem also establishes the $s_{n-1}$-to-$s_n$ ratio conjecture posed in recent work on extremal mean subtree order. The proof lifts a known coupling of rooted Cayley-tree shapes of consecutive orders to uniform labeled tree subgraphs of $K_n$ that are nested at every sample point. Event inclusion gives the count inequalities, and a double-sum identity gives the mean bound.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-15 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.14355 — 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-16T00:39:30.208Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-15?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).