A spectral version of the Moore problem for bipartite regular graphs

Cioabă, Sebastian M.; Koolen, Jack H.; Nozaki, Hiroshi

doi:10.5802/alco.71

Cioabă, Sebastian M.; Koolen, Jack H.; Nozaki, Hiroshi

Algebraic Combinatorics, Volume 2 (2019) no. 6, pp. 1219-1238.

Abstract

Let $b (k, θ)$ be the maximum order of a connected bipartite $k$ -regular graph whose second largest eigenvalue is at most $θ$ . In this paper, we obtain a general upper bound for $b (k, θ)$ for any $0 \leq θ < 2 \sqrt{k - 1}$ . Our bound gives the exact value of $b (k, θ)$ whenever there exists a bipartite distance-regular graph of degree $k$ , second largest eigenvalue $θ$ , diameter $d$ and girth $g$ such that $g \geq 2 d - 2$ . For certain values of $d$ , there are infinitely many such graphs of various valencies $k$ . However, for $d = 11$ or $d \geq 15$ , we prove that there are no bipartite distance-regular graphs with $g \geq 2 d - 2$ .

Received: 2018-05-02
Revised: 2019-03-04
Accepted: 2019-03-04
Published online: 2019-12-04

MR 4049844 | Zbl 1428.05187

DOI: https://doi.org/10.5802/alco.71
Classification: 05B25, 05C35, 05C50, 05E30, 42C05, 94B65
Keywords: second eigenvalue, bipartite regular graph, bipartite distance-regular graph, expander, linear programming bound.

@article{ALCO_2019__2_6_1219_0,
     author = {Cioab\u a, Sebastian M. and Koolen, Jack H. and Nozaki, Hiroshi},
     title = {A spectral version of the Moore problem for bipartite regular graphs},
     journal = {Algebraic Combinatorics},
     pages = {1219--1238},
     publisher = {MathOA foundation},
     volume = {2},
     number = {6},
     year = {2019},
     doi = {10.5802/alco.71},
     mrnumber = {4049844},
     zbl = {1428.05187},
     language = {en},
     url = {alco.centre-mersenne.org/item/ALCO_2019__2_6_1219_0/}
}

Cioabă, Sebastian M.; Koolen, Jack H.; Nozaki, Hiroshi. A spectral version of the Moore problem for bipartite regular graphs. Algebraic Combinatorics, Volume 2 (2019) no. 6, pp. 1219-1238. doi : 10.5802/alco.71. https://alco.centre-mersenne.org/item/ALCO_2019__2_6_1219_0/

References

[1] Abiad, Aida; van Dam, Edwin R.; Fiol, Miquel Ángel Some spectral and quasi-spectral characterizations of distance-regular graphs, J. Combin. Theory Ser. A, Volume 143 (2016), pp. 1-18 | Article | MR 3519812 | Zbl 1342.05031

[2] Alon, Noga Eigenvalues and expanders, Combinatorica, Volume 6 (1986) no. 2, pp. 83-96 (Theory of computing (Singer Island, Fla., 1984)) | Article | MR 875835

[3] Alon, Noga; Milman, Vitali D. $λ_{1},$ isoperimetric inequalities for graphs, and superconcentrators, J. Combin. Theory Ser. B, Volume 38 (1985) no. 1, pp. 73-88 | Article | MR 782626

[4] Bannai, Eiichi; Ito, Tatsuro On the spectra of certain distance-regular graphs, J. Combin. Theory Ser. B, Volume 27 (1979) no. 3, pp. 274-293 | Article | MR 554295 | Zbl 0427.15005

[5] Bannai, Eiichi; Ito, Tatsuro On the spectra of certain distance-regular graphs. II, Quart. J. Math. Oxford Ser. (2), Volume 32 (1981) no. 4, pp. 389-411 | Article | MR 635588 | Zbl 0475.05059

[6] Bannai, Eiichi; Ito, Tatsuro Algebraic combinatorics. I: Association schemes, Mathematics lecture note series, The Benjamin/Cummings Publishing Co., Inc., Menlo Park, CA, 1984, xxiv+425 pages | MR 882540 | Zbl 0555.05019

[7] Brouwer, Andries E.; Cohen, Arjeh M.; Neumaier, Arnold Distance-regular graphs, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], Volume 18, Springer-Verlag, Berlin, 1989, xviii+495 pages | Article | MR 1002568 | Zbl 0747.05073

[8] Brouwer, Andries E.; Haemers, Willem H. Spectra of graphs, Universitext, Springer, New York, 2012, xiv+250 pages | Article | MR 2882891 | Zbl 1231.05001

[9] Chung, Fan R. K. Diameters and eigenvalues, J. Amer. Math. Soc., Volume 2 (1989) no. 2, pp. 187-196 | Article | MR 965008 | Zbl 0678.05037

