Name
Abstract | ||
|---|---|---|
Expander graphs have been a focus of attention in computer science in the last four decades. In recent years a high dimensional theory of expanders is emerging. There are several possible generalizations of the theory of expansion to simplicial complexes, among them stand out coboundary expansion and topological expanders. It is known that for every d there are unbounded degree simplicial complexes of dimension d with these properties. However, a major open problem, formulated by Gromov, is whether bounded degree high dimensional expanders, according to these definitions, exist for d ≥ 2. We present an explicit construction of bounded degree complexes of dimension d = 2 which are high dimensional expanders. More precisely, our main result says that the 2-skeletons of the 3-dimensional Ramanujan complexes are topological expanders. Assuming a conjecture of Serre on the congruence subgroup property, infinitely many of them are also coboundary expanders. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1109/FOCS.2014.58 | Foundations of Computer Science |
Keywords | Field | DocType |
graph theory,group theory,3-dimensional Ramanujan complexes,bounded degree complexes,bounded degree high dimensional expanders,bounded degree topological expanders,coboundary expansion,computer science,congruence subgroup property,expander graphs,high dimensional theory,topological expanders,Ramanujan complexes,high dimensional expanders,topological expanders,topological overlapping | Graph theory,Discrete mathematics,Topology,Combinatorics,Open problem,Expander graph,Ramanujan's sum,Generalization,Congruence subgroup,Conjecture,Mathematics,Bounded function | Conference |
Volume | ISSN | Citations |
abs/1408.6351 | 0272-5428 | 10 |
PageRank | References | Authors |
0.80 | 5 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tali Kaufman | 1 | 499 | 38.33 |
| David Kazhdan | 2 | 20 | 1.88 |
| Alexander Lubotzky | 3 | 231 | 43.47 |