×

zbMATH — the first resource for mathematics

Spectra of regular graphs and hypergraphs and orthogonal polynomials. (English) Zbl 0864.05072
From the introduction: We recast the theme of the article by one of us [the second author, J. Comb. Theory, Ser. B, 56, No. 2, 239-249 (1992; Zbl 0723.05084)] in greater detail and with more caution, and also extend the results to regular hypergraphs and regular bigraphs. The central idea is to approximate the distribution of the spectrum of such a (hyper-, bi-)graph by the distribution of the continuous spectrum of its ‘universal cover’. This is made more precise by considering polynomials with respect to the measures arising from both spectra. The zeroes of these polynomials are then used to estimate the non-trivial extremal eigenvalues as well as the overall distribution of the spectrum of the finite graph of given girth. An important technical difference in contrast with the previous article is the use of variations of the measures arising from spectra; these are the usual measures multiplied by suitable factors designed to eliminate trivial eigenvalues. The zeroes of polynomials orthogonal with respect to these measures enable us to derive non-trivial bounds for extremal non-trivial eigenvalues. Our estimates of eigenvalues are tight in some cases; for instance, they are satisfied by Biggs graphs in the case of regular graphs, and by generalized polygons in the case of hypergraphs. Our results on spectra of regular graphs with given girth have an application to the distribution of eigenvalues of Hecke operators acting on the space of weight 2 cusp forms for certain congruence subgroup.

MSC:
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C65 Hypergraphs
05E35 Orthogonal polynomials (combinatorics) (MSC2000)
PDF BibTeX XML Cite
Full Text: DOI