The smallest eigenvalues of Hamming graphs, Johnson graphs and other distance-regular graphs with classical parameters

DOI10.1016/j.jctb.2018.04.005zbMath1397.05098arXiv1709.09011OpenAlexW2963664782WikidataQ129443275 ScholiaQ129443275MaRDI QIDQ1791705

Matt McGinnis, Ferdinand Ihringer, Sebastian M. Cioabă, Andries E. Brouwer

Publication date: 11 October 2018

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1709.09011

zbMATH Keywords

distance-regular graphassociation schemeJohnson graphHamming graphsmallest eigenvaluemax-cut

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Distance in graphs (05C12)

Related Items

Treewidth of the generalized Kneser graphs, Boolean degree 1 functions on some classical association schemes, Eigenvalues of Cayley graphs, Distance-regular graphs with diameter 3 and eigenvalue \(a_2 - c_3\), Spectral properties of the eccentricity matrix of graphs, Optimal and extremal graphical designs on regular graphs associated with classical parameters, Lower bound on the minimum number of edges in subgraphs of Johnson graphs, High dimensional Hoffman bound and applications in extremal combinatorics, Cameron-Liebler sets of \(k\)-spaces in \(\mathrm{PG}(n,q)\), The second eigenvalue of some normal Cayley graphs of highly transitive groups, Unnamed Item, Harmonic index \(t\)-designs in the Hamming scheme for arbitrary \(q\), Harmonic index \(t\)-designs in the Hamming scheme for arbitrary \(q\), Some observations on the smallest adjacency eigenvalue of a graph, The least Euclidean distortion constant of a distance-regular graph, Spectrum of Johnson graphs, On the eigenvalues of Grassmann graphs, bilinear forms graphs and Hermitian forms graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Zeros of generalized Krawtchouk polynomials
• Spectra of graphs
• New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph
• Forbidding just one intersection
• The Radon transform on \({\mathbb{Z}}^ k_ 2\)
• Reduction of the number of associate classes of hypercubic association schemes
• A partially ordered set and q-Krawtchouk polynomials
• Association schemes and t-designs in regular semilattices
• Alternating bilinear forms over GF(q)
• The tail of the hypergeometric distribution
• Bilinear forms over a finite field, with applications to coding theory
• On a characterization of bilinear forms graphs
• Large \(\{0,1,\ldots,t\}\)-cliques in dual polar graphs
• On integral zeros of Krawtchouk polynomials
• The eigenspaces of the Bose-Mesner algebras of the association schemes corresponding to projective spaces and polar spaces
• More zeros of Krawtchouk polynomials
• A Rank-Metric Approach to Error Control in Random Network Coding
• Some q-Krawtchouk Polynomials on Chevalley Groups
• 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} )$
• On the Shannon capacity of a graph
• How Good is the Goemans--Williamson MAX CUT Algorithm?
• On a quartic diophantine equation
• Bipartite Subgraphs and the Smallest Eigenvalue
• Spherically Punctured Biorthogonal Codes