LIPIcs.APPROX-RANDOM.2014.313.pdf
- Filesize: 458 kB
- 12 pages
Document
Lower Bounds on Expansions of Graph Powers
Authors
-
Part of:
Volume:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Randomization and Computation (RANDOM)
Conference: International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2014-09-04
File
Document Identifiers
Cite AsGet 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
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.313
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.
Keywords
- Conductance
- Expansion
- Graph power
- Random walk
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads