Large regular bipartite graphs with median eigenvalue 1. (English) Zbl 1286.05087
Summary: A recent result of one of the authors says that every connected subcubic bipartite graph that is not isomorphic to the Heawood graph has at least one, and in fact a positive proportion of its eigenvalues in the interval \([-1,1]\). We construct an infinite family of connected cubic bipartite graphs which have no eigenvalues in the open interval \((-1,1)\), thus showing that the interval \([-1,1]\) cannot be replaced by any smaller symmetric subinterval even when allowing any finite number of exceptions.
Similar examples with vertices of larger degrees are considered and it is also shown that their eigenvalue distribution has somewhat unusual properties. By taking limits of these graphs, we obtain examples of infinite vertex-transitive \(r\)-regular graphs for every \(r\geqslant 3\), whose spectrum consists of points \({\pm}1\) together with intervals \([r-2,r]\) and \([-r,-r+2]\). These examples shed some light onto a question communicated by Daniel Lenz and Matthias Keller with motivation in relation to the Baum-Connes Conjecture.
Similar examples with vertices of larger degrees are considered and it is also shown that their eigenvalue distribution has somewhat unusual properties. By taking limits of these graphs, we obtain examples of infinite vertex-transitive \(r\)-regular graphs for every \(r\geqslant 3\), whose spectrum consists of points \({\pm}1\) together with intervals \([r-2,r]\) and \([-r,-r+2]\). These examples shed some light onto a question communicated by Daniel Lenz and Matthias Keller with motivation in relation to the Baum-Connes Conjecture.
References:
| [1] | Alon, N.; Milman, V. D., \( \lambda_1\), isoperimetric inequalities for graphs, and superconcentrators, J. Combin. Theory Ser. B, 38, 1, 73-88 (1985) · Zbl 0549.05051 |
| [2] | Brouwer, Andries E.; Haemers, Willem H., Spectra of Graphs, Universitext (2012), Springer: Springer New York · Zbl 1231.05001 |
| [3] | Fowler, Patrick W.; Pisanski, Tomaž, HOMO-LUMO maps for chemical graphs, MATCH Commun. Math. Comput. Chem., 64, 2, 373-390 (2010) · Zbl 1265.05574 |
| [4] | Fowler, Patrick W.; Pisanski, Tomaž, HOMO-LUMO maps for fullerenes, Acta Chim. Slov., 57, 513-517 (2010) · Zbl 1265.05574 |
| [5] | Higson, N.; Lafforgue, V.; Skandalis, G., Counterexamples to the Baum-Connes conjecture, Geom. Funct. Anal., 12, 2, 330-354 (2002) · Zbl 1014.46043 |
| [6] | Hoory, Shlomo; Linial, Nathan; Wigderson, Avi, Expander graphs and their applications, Bull. Amer. Math. Soc. (N.S.), 43, 4, 439-561 (2006), (electronic) · Zbl 1147.68608 |
| [8] | Mohar, Bojan, Median eigenvalues of bipartite subcubic graphs, Combin. Probab. Comput. (2014), in press · Zbl 1372.05129 |
| [9] | Mohar, Bojan, The spectrum of an infinite graph, Linear Algebra Appl., 48, 245-256 (1982) · Zbl 0502.05040 |
| [10] | Mohar, Bojan; Poljak, Svatopluk, Eigenvalues in combinatorial optimization, (Combinatorial and Graph-Theoretical Problems in Linear Algebra. Combinatorial and Graph-Theoretical Problems in Linear Algebra, Minneapolis, MN, 1991. Combinatorial and Graph-Theoretical Problems in Linear Algebra. Combinatorial and Graph-Theoretical Problems in Linear Algebra, Minneapolis, MN, 1991, IMA Vol. Math. Appl., vol. 50 (1993), Springer: Springer New York), 107-151 · Zbl 0806.90104 |
| [11] | Mohar, Bojan; Woess, Wolfgang, A survey on spectra of infinite graphs, Bull. Lond. Math. Soc., 21, 3, 209-234 (1989) · Zbl 0645.05048 |
| [12] | Schenker, Jeffrey H.; Aizenman, Michael, The creation of spectral gaps by graph decoration, Lett. Math. Phys., 53, 3, 253-262 (2000) · Zbl 0990.47006 |
| [13] | Valette, Alain, Introduction to the Baum-Connes Conjecture, Lectures Math. ETH Zürich (2002), Birkhäuser Verlag: Birkhäuser Verlag Basel, From notes taken by Indira Chatterji. With an appendix by Guido Mislin · Zbl 1136.58013 |
| [14] | Woess, Wolfgang, Random Walks on Infinite Graphs and Groups, Cambridge Tracts in Math., vol. 138 (2000), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0951.60002 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
