DROPS

Document

DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.313

Lower Bounds on Expansions of Graph Powers

Authors: Tsz Chiu Kwok and Lap Chi Lau

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

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

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)

Copy BibTex To Clipboard

@InProceedings{kwok_et_al:LIPIcs.APPROX-RANDOM.2014.313,
  author =	{Kwok, Tsz Chiu and Lau, Lap Chi},
  title =	{{Lower Bounds on Expansions of Graph Powers}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{313--324},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.313},
  URN =		{urn:nbn:de:0030-drops-47057},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.313},
  annote =	{Keywords: Conductance, Expansion, Graph power, Random walk}
}

Search Results

Documents authored by Kwok, Tsz Chiu

Lower Bounds on Expansions of Graph Powers

Abstract

Cite as

Thanks for your feedback!

Could not send message