Lower Bounds on Expansions of Graph Powers

Kwok, Tsz Chiu; Lau, Lap Chi

doi:10.4230/LIPIcs.APPROX-RANDOM.2014.313

Document

Lower Bounds on Expansions of Graph Powers

Authors Tsz Chiu Kwok, Lap Chi Lau

Part of: Volume: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Part of: Series: Leibniz International Proceedings in Informatics (LIPIcs)
Part of: Conference: International Conference on Randomization and Computation (RANDOM)
Part of: Conference: International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)
License: Creative Commons Attribution 3.0 Unported license
Publication Date: 2014-09-04

PDF

File

PDF

LIPIcs.APPROX-RANDOM.2014.313.pdf

Filesize: 458 kB
12 pages

Document Identifiers

DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.313
URN: urn:nbn:de:0030-drops-47057

Subject Classification

Keywords

Conductance
Expansion
Graph power
Random walk

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

Abstract

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.

Cite As Get BibTex

Tsz Chiu Kwok and Lap Chi Lau. Lower Bounds on Expansions of Graph Powers. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 313-324, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.313

Author Details

Tsz Chiu Kwok

Lap Chi Lau

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail