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 Zt2 and have vertex degree which is polylogarithmic in the number of vertices. Their expansion propert...
| Main Author: | |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Springer
2019
|
| _version_ | 1797050267901886464 |
|---|---|
| author | Conlon, D |
| author_facet | Conlon, D |
| author_sort | Conlon, D |
| collection | OXFORD |
| description | 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 Zt2 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. |
| first_indexed | 2024-03-06T18:02:39Z |
| format | Journal article |
| id | oxford-uuid:00586e76-5b82-4e3d-b920-52bf67021568 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T18:02:39Z |
| publishDate | 2019 |
| publisher | Springer |
| record_format | dspace |
| spelling | oxford-uuid:00586e76-5b82-4e3d-b920-52bf670215682022-03-26T08:29:04ZHypergraph expanders from Cayley graphsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:00586e76-5b82-4e3d-b920-52bf67021568EnglishSymplectic Elements at OxfordSpringer2019Conlon, DWe 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 Zt2 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. |
| spellingShingle | Conlon, D Hypergraph expanders from Cayley graphs |
| title | Hypergraph expanders from Cayley graphs |
| title_full | Hypergraph expanders from Cayley graphs |
| title_fullStr | Hypergraph expanders from Cayley graphs |
| title_full_unstemmed | Hypergraph expanders from Cayley graphs |
| title_short | Hypergraph expanders from Cayley graphs |
| title_sort | hypergraph expanders from cayley graphs |
| work_keys_str_mv | AT conlond hypergraphexpandersfromcayleygraphs |