
arXiv: 2112.01647
For an abelian group $H$ acting on the set $[\ell]$, an $(H,\ell)$-lift of a graph $G_0$ is a graph obtained by replacing each vertex by $\ell$ copies, and each edge by a matching corresponding to the action of an element of $H$. In this work, we show the following explicit constructions of expanders obtained via abelian lifts. For every (transitive) abelian group $H \leqslant \text{Sym}(\ell)$, constant degree $d \ge 3$ and $��> 0$, we construct explicit $d$-regular expander graphs $G$ obtained from an $(H,\ell)$-lift of a (suitable) base $n$-vertex expander $G_0$ with the following parameters: (i) $��(G) \le 2\sqrt{d-1} + ��$, for any lift size $\ell \le 2^{n^��}$ where $��=��(d,��)$, (ii) $��(G) \le ��\cdot d$, for any lift size $\ell \le 2^{n^{��_0}}$ for a fixed $��_0 > 0$, when $d \ge d_0(��)$, or (iii) $��(G) \le \widetilde{O}(\sqrt{d})$, for lift size ``exactly'' $\ell = 2^{��(n)}$. As corollaries, we obtain explicit quantum lifted product codes of Panteleev and Kalachev of almost linear distance (and also in a wide range of parameters) and explicit classical quasi-cyclic LDPC codes with wide range of circulant sizes. Items $(i)$ and $(ii)$ above are obtained by extending the techniques of Mohanty, O'Donnell and Paredes [STOC 2020] for $2$-lifts to much larger abelian lift sizes (as a byproduct simplifying their construction). This is done by providing a new encoding of special walks arising in the trace power method, carefully "compressing'" depth-first search traversals. Result $(iii)$ is via a simpler proof of Agarwal et al. [SIAM J. Discrete Math 2019] at the expense of polylog factors in the expansion.
31 pages
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Computer Science - Information Theory, Information Theory (cs.IT), expander graphs, 004, 510, Computer Science - Data Structures and Algorithms, FOS: Mathematics, Mathematics - Combinatorics, quantum LDPC codes, Data Structures and Algorithms (cs.DS), Combinatorics (math.CO), Graph lifts, quasi-cyclic LDPC codes, Computer Science - Discrete Mathematics, ddc: ddc:004
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Computer Science - Information Theory, Information Theory (cs.IT), expander graphs, 004, 510, Computer Science - Data Structures and Algorithms, FOS: Mathematics, Mathematics - Combinatorics, quantum LDPC codes, Data Structures and Algorithms (cs.DS), Combinatorics (math.CO), Graph lifts, quasi-cyclic LDPC codes, Computer Science - Discrete Mathematics, ddc: ddc:004
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
