Smoothed Analysis on Connected Graphs

DOI10.1137/151002496MaRDI QIDQ2947435zbMATH OpenOpenAlexFDO

Authors Michael Krivelevich, Daniel Reichman, Wojciech Samotij

Publication date 23 September 2015

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.4884

zbMATH Keywords

random walksgraph expansionsmall worlds

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Abstract: The main paradigm of smoothed analysis on graphs suggests that for any large graph $G$ in a certain class of graphs, perturbing slightly the edges of $G$ at random (usually adding few random edges to $G$) typically results in a graph having much "nicer" properties. In this work we study smoothed analysis on trees or, equivalently, on connected graphs. Given an $n$-vertex connected graph $G$, form a random supergraph $G^{\ast }$ of $G$ by turning every pair of vertices of $G$ into an edge with probability $fracepsilonn$, where $epsilon$ is a small positive constant. This perturbation model has been studied previously in several contexts, including smoothed analysis, small world networks, and combinatorics. Connected graphs can be bad expanders, can have very large diameter, and possibly contain no long paths. In contrast, we show that if $G$ is an $n$-vertex connected graph then typically $G^{\ast }$ has edge expansion $Omega(frac1logn)$, diameter $O(logn)$, vertex expansion $Omega(frac1logn)$, and contains a path of length $Omega(n)$, where for the last two properties we additionally assume that $G$ has bounded maximum degree. Moreover, we show that if $G$ has bounded degeneracy, then typically the mixing time of the lazy random walk on $G^{\ast }$ is $O(lo{g}^{2}n)$. All these results are asymptotically tight.

Recommendations

• Smoothed Analysis on Connected Graphs
• On smoothed analysis in dense graphs and formulas
• scientific article; zbMATH DE number 1072412
• scientific article; zbMATH DE number 1962932
• Fundamentals of Computation Theory
• Smoothed analysis of the successive shortest path algorithm

Cites work

• scientific article; zbMATH DE number 5485458 (Why is no real title available?)
• scientific article; zbMATH DE number 2119754 (Why is no real title available?)
• Coloring Random and Semi-Random k-Colorable Graphs
• Coloring complete bipartite graphs from random lists
• Crossing numbers of random graphs
• Expansion and Lack Thereof in Randomly Perturbed Graphs
• Faster mixing and small bottlenecks
• Heuristics for semirandom graph problems
• How many random edges make a dense graph hamiltonian?
• How many random edges make a dense hypergraph non-2-colorable?
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• On generalized graphs
• On smoothed \(k\)-CNF formulas and the \texttt{Walksat} algorithm
• On smoothed analysis in dense graphs and formulas
• On the mixing time of a simple random walk on the super critical percolation cluster
• Probability and Computing
• Random graph dynamics
• Renormalization group analysis of the small-world network model
• Sensitivity of mixing times
• Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
• Smoothed analysis of algorithms
• The Diameter of a Cycle Plus a Random Matching
• The Mixing Time of the Newman-Watts Small-World Model
• The diameter of randomly perturbed digraphs and some applications
• The evolution of the mixing rate of a simple random walk on the giant component of a random graph
• The longest path in a random graph
• The mixing time of the giant component of a random graph
• The phase transition in random graphs: a simple proof

Cited in

(12)

• Accelerated information dissemination on networks with local and global edges
• Expansion in supercritical random subgraphs of expanders and its consequences
• Expansion and Lack Thereof in Randomly Perturbed Graphs
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• A framework for imperfectly observed networks
• Isoperimetric numbers of randomly perturbed intersection graphs
• Cycle lengths in sparse random graphs
• scientific article; zbMATH DE number 5769858 (Why is no real title available?)
• Speeding up random walk mixing by starting from a uniform vertex
• Improved mixing rates of directed cycles by added connection
• The genus of the Erdős-Rényi random graph and the fragile genus property
• Smoothed Analysis on Connected Graphs

This page was built for publication: Smoothed Analysis on Connected Graphs

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