Abelian Cayley graphs produce new high-dimensional expanders with low degree
Abelian Cayley High-Dimensional Expanders with Polylogarithmic Degree
Discrete Mathematics
Summary
The paper finds special geometric structures called high-dimensional expanders that are built from simple algebraic groups called Abelian groups. These structures are highly connected but keep a low number of connections per point, which is useful for many computing applications. The authors use new mathematical methods involving algebraic curves to design these expanders explicitly. Their work might help improve tools that rely on such complex networks.
What this means in practice
- •For network architects: Design network topologies with strong connectivity but fewer links per node for efficient data routing and fault tolerance.
- •For error correction engineers: Develop new error-correcting codes based on explicitly constructed high-dimensional structures for better error detection and correction.
A theory result. No direct application yet.
Authors
Songtao Mao
Abstract
We construct an explicit infinite family of simple two-dimensional Cayley complexes over $\mathbb{F}_2^n$ whose degree is polynomial in $n$ and whose nontrivial vertex-link eigenvalues lie in $[-λ,λ]$ for every fixed $λ>0$. For every fixed $d\ge2$, we also obtain an explicit infinite family of weighted $d$-dimensional Cayley complexes over $\mathbb{F}_2^n$ with codimension-two local spectral norm at most $1/d$ and Cayley degree $Θ_d(n)$. Our two-dimensional construction uses evaluation at rational points of algebraic curves to produce projective direction sets and many functions affine along these directions, which may be useful for further constructions and improvements.