×

zbMATH — the first resource for mathematics

Eigenvalues and expansion of bipartite graphs. (English) Zbl 1254.05103
Summary: We prove lower bounds on the largest and second largest eigenvalue of the adjacency matrix of connected bipartite graphs and give necessary and sufficient conditions for equality. We give several examples of classes of graphs that are optimal with respect to the bounds. We prove that BIBD-graphs are characterized by their eigenvalues. Finally we present a new bound on the expansion coefficient of \((c, d)\)-regular bipartite graphs and compare that with with a classical bound.

MSC:
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C45 Eulerian and Hamiltonian graphs
05B05 Combinatorial aspects of block designs
94C30 Applications of design theory to circuits and networks
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alon N., Chung F.R.K.: Explicit construction of linear sized tolerant networks. Discret. Math. 72, 15–19 (1988) · Zbl 0657.05068 · doi:10.1016/0012-365X(88)90189-6
[2] Arslan O.: The dimension of LU(3,q) codes. J. Comb. Theory A 116(5), 1073–1079 (2009) · Zbl 1169.94015 · doi:10.1016/j.jcta.2008.12.007
[3] Barg A., Zemor G.: Error exponent of expander codes. IEEE Trans. Inform. Theory 48(6), 1725–1729 (2002) · Zbl 1061.94078 · doi:10.1109/TIT.2002.1003853
[4] Chung F.G.: Spectral Graph Theory. (Revised and Improved Edition). http://www.math.ucsd.edu-fan .
[5] Cvetkovic D.M., Doob M., Sachs H.: Spectra of Graphs: Theory and Applications. Academic Press (1979). · Zbl 0458.05042
[6] Cvetkovic D., Rowlinson P., Simic S.: An introduction to the theory of graph spectra. Cambridge University Press (2010).
[7] Davidoff G., Sarnak P., Valette A.: Elementary Number Teory, Group Theory, and Ramanujan Graphs. London Mathematical Society Student Texts 55 (2003). · Zbl 1032.11001
[8] Forney G.D.: Codes on graphs: recent progress. Phys. A 302(104), 1–13 (2001) · Zbl 0980.68078 · doi:10.1016/S0378-4371(01)00436-8
[9] Godsil C.D.: Algebraic Combinatorics. Chapman and Hall (1993). · Zbl 0784.05001
[10] Gunnells P.E.: Some elementary Ramanujan graphs. Geometriae Dedicata 112, 51–63 (2005) · Zbl 1074.05046 · doi:10.1007/s10711-005-0549-0
[11] Guruswami V., Indyk P.: Expander-based construction of efficiently decodable codes. 42nd IEEE Symposium on Foundation of Computer Science, October 14–17, 658 (2001).
[12] Hall M. Jr.: Combinatorial Theory, 2nd edn. Wiley Interscience in discrete Mathematics.
[13] Høholdt T., Janwa H.: Optimal bipartite Ramanujan graphs from balanced incomplete block designs: their characterizations and applications to expander/LDPC codes. In: Bras-Amoros M., Høholdt T. (eds.) Proceedings of AAECC-18. Springer Lecture Notes in Computer Science, vol. 5527, pp. 53–64 (2009). · Zbl 1273.05185
[14] Horn Roger A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, (1992). · Zbl 0704.15002
[15] Hoory S., Linial N., Wigderson A.: Expander graphs and their applications. Bull. Am. Math. Soc. (N.S.), 43(4), 439–561 (2006) · Zbl 1147.68608 · doi:10.1090/S0273-0979-06-01126-8
[16] Janwa H., Lal A.K.: On Expander Graphs: Parameters and Applications. submitted, January 2001. (see arXiv:cs.IT/04060-48v1).
[17] Janwa H., Lal A.K.: On tanner codes: parameters and decoding. Appl. Algebra Eng. Commun. Comput. 13, 335–347 (2003) · Zbl 1031.94018 · doi:10.1007/s00200-003-0098-4
[18] Janwa H., Moreno O.: Strongly Ramanujan graphs from codes, polyphase-sequences, and Combinatorics. Proceedings of the International Symposium on Information Theory, 1997 (ISIT-97) Ulm, Germany, pp. 408–408 (1997).
[19] Kim J.L., Peled U.N., Perepelitsa I., Pless V., Friedl S.: Explicit construction of families of LDPC codes with no 4-cycles. IEEE Trans. Inform. Theory 50, 2378–2388 (2004) · Zbl 1315.94140 · doi:10.1109/TIT.2004.834760
[20] Kou Y., Lin S., Fossorier M.P.C.: Low-density parity-check codes based on finite geometries: a rediscovery and new results. IEEE Trans. Inform. Theory 47(7), 2711–2736 (2001) · Zbl 1015.94015 · doi:10.1109/18.959255
[21] Lazebnik F., Ustimenko V.A.: Explicit construction of graphs with arbitrary large girth and of largh size. Discret. Appl. Math. 60, 275–284 (1997) · Zbl 0840.05045 · doi:10.1016/0166-218X(94)00058-L
[22] Li W.W.: Character sums and abelian Ramanujan graphs. J. Number Theory 41, 199–217 (1992) · Zbl 0760.11040 · doi:10.1016/0022-314X(92)90120-E
[23] Li W.W., Meemark Y.: Ramanujan graphs on cosets of PGL 2 (F q ). Finite Fields Their Appl. 11(3), pp. 511–543 · Zbl 1075.05053
[24] MacWilliams F.J., Sloane N.J.A.: The theory of error-correcting codes. North Holland (1998). · Zbl 0369.94008
[25] Niho Y.: Multi-valued cross-correlation functions between two maximal linear recursive sequences. Ph.D. dissetrtation, Unvi. Southern California, Los Angeles, CA (1972).
[26] Payne S.E., Thas J.A.: Finite Generalized Quadrangles, 2nd edn. European Mathematical Society, April 15 (2009). · Zbl 1247.05047
[27] Rosenthal J., Vontobel P.O.: Construction of LDPC codes using ramanujan graphs and ideas from margulis. Allerton Conference (2000).
[28] Sarnak P.: What is. an Expander. Notices AMS 51(7), 762–763 (2004) · Zbl 1161.05341
[29] Sin P., Xiang Q.: On the dimensions of certain LDPC codes based on q-regular bipartite graphs. IEEE Trans. Inform. Theory 52, 3735–3737 (2006) · Zbl 1309.94172 · doi:10.1109/TIT.2006.878231
[30] Sipser M., Spielman D.A.: Expander codes. Codes and complexity. IEEE Trans. Inform. Theory 42(6), part 1, 1710–1722 (1996). · Zbl 0943.94543
[31] Spielman D.A.: Linear-time encodable and decodable error-correcting codes. IEEE Trans. Inform. Theory 42(6), 1710–1722 (1996) · Zbl 0943.94544 · doi:10.1109/18.556668
[32] Tanner R.M.: Explicit concentrators from generalized N-gons. SIAM J. Discret. Appl. Math. 5, 287–329 (1984) · Zbl 0554.05045 · doi:10.1137/0605030
[33] Terras A.: Home page of Audrey Terras. http://math.ucsd.edu/\(\sim\)aterras .
[34] Tanner R.M.: Minimum-distance bounds by graph analysis. IEEE Trans. Inform. Theory 47(2), 808–821 (2001) · Zbl 1002.94034 · doi:10.1109/18.910591
[35] Vanderndriessche P.: Some low-density parity-check codes derived from finite geometries. Des. Codes Cryptogr. 54(3), 287–297 (2010) · Zbl 1185.05033 · doi:10.1007/s10623-009-9324-9
[36] Wang C.: Analysis of finite-length low-density parity-check codes. Thesis, Pen State University, USA (2010).
[37] Zemor G.: On expander codes. IEEE Trans. Inform. Theory IT-47(2), 835–837 (2001) · Zbl 1021.94025 · doi:10.1109/18.910593
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.