Hypergraph expanders of all uniformities from Cayley graphs
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.
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.
Submitted - 1809.06342.pdf