---
_id: '18'
abstract:
- lang: eng
text: An N-superconcentrator is a directed, acyclic graph with N input nodes and
N output nodes such that every subset of the inputs and every subset of the outputs
of same cardinality can be connected by node-disjoint paths. It is known that
linear-size and bounded-degree superconcentrators exist. We prove the existence
of such superconcentrators with asymptotic density 25.3 (where the density is
the number of edges divided by N). The previously best known densities were 28
[12] and 27.4136 [17].
article_processing_charge: No
author:
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Michal
full_name: Rolinek, Michal
id: 3CB3BC06-F248-11E8-B48F-1D18A9856A87
last_name: Rolinek
citation:
ama: Kolmogorov V, Rolinek M. Superconcentrators of density 25.3. Ars Combinatoria.
2018;141(10):269-304.
apa: Kolmogorov, V., & Rolinek, M. (2018). Superconcentrators of density 25.3.
Ars Combinatoria. Charles Babbage Research Centre.
chicago: Kolmogorov, Vladimir, and Michal Rolinek. “Superconcentrators of Density
25.3.” Ars Combinatoria. Charles Babbage Research Centre, 2018.
ieee: V. Kolmogorov and M. Rolinek, “Superconcentrators of density 25.3,” Ars
Combinatoria, vol. 141, no. 10. Charles Babbage Research Centre, pp. 269–304,
2018.
ista: Kolmogorov V, Rolinek M. 2018. Superconcentrators of density 25.3. Ars Combinatoria.
141(10), 269–304.
mla: Kolmogorov, Vladimir, and Michal Rolinek. “Superconcentrators of Density 25.3.”
Ars Combinatoria, vol. 141, no. 10, Charles Babbage Research Centre, 2018,
pp. 269–304.
short: V. Kolmogorov, M. Rolinek, Ars Combinatoria 141 (2018) 269–304.
date_created: 2018-12-11T11:44:11Z
date_published: 2018-10-01T00:00:00Z
date_updated: 2023-09-19T14:46:18Z
day: '01'
department:
- _id: VlKo
external_id:
arxiv:
- '1405.7828'
isi:
- '000446809500022'
intvolume: ' 141'
isi: 1
issue: '10'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1405.7828
month: '10'
oa: 1
oa_version: Preprint
page: 269 - 304
publication: Ars Combinatoria
publication_identifier:
issn:
- 0381-7032
publication_status: published
publisher: Charles Babbage Research Centre
publist_id: '8037'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Superconcentrators of density 25.3
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 141
year: '2018'
...