Number of the records: 1
Partition expanders
- 1.
SYSNO ASEP 0434518 Document Type C - Proceedings Paper (int. conf.) R&D Document Type Conference Paper Title Partition expanders Author(s) Gavinsky, Dmitry (MU-W) RID, SAI, ORCID
Pudlák, Pavel (MU-W) RID, SAISource Title 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). - Dagstuhl : Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2014 / Mayr E.W. ; Portier N. - ISSN 1868-8969 - ISBN 978-3-939897-65-1 Pages s. 325-336 Number of pages 12 s. Publication form Print - P Action International Symposium on Theoretical Aspects of Computer Science (STACS 2014), /31./ Event date 05.03.2014-08.03.2014 VEvent location Lyon Country FR - France Event type WRD Language eng - English Country DE - Germany Keywords partitions ; expanders ; random graphs Subject RIV BA - General Mathematics R&D Projects GBP202/12/G061 GA ČR - Czech Science Foundation (CSF) Institutional support MU-W - RVO:67985840 UT WOS 000521069500029 EID SCOPUS 84907815968 DOI 10.4230/LIPIcs.STACS.2014.325 Annotation 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. Workplace Mathematical Institute Contact Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Year of Publishing 2015
Number of the records: 1