A sharp lower bound for adjacent-edge correlations in random subtrees
Loading original first page…
Abstract
For a uniformly chosen nonempty subtree of the labeled complete graph K_n, with singleton subtrees included, the conditional probability of an edge given an adjacent edge is strictly greater than three quarters of its unconditional probability for every n >= 3. This proves the lower-bound conjecture stated by Luo, Xu and Tian in their 2023 author manuscript. Classical fixed-forest extension counts reduce the inequality to a reciprocal moment of the subtree order; Jensen’s inequality and a count of four-vertex trees then establish the strict bound. A self-contained derivation of the previously known limiting ratio 3/4 establishes optimality of the constant.
Read the full paper in the original PDF.
Edition files
- main.pdf164.6 KiB · pdf
SHA-256
94c6483dce59f9404508a451152113a594a59c818a97d4cdf2e7241efa1c190e - Revised_publication_package.zip166.4 KiB · package
SHA-256
47200eb91425dc5eff8123f8a684e2f0b81ace679b1d62fecb1b6952c43fe040
Available editions
Research details
- Subjects
- Mathematics · Combinatorics and Graph Theory
- Keywords
- random subtrees, adjacent-edge correlations, complete graphs, Cayley’s formula, Jensen’s inequality
- Manuscript date
- 2026-10-18
- Reader reuse
- No additional permission granted
Scope
For a uniform nonempty subtree of the labelled complete graph and two distinct adjacent edges, the conditional inclusion probability exceeds three quarters of the unconditional one; the constant is asymptotically sharp.
Reproduction
The three-page manuscript and seven-file editable source package include the complete analytic proof, a credited derivation of the known optimal limiting constant, standard-library exact finite checks, build instructions and integrity manifests. Run verification/independent_check.py with ordinary Python 3, without -O or -OO.