Conlon, David (2019) Hypergraph expanders from Cayley graphs. . (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20190819-170907486
![]() |
PDF
- Submitted Version
See Usage Policy. 178kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190819-170907486
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.
Item Type: | Report or Paper (Discussion Paper) | ||||||||
---|---|---|---|---|---|---|---|---|---|
Related URLs: |
| ||||||||
ORCID: |
| ||||||||
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. | ||||||||
Funders: |
| ||||||||
Record Number: | CaltechAUTHORS:20190819-170907486 | ||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20190819-170907486 | ||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||
ID Code: | 98025 | ||||||||
Collection: | CaltechAUTHORS | ||||||||
Deposited By: | Melissa Ray | ||||||||
Deposited On: | 20 Aug 2019 19:50 | ||||||||
Last Modified: | 03 Oct 2019 21:37 |
Repository Staff Only: item control page