---
_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
arxiv: 1
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. <i>Ars Combinatoria</i>.
    2018;141(10):269-304.
  apa: Kolmogorov, V., &#38; Rolinek, M. (2018). Superconcentrators of density 25.3.
    <i>Ars Combinatoria</i>. Charles Babbage Research Centre.
  chicago: Kolmogorov, Vladimir, and Michal Rolinek. “Superconcentrators of Density
    25.3.” <i>Ars Combinatoria</i>. Charles Babbage Research Centre, 2018.
  ieee: V. Kolmogorov and M. Rolinek, “Superconcentrators of density 25.3,” <i>Ars
    Combinatoria</i>, 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.”
    <i>Ars Combinatoria</i>, 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'
...