CaltechAUTHORS
  A Caltech Library Service

Hypergraph expanders from Cayley graphs

Conlon, David (2019) Hypergraph expanders from Cayley graphs. . (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20190819-170907486

[img] PDF - Submitted Version
See Usage Policy.

174Kb

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:
URLURL TypeDescription
http://arxiv.org/abs/1709.10006arXivDiscussion Paper
ORCID:
AuthorORCID
Conlon, David0000-0001-5899-1829
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:
Funding AgencyGrant Number
Royal SocietyUNSPECIFIED
European Research Council (ERC)676632
Simons FoundationUNSPECIFIED
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