Pairwise edge correlations in random minimum spanning trees

This repository is the GitHub home for the paper Pairwise edge correlations in random minimum spanning trees: a universal bound and complete-graph negative correlation by Anish Gupta, arXiv:2608.06816 [math.PR].

The paper proves a universal factor-8 bound for two-edge inclusion in minimum spanning trees with i.i.d. atomless edge weights, gives simple-graph counterexamples to pairwise negative correlation, proves strict pairwise negative correlation on every complete graph, and relates the complete-graph pair probabilities to the expected minimum-spanning-tree weight.

• Read the paper on arXiv (or the built PDF in this repository)
• Archival snapshot on Zenodo (all versions; resolves to the most recent deposit)
• See the preferred citation
• Explore the exact supporting data

Status: preprint, arXiv:2608.06816v1, announced August 2026. The v2 tag marks the repository state matching the current manuscript; v1 marks the earlier 3 August snapshot. This repository provides a stable paper landing page and its optional supporting materials; it is not a claim of peer review.

Supporting computations

The mathematical proofs are contained in the paper and do not require the software. The repository also includes exact data and standard-library Python checks for readers who want to inspect the finite computations and certificates.

Requirements are Python 3 using only the standard library and a working pdflatex. No BibTeX or latexmk step is required.

make check          # standard exact suite
make check-full     # widest documented exact suite
make table          # regenerate data/kn-exact-table.csv
make clean paper    # clean three-pass manuscript build
make verify-sha256  # verify the release-tree integrity manifest

The executable checks independently evaluate finite MST measures, regenerate the complete-graph data, verify polynomial certificates and counterexamples, and retain deliberately false variants as hostile controls.

Repository contents

paper/                         manuscript source and PDF
data/                          exact and published-comparison tables
src/                           exact algorithms and table generator
tests/                         exact regression and claim checks
evidence/SHA256SUMS.txt        release-tree integrity manifest
CITATION.cff                   GitHub and general citation metadata
LICENSES.md                    manuscript/data/software licence boundary

Citation

Cite the arXiv version of the paper: arXiv:2608.06816, doi:10.48550/arXiv.2608.06816. Preferred citation metadata are provided in CITATION.cff.

The manuscript is additionally archived on Zenodo under the all-versions DOI doi:10.5281/zenodo.21780629, which resolves to the most recent deposit. That record was created before the paper reached arXiv and is retained as an archival snapshot, not as the version of record. Individual deposits also carry their own version DOIs: 10.5281/zenodo.21780630 is the v1 snapshot of 3 August 2026, which predates the revisions in the current manuscript.

Licence

Software under src/ and tests/, together with the Makefile, is available under the MIT License. The manuscript and accompanying data are available under CC BY 4.0. See LICENSES.md for the exact boundary.

Contact

• Anish Gupta, independent researcher
• ag2269@cantab.ac.uk
• ORCID 0009-0008-8137-7729