×

zbMATH — the first resource for mathematics

A lower bound for the discriminant of polynomials related to Chebyshev polynomials. (English) Zbl 1472.05158
The discriminant of a polynomial \(f=a\prod_{i=0}^m (x-\alpha_i)\) is defined by \[D(f)=a^{2m-2}\prod_{1\leq i<j\leq m} (\alpha_j-\alpha_i)^2.\] The discriminant is a useful tool to get information about the roots of a high-degree polynomial.
In this paper, the author gives a lower bound for the discriminant of the polynomials \(\{G_{k,i}\}\) defined by \(G_{k,0}(x)=1\), \(G_{k,1}(x)=x+1\) and then recursively \[G_{k,i+2}(x)=xG_{k,i+1}(x)-(k-1)G_{k,i}(x).\]
These polynomials have been used for the study of graphs and their girth (this is the length of the shortest circuit in the graph), specially due to its relation with the Moore Bound \[M_{d,k}=\begin{cases} 1+d\frac{(d-1)^{k-1}-1}{d-2}& d>2\\ 2k+1& d=2 \end{cases},\] which relates the degree, the order, the diameter and the girth of a graph. The discriminant of these polynomials have been used to prove the existence of graphs with certain degree or girth as in [C. Delorme and G. Pineda-Villavicencio, Electron. J. Comb. 17, No. 1, Research Paper R143, 25 p. (2010; Zbl 1204.05043)].
While all of this is addressed in the second section of the paper and the author suggests a path to proof his main result in a graph-theoretical way, most of the document is devoted to proof the result in a more elementary way. The main idea is to use orthogonality of some polynomials related to \(\{G_{k,i}\}\) and from there stablish a relation through simple inequalities with the discriminant of \(G_{k,d}\). While the notation could be a little heavy, the results are quite simple to follow, leading to the following bound for the discriminant: \[D(G_{k,d})>d^d(k-2)\left[\sqrt{k(k-1)^2-2}\right]^{d-2}.\]
MSC:
05E30 Association schemes, strongly regular graphs
05C12 Distance in graphs
05C07 Vertex degrees
33C45 Orthogonal polynomials and functions of hypergeometric type (Jacobi, Laguerre, Hermite, Askey scheme, etc.)
42C05 Orthogonal functions and polynomials, general theory of nontrigonometric harmonic analysis
Citations:
Zbl 1204.05043
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Andrews, E.; Askey, R.; Roy, R., Special Functions (1999), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0920.33001
[2] Apostol, M., The resultants of the cyclotomic polynomials \(F_m ( a x )\) and \(F_n ( b x )\), Math. Comp., 29, 1-6 (1975) · Zbl 0298.12001
[3] Biggs, N. L., Algebraic Graph Theory (1993), Cambridge University Press: Cambridge University Press Great Britain
[4] Brouwer, A. E.; Cohen, A. M.; Neumaier, A., Distance Regular Graphs (1989), Springer-Verlag: Springer-Verlag Berlin · Zbl 0747.05073
[5] Dalfó, C., A survey on the missing Moore graph, Linear Algebra Appl., 569, 1-14 (2019) · Zbl 1411.05155
[6] Delorme, C.; Villavicencio, G. P., On graphs with cyclic defect or excess, Electron. J. Combin., 17, R143 (2010) · Zbl 1204.05043
[7] Dilcher, K.; Stolarsky, K. B., Resultants and discriminants of Chebyshev and related polynomials, Trans. Amer. Math. Soc., 357, 965-981 (2004) · Zbl 1067.12001
[8] Fiol, M. A.; Gago, S.; Garriga, E., A simple proof of the spectral excess theorem for distance-regular graphs, Linear Algebra Appl., 432, 2418-2422 (2010) · Zbl 1221.05112
[9] Fiol, M. A.; Garriga, E., From local adjacency polynomials to locally pseudo-distance-regular graphs, J. Combin. Theory Ser. B, 71, 162-183 (1997) · Zbl 0888.05056
[10] Fiol, M. A.; Garriga, E.; Yebra, J. L.A., Locally pseudo-regular graphs, J. Combin. Theory B, 68, 179-205 (1996) · Zbl 0861.05064
[11] Fiol, M. A.; Penjić, S., On a version of the spectral excess theorem, Electr. J. Graph Theory Appl., 8, 2, 391-400 (2020)
[12] Gelfand, M.; Kapranov, M. M.; Zelevinsky, A. V., Discriminants, Resultants, and Multidimensional Determinants (1994), Birkhuser Boston: Birkhuser Boston Boston · Zbl 0827.14036
[13] Hoffman, A. J.; Singleton, R. R., On moore graphs with diameter 2 and 3, IBM J. Res. Dev., 4, 497-504 (1960) · Zbl 0096.38102
[14] Mahler, K., An inequality for the discriminant of a polynomial, Michigan Math. J., 11, 257-262 (1964) · Zbl 0135.01702
[15] Miller, M.; Širáň, J., Moore graphs and beyond: A survey of the degree/diameter problem, Electron. J. Combin., 14 (2013), Dynamic Survey
[16] Nikiforov, A. F.; Suslov, S. K.; Uvarov, V. B., Classical Orthogonal Polynomials of a Discrete Variable (1991), Springer-Verlag: Springer-Verlag Berlin · Zbl 0743.33001
[17] Rivlin, T. J., Chebyshev Polynomials (1990), Wiley: Wiley New York
[18] Singleton, R. C., On minimal graphs of maximum even girth, J. Combin. Theory, 1, 3, 306-332 (1966) · Zbl 0168.44703
[19] Szegö, G., Orthogonal Polynomials (1975), American Mathematical Society: American Mathematical Society Provi-dence, Rhode Island · JFM 61.0386.03
[20] van Dam, E. R., The spectral excess theorem for distance-regular graphs: a global (over)view, Electron. J. Combin., 15, 1, R129 (2008) · Zbl 1180.05130
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.