zbMATH — the first resource for mathematics

On the sizes of expander graphs and minimum distances of graph codes. (English) Zbl 1288.05070
Summary: We give lower bounds for the minimum distances of graph codes based on expander graphs. The bounds depend only on the second eigenvalue of the graph and the parameters of the component codes. We also give an upper bound on the size of a degree regular graph with given second eigenvalue.

05C12 Distance in graphs
05C35 Extremal problems in graph theory
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
Full Text: DOI
[1] Barg, A.; Zémor, G., Error exponents of expander codes, IEEE Trans. Inform. Theory, 48, 6, 1725-1729, (2002) · Zbl 1061.94078
[2] Brouwer, A. E.; Haemers, W. H., Spectra of graphs, (2012), Springer New York · Zbl 1231.05001
[3] Cvetković, D. M.; Doob, M.; Sachs, H., Spectra of graphs, (1980), Academic Press New York · Zbl 0458.05042
[4] Davidoff, G.; Sarnak, P.; Valette, A., (Elementary Number Theory, Group Theory, and Ramanujan Graphs, London Mathematical Society, Student Texts, vol. 55, (2003)) · Zbl 1032.11001
[5] Feit, W.; Higman, G., The nonexistence of certain generalized polygons, J. Algebra, 1, 114-131, (1964) · Zbl 0126.05303
[6] Haemers, W. H., Interlacing eigenvalues and graphs, Linear Algebra Appl., 227/228, 593-616, (1995) · Zbl 0831.05044
[7] Høholdt, T.; Janwa, H., Eigenvalues and expansion of bipartite graphs, Des. Codes Cryptogr., 65, (2012) · Zbl 1254.05103
[8] Høholdt, T.; Justesen, J., The minimum distance of graph codes, (Lecture Notes in Computer Science, vol. 6639, (2011)), 201-212 · Zbl 1271.05096
[9] Justesen, J., Iterated decoding of product codes, IEEE Trans. Commun., 59, 407-415, (2011)
[10] Li, W.-C. W.; Sole’, P., Spectra of regular graphs and hypergraphs and orthogonal polynomials, European J. Combin., 17, 461-477, (1996) · Zbl 0864.05072
[11] Lovász, L., Combinatorial problems and exercises, (2007), AMS Chelsea Publishing Providence, Rhode Island · Zbl 1120.05001
[12] Miller, M.; Siran, J., Moore graphs and beyond: a survey of the degree/diameter problem, Electron. J. Combin., #DS14, 1-47, (2005)
[13] Nilli, A., On the second eigenvalue of a graph, Discrete Math., 91, 207-210, (1991) · Zbl 0771.05064
[14] Sipser, M.; Spielmann, D. A., Expander codes, IEEE Trans. Inform. Theory, 42, 6, 1710-1722, (1996) · Zbl 0943.94543
[15] Tanner, M., A recursive approach to low complexity codes, IEEE Trans. Inform. Theory, 27, 533-547, (1981) · Zbl 0474.94029
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.