CaltechAUTHORS
  A Caltech Library Service

Hypergraph expanders of all uniformities from Cayley graphs

Conlon, David and Tidor, Jonathan and Zhao, Yufei (2020) Hypergraph expanders of all uniformities from Cayley graphs. Proceedings of the London Mathematical Society, 121 (5). pp. 1311-1336. ISSN 0024-6115. https://resolver.caltech.edu/CaltechAUTHORS:20190819-170932806

[img] PDF - Submitted Version
See Usage Policy.

365Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190819-170932806

Abstract

Hypergraph expanders are hypergraphs with surprising, non‐intuitive expansion properties. In a recent paper, the first author gave a simple construction, which can be randomized, of 3‐uniform hypergraph expanders with polylogarithmic degree. We generalize this construction, giving a simple construction of r‐uniform hypergraph expanders for all r ⩾ 3.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1112/plms.12371DOIArticle
https://arxiv.org/abs/1809.06342arXivDiscussion Paper
ORCID:
AuthorORCID
Conlon, David0000-0001-5899-1829
Additional Information:© 2020 The Authors. The publishing rights in this article are licensed to the London Mathematical Society under an exclusive licence. Issue Online: 21 July 2020; Version of Record online: 21 July 2020; Manuscript revised: 17 February 2020; Manuscript received: 18 September 2018. D. Conlon was supported by a Royal Society University Research Fellowship and ERC Starting Grant 676632. J. Tidor was supported by an MIT Presidential Fellowship. Y. Zhao was supported by NSF Awards DMS-1764176 and DMS-1362326 and the MIT Solomon Buchsbaum Fund. This paper was partially written while the first author was visiting the California Institute of Technology as a Moore Distinguished Scholar and he is extremely grateful for their kind support.
Funders:
Funding AgencyGrant Number
Royal SocietyUNSPECIFIED
European Research Council (ERC)676632
Massachusetts Institute of Technology (MIT)UNSPECIFIED
NSFDMS-1764176
NSFDMS-1362326
Gordon and Betty Moore FoundationUNSPECIFIED
Issue or Number:5
Classification Code:MSC: 05C65; 05C81 (primary)
Record Number:CaltechAUTHORS:20190819-170932806
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20190819-170932806
Official Citation:Conlon, D., Tidor, J. and Zhao, Y. (2020), Hypergraph expanders of all uniformities from Cayley graphs. Proc. London Math. Soc., 121: 1311-1336. doi:10.1112/plms.12371
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:98032
Collection:CaltechAUTHORS
Deposited By: Melissa Ray
Deposited On:20 Aug 2019 23:10
Last Modified:18 Aug 2020 21:30

Repository Staff Only: item control page