{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:21:40Z","timestamp":1787322100833,"version":"build-2736575974"},"reference-count":31,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>The main paradigm of smoothed analysis on graphs suggests that for any large graph $G$ in a certain class of graphs, perturbing slightly the edge set of $G$ at random (usually adding few random edges to $G$) typically results in a graph having much \u201cnicer\u201d 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{\\varepsilon}{n}$, where $\\varepsilon$ 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 a very large diameter, and can 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)$, and 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 degeneracy, then typically the mixing time of the lazy random walk on $G^*$ is $O(\\log^2 n)$. All these results are asymptotically tight.<\/jats:p>","DOI":"10.1137\/151002496","type":"journal-article","created":{"date-parts":[[2015,9,10]],"date-time":"2015-09-10T13:56:55Z","timestamp":1441893415000},"page":"1654-1669","source":"Crossref","is-referenced-by-count":16,"title":["Smoothed Analysis on Connected Graphs"],"prefix":"10.1137","volume":"29","author":[{"given":"Michael","family":"Krivelevich","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel","family":"Reichman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wojciech","family":"Samotij","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,9,10]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"L. Addario-Berry and T. Lei,\n                      The mixing time of the Newman-Watts small world\n                      , in Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '12, 2012, pp. 1661-1668.","DOI":"10.1137\/1.9781611973099.131"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579172"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20539"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-002-0246-y"},{"key":"atypb5","unstructured":"A. Blum and J. Dunagan,\n                      Smoothed analysis of the perceptron algorithm for linear programming\n                      , in Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '02, 2002, pp. 905-914."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1034"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10070"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01904851"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1137\/0401033"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"A. Coja-Oghlan, U. Feige, A. Frieze, M. Krivelevich, and D. Vilenchik,\n                      On Smoothed k-CNF Formulas and the Walksat Algorithm\n                      , in Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '09, 2009, pp. 451-460.","DOI":"10.1137\/1.9781611973068.50"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1214\/ECP.v18-2765"},{"key":"atypb12","unstructured":"R. Durrett,\n                      Random Graph Dynamics\n                      , Camb. Ser. Stat. Probab. Math., Cambridge University Press, Cambridge, 2010."},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"U. Feige,\n                      Refuting Smoothed $3$CNF Formulas\n                      , in Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS '07, 2007, pp. 407-417.","DOI":"10.1109\/FOCS.2007.16"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1773"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20172"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2007.10129290"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-006-0003-8"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20210"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"M. Jerrum and A. Sinclair,\n                      Conductance and the rapid mixing property for Markov chains: The approximation of the permanent resolved\n                      , in Proceedings of the 20th Annual ACM Symposium on Theory of Computing, STOC '88, 1988, pp. 235-244.","DOI":"10.1145\/62212.62234"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20114"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20435"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20097"},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"D. A. Levin, Y. Peres, and E. L. Wilmer,\n                      Markov Chains and Mixing Times\n                      , American Mathematical Society, Providence, RI, 2009.","DOI":"10.1090\/mbk\/058"},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"M. Mitzenmacher and E. Upfal,\n                      Probability and Computing, Randomized Algorithms and Probabilistic Analysis\n                      , Cambridge University Press, Cambridge, 2005.","DOI":"10.1017\/CBO9780511813603"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1016\/S0375-9601(99)00757-4"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.60.7332"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479803436202"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10053"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990310"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.25155"},{"key":"atypb31","first-page":"248","author":"Tao T.","year":"2007","journal-title":"New York"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/151002496","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:18:11Z","timestamp":1787318291000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/151002496"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/151002496"],"URL":"https:\/\/doi.org\/10.1137\/151002496","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}