×

zbMATH — the first resource for mathematics

The smallest eigenvalues of Hamming graphs, Johnson graphs and other distance-regular graphs with classical parameters. (English) Zbl 1397.05098
Summary: We prove a conjecture by E. R. van Dam and R. Sotirov [Linear Algebra Appl. 488, 216–234 (2016; Zbl 1326.05089)] on the smallest eigenvalue of (distance-\(j\)) Hamming graphs and a conjecture by Karloff on the smallest eigenvalue of (distance-\(j\)) Johnson graphs. More generally, we study the smallest eigenvalue and the second largest eigenvalue in absolute value of the graphs of the relations of classical \(P\)- and \(Q\)-polynomial association schemes.

MSC:
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C12 Distance in graphs
Citations:
Zbl 1326.05089
PDF BibTeX XML Cite
Full Text: DOI arXiv Link
References:
[1] Alon, N.; Sudakov, B., Bipartite subgraphs and the smallest eigenvalue, Combin. Probab. Comput., 9, 1-12, (2000) · Zbl 0945.05041
[2] Brouwer, A. E.; Cohen, A. M.; Neumaier, A., Distance-regular graphs, (1989), Springer Heidelberg · Zbl 0747.05073
[3] Brouwer, A. E.; Haemers, W. H., Spectra of graphs, (2012), Springer New York · Zbl 1231.05001
[4] Chihara, L.; Stanton, D., Zeros of generalized krawtchouk polynomials, J. Approx. Theory, 60, 43-57, (1990) · Zbl 0693.33005
[5] Chvátal, V., The tail of the hypergeometric distribution, Discrete Math., 25, 285-287, (1979) · Zbl 0396.60016
[6] van Dam, E.; Sotirov, R., New bounds for the MAX-k-cut and chromatic number of a graph, Linear Algebra Appl., 488, 216-234, (2016) · Zbl 1326.05089
[7] Delsarte, P., An algebraic approach to the association schemes of coding theory, Philips Res. Rep., Suppl., 10, (1973), vi+97 pp · Zbl 1075.05606
[8] Delsarte, P., Properties and applications of the recurrence \(F(i + 1, k + 1, n + 1) = q^{k + 1} F(i, k + 1, n) - q^k F(i, k, n)\), SIAM J. Appl. Math., 31, 262-270, (1976) · Zbl 0353.42010
[9] Delsarte, P., Association schemes and t-designs in regular semilattices, J. Combin. Theory Ser. A, 20, 230-243, (1976) · Zbl 0342.05020
[10] Delsarte, P., Bilinear forms over a finite field with applications to coding theory, J. Combin. Theory Ser. A, 25, 226-241, (1978) · Zbl 0397.94012
[11] Delsarte, P.; Goethals, J. M., Alternating bilinear forms over \(G F(q)\), J. Combin. Theory Ser. A, 19, 26-50, (1975) · Zbl 0343.05015
[12] Diaconis, P.; Graham, R. L., The Radon transform on \(\mathbb{Z}_2^k\), Pacific J. Math., 118, 323-345, (1985) · Zbl 0581.43001
[13] Dumer, I.; Kapralova, O., Spherically punctured biorthogonal codes, IEEE Trans. Inform. Theory, 59, 6010-6017, (2013) · Zbl 1364.94596
[14] Eisfeld, J., The eigenspaces of the Bose-mesner algebras of the association schemes corresponding to projective spaces and polar spaces, Des. Codes Cryptogr., 17, 129-150, (1999) · Zbl 0970.51008
[15] Habsieger, L.; Stanton, D., More zeros of krawtchouk polynomials, Graphs Combin., 2, 163-172, (1993) · Zbl 0805.33008
[16] Hanrot, G., Résolution effective d’équations diophantiennes: algorithmes et applications, (1997), Université Bordeaux I, Thèse
[17] Ihringer, F.; Metsch, K., Large \(\{0, 1, \ldots, t \}\)-cliques in dual polar graphs, J. Combin. Theory Ser. A, 154, 285-322, (2018) · Zbl 1373.05139
[18] Frankl, P.; Füredi, Z., Forbidding just one intersection, J. Combin. Theory Ser. A, 39, 160-176, (1985) · Zbl 0573.05001
[19] Kageyama, S.; Saha, G. M.; Das, A. D., Reduction of the number of association classes of hypercubic association schemes, Ann. Inst. Statist. Math., 30, 115-123, (1978) · Zbl 0443.62065
[20] Karloff, H., How good is the goemans-williamson MAX cut algorithm?, SIAM J. Comput., 20, 336-350, (1999) · Zbl 0942.90033
[21] Khot, S.; Minzer, D.; Safra, M., Pseudorandom sets in Grassmann graph have near-perfect expansion, (2018), ECCC, Technical Report TR18-006
[22] Krasikov, I.; Litsyn, S., On integral zeros of krawtchouk polynomials, J. Combin. Theory Ser. A, 74, 71-99, (1996) · Zbl 0853.33008
[23] Lovász, L., On the Shannon capacity of a graph, IEEE Trans. Inform. Theory, 25, 1-7, (1979) · Zbl 0395.94021
[24] Metsch, K., On a characterization of bilinear forms graphs, European J. Combin., 20, 293-306, (1999) · Zbl 0923.05050
[25] Schmidt, K.-U., Hermitian rank distance codes, Des. Codes Cryptogr., (2017), also available at
[26] Silva, D.; Kschischang, F. R.; Kötter, R., A rank-metric approach to error control in random network coding, IEEE Trans. Inform. Theory, 54, 3951-3967, (2008) · Zbl 1318.94119
[27] Skala, M., Hypergeometric tail inequalities: ending the insanity, (Nov. 2013)
[28] Stanton, D., Some q-krawtchouk polynomials on Chevalley groups, Amer. J. Math., 102, 625-662, (1980) · Zbl 0448.33019
[29] Stanton, D., A partially ordered set and q-krawtchouk polynomials, J. Combin. Theory Ser. A, 30, 276-284, (1981) · Zbl 0502.05013
[30] Stroeker, R. J.; de Weger, B. M.M., On a quartic Diophantine equation, Proc. Edinb. Math. Soc., 39, 97-114, (1996) · Zbl 0861.11020
[31] Stroeker, R. J.; de Weger, B. M.M., On integral zeroes of binary krawtchouk polynomials, Nieuw Arch. Wiskd., 17, 175-186, (1999) · Zbl 1069.33010
[32] Vanhove, F., Incidence geometry from an algebraic graph theory point of view, (2011), University of Ghent, PhD thesis
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.