Smoothed Analysis on Connected Graphs

DOI10.1137/151002496zbMATH Open1327.05312arXiv1307.4884OpenAlexW1637337126MaRDI QIDQ2947435FDOQ2947435

Authors: Michael Krivelevich, Daniel Reichman, Wojciech Samotij 

Publication date: 23 September 2015

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

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^{*}$ 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^{*}$ 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^{*}$ is $O(lo{g}^{2}n)$. All these results are asymptotically tight.

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

Recommendations

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

zbMATH Keywords

random walksgraph expansionsmall worlds

Mathematics Subject Classification ID

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

Cites Work

• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Random graph dynamics
• Renormalization group analysis of the small-world network model
• The Mixing Time of the Newman-Watts Small-World Model
• Probability and Computing
• Coloring complete bipartite graphs from random lists
• Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
• Smoothed analysis of algorithms
• On generalized graphs
• On smoothed analysis in dense graphs and formulas
• The Diameter of a Cycle Plus a Random Matching
• Title not available (Why is that?)
• How many random edges make a dense graph hamiltonian?
• The diameter of randomly perturbed digraphs and some applications
• On the mixing time of a simple random walk on the super critical percolation cluster
• 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 phase transition in random graphs: a simple proof
• The mixing time of the giant component of a random graph
• Faster mixing and small bottlenecks
• Sensitivity of mixing times
• Title not available (Why is that?)
• Title not available (Why is that?)
• Heuristics for semirandom graph problems
• Coloring Random and Semi-Random k-Colorable Graphs
• Crossing numbers of random graphs
• How many random edges make a dense hypergraph non-2-colorable?
• Expansion and Lack Thereof in Randomly Perturbed Graphs

Cited In (14)

• Smoothed Analysis on Connected Graphs
• Improved mixing rates of directed cycles by added connection
• Expansion and Lack Thereof in Randomly Perturbed Graphs
• Isoperimetric numbers of randomly perturbed intersection graphs
• A framework for imperfectly observed networks
• Smoothed analysis of dynamic networks
• Some remarks on rainbow connectivity
• Expansion in supercritical random subgraphs of expanders and its consequences
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Title not available (Why is that?)
• The genus of the Erd\H{o}s-R\'enyi random graph and the fragile genus property
• Cycle lengths in sparse random graphs
• Accelerated information dissemination on networks with local and global edges
• Speeding up random walk mixing by starting from a uniform vertex

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)