Noise sensitivity of the minimum spanning tree of the complete graph

DOI10.1017/S0963548324000129MaRDI QIDQ6883598zbMATH OpenFDO

Authors Omer Israeli, Yuval Peled

Publication date 16 December 2025

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1017/S0963548324000129

zbMATH Keywords

minimum spanning treenoise sensitivityrandom graphsscaling limits

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Modular lattices, Desarguesian lattices (06C05) Central limit and other weak theorems (60F05)

Cites work

• Brownian excursions, critical random graphs and the multiplicative coalescent
• Critical random graphs: limiting constructions and distributional properties
• Exceptional times of the critical dynamical Erdős-Rényi graph
• Noise sensitivity of Boolean functions and applications to percolation
• Noise sensitivity of critical random graphs
• On the shortest spanning subtree of a graph and the traveling salesman problem
• On the value of a random minimum spanning tree problem
• Otakar Borůvka on minimum spanning tree problem. Translation of both the 1926 papers, comments, history
• Probability theory. An analytic view.
• Random trees and applications
• Scaling limit of dynamical percolation on critical Erdős-Rényi random graphs
• Strong noise sensitivity and random graphs
• Susceptibility in subcritical random graphs
• The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph
• The scaling limit of the minimum spanning tree of the complete graph
• The Structure of a Random Graph at the Point of the Phase Transition

This page was built for publication: Noise sensitivity of the minimum spanning tree of the complete graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6883598)