Published August 20, 2019
| Submitted
Report
Open
Hypergraph expanders from Cayley graphs
- Creators
-
Conlon, David
Abstract
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
1709.10006.pdf
Files
(178.3 kB)
| Name | Size | Download all |
|---|---|---|
|
md5:4c0725d2884f1286bfa11b0aab628953
|
178.3 kB | Preview Download |
Additional details
- Eprint ID
- 98025
- Resolver ID
- CaltechAUTHORS:20190819-170907486
- Royal Society
- 676632
- European Research Council (ERC)
- Simons Foundation
- Created
-
2019-08-20Created from EPrint's datestamp field
- Updated
-
2023-06-02Created from EPrint's last_modified field