Number of the records: 1
Partition expanders
- 1.0434518 - MÚ 2015 RIV DE eng C - Conference Paper (international conference)
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]
R&D Projects: GA ČR GBP202/12/G061
Institutional support: RVO:67985840
Keywords : partitions * expanders * random graphs
Subject RIV: BA - General Mathematics
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.
Permanent Link: http://hdl.handle.net/11104/0238547
File Download Size Commentary Version Access Gavinsky3.pdf 1 675.2 KB Publisher’s postprint open-access
Number of the records: 1