A sharp lower bound for adjacent-edge correlations in random subtrees
Loading original first page…
Abstract
Choose uniformly a nonempty tree subgraph of the labeled complete graph, including single-vertex trees. For every n ≥ 3 and two distinct adjacent edges, we prove that the conditional probability of one edge, given the other, exceeds three quarters of its unconditional probability. The short proof combines classical fixed-forest extension counts, Jensen’s inequality and a count of four-vertex trees. The constant is sharp by the previously established asymptotic limit.
Read the full paper in the original PDF.
Edition files
- main.pdf55.0 KiB · pdf
SHA-256
7d5325015ef9abcc3861533c977074d2695c6cb6071af7a02b4e9529238465c5 - main.tex5.7 KiB · source
SHA-256
f6fae95f9fe647bbff8fc02a814ff1867923a6609fa902e4eef7588aecbf4049 - Random-subtree-correlations-edition-1-privacy-corrected-20261019.zip57.3 KiB · package
SHA-256
bc583b54e248acb61b00286b1a1c8d10a7cdf53142273f7a4fcbcb906d2932d5 - subtree_publication_qualified_20261018_source.zip3.5 KiB · package
SHA-256
cc380295b25b096c7830e6e1e25a41738567fbffcd519f4b14cf2776d4f2f776 - MANIFEST.sha256.json0.7 KiB · manifest
SHA-256
dab8d8733e8ba41194dee41e12158bc824bc3eb2b2ad1befc764f945ff6e0d0d
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
Uniform nonempty tree subgraphs of labeled complete graphs, with singleton trees included. Subtrees may be induced or noninduced, spanning or nonspanning.
Reproduction
The complete package includes the three-page paper, LaTeX source, exact-arithmetic checker and checksum manifest. Reproduction instructions are in README.txt. Finite exact checks supplement the analytic proof for all n.
Publication package corrected to contain publication materials only. The manuscript and edition are unchanged.