Loading...
Please wait, while we are loading the content...
Similar Documents
Hypergraph expanders from Cayley graphs
| Content Provider | Semantic Scholar |
|---|---|
| Author | Conlon, David |
| Copyright Year | 2017 |
| 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 $\mathbb{Z}_2^t$ 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. |
| Starting Page | 1 |
| Ending Page | 17 |
| Page Count | 17 |
| File Format | PDF HTM / HTML |
| DOI | 10.1007/s11856-019-1895-1 |
| Alternate Webpage(s) | https://arxiv.org/pdf/1709.10006v2.pdf |
| Alternate Webpage(s) | http://people.maths.ox.ac.uk/~conlond/hypergraphexpanders.pdf |
| Alternate Webpage(s) | https://doi.org/10.1007/s11856-019-1895-1 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