[10] Cioabă, Sebastian M.; Koolen, Jack H.; Nozaki, Hiroshi; Vermette, Jason R. Maximizing the order of a regular graph of given valency and second eigenvalue, SIAM J. Discrete Math., Volume 30 (2016) no. 3, pp. 1509-1525 | Article | MR 3537002 | Zbl 1344.05086

[11] Cohn, Henry; Kumar, Abhinav Universally optimal distribution of points on spheres, J. Amer. Math. Soc., Volume 20 (2007) no. 1, pp. 99-148 | Article | MR 2257398 | Zbl 1198.52009

[12] Damerell, Robert Mark; Georgiacodis, Michael A. On the maximum diameter of a class of distance-regular graphs, Bull. London Math. Soc., Volume 13 (1981) no. 4, pp. 316-322 | Article | MR 620044 | Zbl 0457.05055

[13] Davidoff, Giuliana; Sarnak, Peter; Valette, Alain Elementary number theory, group theory, and Ramanujan graphs, London Mathematical Society Student Texts, Volume 55, Cambridge University Press, Cambridge, 2003, x+144 pages | Article | MR 1989434 | Zbl 1032.11001

[14] Fuglister, Frederick J. On generalized Moore geometries. I, Discrete Math., Volume 67 (1987) no. 3, pp. 249-258 | Article | MR 915950 | Zbl 0626.51006

[15] Fuglister, Frederick J. On generalized Moore geometries. II, Discrete Math., Volume 67 (1987) no. 3, pp. 259-269 | Article | MR 915950 | Zbl 0626.51006

[16] Geronimus, James On a set of polynomials, Ann. of Math. (2), Volume 31 (1930) no. 4, pp. 681-686 | Article | MR 1502972

[17] Harris, Lawrence A. Lagrange polynomials, reproducing kernels and cubature in two dimensions, J. Approx. Theory, Volume 195 (2015), pp. 43-56 | Article | MR 3339053 | Zbl 1314.41023

[18] Høholdt, Tom; Janwa, Heeralal Eigenvalues and expansion of bipartite graphs, Des. Codes Cryptogr., Volume 65 (2012) no. 3, pp. 259-273 | Article | MR 2988185 | Zbl 1254.05103

[19] Høholdt, Tom; Justesen, Jørn On the sizes of expander graphs and minimum distances of graph codes, Discrete Math., Volume 325 (2014), pp. 38-46 | Article | MR 3181231 | Zbl 1288.05070

[20] Hoory, Shlomo; Linial, Nathan; Wigderson, Avi Expander graphs and their applications, Bull. Amer. Math. Soc. (N.S.), Volume 43 (2006) no. 4, pp. 439-561 | Article | MR 2247919 | Zbl 1147.68608

[21] Hora, Akihito; Obata, Nobuaki Quantum probability and spectral analysis of graphs, Theoretical and Mathematical Physics, Springer, Berlin, 2007, xviii+371 pages (With a foreword by Luigi Accardi) | MR 2316893 | Zbl 1141.81005

[22] Koledin, Tamara; Stanić, Zoran Regular graphs with small second largest eigenvalue, Appl. Anal. Discrete Math., Volume 7 (2013) no. 2, pp. 235-249 | Article | MR 3135926 | Zbl 1313.05229

[23] Koledin, Tamara; Stanić, Zoran Reflexive bipartite regular graphs, Linear Algebra Appl., Volume 442 (2014), pp. 145-155 | Article | MR 3134359 | Zbl 1282.05125

[24] Li, Wen-Ch’ing Winnie; Solé, Patrick Spectra of regular graphs and hypergraphs and orthogonal polynomials, European J. Combin., Volume 17 (1996) no. 5, pp. 461-477 | Article | MR 1397154 | Zbl 0864.05072

[25] Marcus, Adam W.; Spielman, Daniel A.; Srivastava, Nikhil Interlacing families I: Bipartite Ramanujan graphs of all degrees, Ann. of Math. (2), Volume 182 (2015) no. 1, pp. 307-325 | Article | MR 3374962 | Zbl 1316.05066

[26] Miller, Mirka; Sirán, Jozef Moore graphs and beyond: A survey of the degree/diameter problem, Electron. J. Combin. (2005), 61 pages | Zbl 1079.05043

[27] Nozaki, Hiroshi Linear programming bounds for regular graphs, Graphs Combin., Volume 31 (2015) no. 6, pp. 1973-1984 | Article | MR 3417208 | Zbl 1332.90160

[28] Singleton, Robert On minimal graphs of maximum even girth, J. Combinatorial Theory, Volume 1 (1966) no. 3, pp. 306-332 | Article | MR 0201347 | Zbl 0168.44703

[29] Teranishi, Yasuo; Yasuno, Fumiko The second largest eigenvalues of regular bipartite graphs, Kyushu J. Math., Volume 54 (2000) no. 1, pp. 39-54 | Article | MR 1762790 | Zbl 0990.05095

ALGEBRAIC COMBINATORICS

About the Journal

Editorial Team

Author Guidelines

Submit a paper