PreprintarXiv licencearXiv
Subtree Counts and the Maximum Mean Subtree Order
Abstract
For a finite simple graph G of positive order, let sk(G) be the number of its k-vertex tree subgraphs. We prove that, among graphs of a fixed order n, the ratios sk(G)/sk(Kn) form a nonincreasing sequence in k. It follows that the complete graph maximizes the mean subtree order: μ(G)≤μ(Kn), with equality if and only if G is complete. This monotonicity theorem also establishes the sn−1-to-sn 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 Kn that are nested at every sample point. Event inclusion gives the count inequalities, and a double-sum identity gives the mean bound.
Related
- Rare subtree patterns in size-conditioned Bienaymé trees: Poisson approximation and declumping
- On the largest common subtree of uniform attachment trees
- Tensor network representations of discrete maximum entropy distributions via mean polytopes
- Maximum Entropy Probability Distributions on Spheres with Fixed Mean Busemann Function and Holomorphic-Information-Geometric Model of Cognition
- Edge-Defect Spectral Methods for Higher-Order Rankings of Spanning Tree Counts
BibTeX
@misc{chen2026subtree,
title = {{Subtree Counts and the Maximum Mean Subtree Order}},
author = {Jungang Chen and Xian'an Jin and Zhuo Li and Hongxia Ma},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.14355},
eprint = {2609.14355},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.14355},
}
RIS
TY - UNPB
TI - Subtree Counts and the Maximum Mean Subtree Order
AU - Jungang Chen
AU - Xian'an Jin
AU - Zhuo Li
AU - Hongxia Ma
PY - 2026
DA - 2026/09/13
PB - arXiv
DO - 10.48550/arxiv.2609.14355
UR - https://arxiv.org/abs/2609.14355
AB - 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: μ(G)≤μ(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.
ER -