Can I read Smoothed Analysis on Connected Graphs on EtoBox?

Smoothed Analysis on Connected Graphs by Krivelevich, Michael; Reichman, Daniel; Samotij, Wojciech is a scholarly article available to read on EtoBox.

What is Smoothed Analysis on Connected Graphs about?

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 $\frac{\epsilon}{n}$, 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(\frac{1}{\log n})$, diameter $O(\log n)$, vertex expansion $\Omega(\frac{1}{\log n})$, 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

Author

Krivelevich, Michael; Reichman, Daniel; Samotij, Wojciech

Published

2013

Language

EN