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 ³

¹ University of Delaware Department of Mathematical Sciences Ewing Hall Newark, DE 19716-2553, USA
² School of Mathematical Sciences University of Science and Technology of China Wen-Tsun Wu Key Laboratory of the Chinese Academy of Sciences Hefei, Anhui, China
³ Aichi University of Education 1 Hirosawa, Igaya-cho, Kariya Aichi 448-8542, Japan

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-01
Revised: 2019-03-03
Accepted: 2019-03-03
Published online: 2019-12-03

MR Zbl

DOI: 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.

Author's affiliations:

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

¹ University of Delaware Department of Mathematical Sciences Ewing Hall Newark, DE 19716-2553, USA
² School of Mathematical Sciences University of Science and Technology of China Wen-Tsun Wu Key Laboratory of the Chinese Academy of Sciences Hefei, Anhui, China
³ Aichi University of Education 1 Hirosawa, Igaya-cho, Kariya Aichi 448-8542, Japan

License:

CC-BY 4.0

Copyrights: The authors retain unrestricted copyrights and publishing rights

@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},
     zbl = {1428.05187},
     mrnumber = {4049844},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.71/}
}

TY  - JOUR
AU  - Cioabă, Sebastian M.
AU  - Koolen, Jack H.
AU  - Nozaki, Hiroshi
TI  - A spectral version of the Moore problem for bipartite regular graphs
JO  - Algebraic Combinatorics
PY  - 2019
SP  - 1219
EP  - 1238
VL  - 2
IS  - 6
PB  - MathOA foundation
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.71/
DO  - 10.5802/alco.71
LA  - en
ID  - ALCO_2019__2_6_1219_0
ER  -

%0 Journal Article
%A Cioabă, Sebastian M.
%A Koolen, Jack H.
%A Nozaki, Hiroshi
%T A spectral version of the Moore problem for bipartite regular graphs
%J Algebraic Combinatorics
%D 2019
%P 1219-1238
%V 2
%N 6
%I MathOA foundation
%U https://alco.centre-mersenne.org/articles/10.5802/alco.71/
%R 10.5802/alco.71
%G en
%F 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/articles/10.5802/alco.71/

References
Cited by

[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 | DOI | MR | Zbl

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

[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 | DOI | MR

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | Zbl

[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)], 18, Springer-Verlag, Berlin, 1989, xviii+495 pages | DOI | MR | Zbl

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

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

[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 | DOI | MR | Zbl

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

[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 | DOI | MR | Zbl

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

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

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

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

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

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

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | Zbl

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

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

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

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

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

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

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

Cited by Sources: