2026-08-14T20:02:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4705 2024-03-06T10:35:16Z ddc:004 open_access

Lower Bounds on Expansions of Graph Powers Kwok, Tsz Chiu Lau, Lap Chi Conductance Expansion Graph power Random walk Given a lazy regular graph G, we prove that the expansion of G^t is at least sqrt(t) times the expansion of G. This bound is tight and can be generalized to small set expansion. We show some applications of this result. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tsz Chiu Kwok and Lap Chi Lau 2014 Is Part Of LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2014.313 urn:nbn:de:0030-drops-47057 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.313 eng https://creativecommons.org/licenses/by/3.0/legalcode