Partition expanders

0434518 - MÚ 2015 RIV DE eng C - Konferenční příspěvek (zahraniční konf.)
Gavinsky, Dmitry - Pudlák, Pavel
Partition expanders.
31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Dagstuhl: Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2014 - (Mayr, E.; Portier, N.), s. 325-336. Leibniz International Proceedings in Informatics, 25. ISBN 978-3-939897-65-1. ISSN 1868-8969.
[International Symposium on Theoretical Aspects of Computer Science (STACS 2014), /31./. Lyon (FR), 05.03.2014-08.03.2014]
Grant CEP: GA ČR GBP202/12/G061
Institucionální podpora: RVO:67985840
Klíčová slova: partitions * expanders * random graphs
Kód oboru RIV: BA - Obecná matematika
http://drops.dagstuhl.de/opus/volltexte/2014/4468/

We introduce a new concept, which we call partition expanders. The basic idea is to study quantitative properties of graphs in a slightly different way than it is in the standard definition of expanders. We show that for some range of parameters, to be a partition expander a random graph needs exponentially smaller degree than any expander would require in order to achieve similar expanding properties.
Trvalý link: http://hdl.handle.net/11104/0238547