Symmetric Unique Neighbor Expanders and Good LDPC Codes
Author:
Preprint
Abstract
An infinite family of bounded-degree 'unique-neighbor' expanders was constructed explicitly by Alon and Capalbo (2002). We present an infinite family F of bounded-degree unique-neighbor expanders with the additional property that every graph in the family F is a Cayley graph. This answers a question raised by Tali Kaufman. Using the same methods, we show that the symmetric LDPC codes constructed by Kaufman and Lubotzky (2012) are in fact symmetric under a simply transitive group action on coordinates.Keywords
All Related Versions
- Version 1, 2016-05-01, ArXiv
- Published version: Discrete Applied Mathematics, 211, 211.
This publication has 9 references indexed in Scilit:
- Edge transitive ramanujan graphs and symmetric LDPC good codes2012
- Symmetric LDPC Codes and Local TestingLecture Notes in Computer Science, 2010
- Explicit constructions of Ramanujan complexes of typeEuropean Journal of Combinatorics, 2005
- Expander codesIEEE Transactions on Information Theory, 1996
- Eigenvalues and expansion of regular graphsJournal of the ACM, 1995
- Explicit construction of linear sized tolerant networksDiscrete Mathematics, 1988
- Ramanujan graphsCombinatorica, 1988
- A recursive approach to low complexity codesIEEE Transactions on Information Theory, 1981
- The minimum distance of all binary cyclic codes of odd lengths from 69 to 99IEEE Transactions on Information Theory, 1978