Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published August 20, 2019 | Submitted
Report Open

Hypergraph expanders from Cayley graphs


We present a simple mechanism, which can be randomised, for constructing sparse 3-uniform hypergraphs with strong expansion properties. These hypergraphs are constructed using Cayley graphs over ℤ^(t)_(2) and have vertex degree which is polylogarithmic in the number of vertices. Their expansion properties, which are derived from the underlying Cayley graphs, include analogues of vertex and edge expansion in graphs, rapid mixing of the random walk on the edges of the skeleton graph, uniform distribution of edges on large vertex subsets and the geometric overlap property.

Additional Information

Research supported by a Royal Society University Research Fellowship and by ERC Starting Grant 676632. The author gratefully acknowledges the support of the Simons Institute for the Theory of Computing during part of the period when this paper was written. The author is also indebted to Noga Alon, who brought the problem of constructing high-dimensional expanders to his attention, and to Rajko Nenadov, Jonathan Tidor and Yufei Zhao for several valuable discussions.

Attached Files

Submitted - 1709.10006.pdf


Files (178.3 kB)
Name Size Download all
178.3 kB Preview Download

Additional details

August 19, 2023
October 18, 2023