Minimum supports of eigenfunctions of Johnson graphs

DOI10.1016/J.DISC.2018.04.018zbMATH Open1388.05119arXiv1706.03987OpenAlexW2963410367MaRDI QIDQ1637129FDOQ1637129

Authors: Konstantin Vorob'ev, Alexandr Valyuzhenich, Ivan Yu. Mogilnykh 

Publication date: 7 June 2018

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: We study the weights of eigenvectors of the Johnson graphs $J(n,w)$. For any $iin1,ldots,w$ and sufficiently large $n,ngeqn(i,w)$ we show that an eigenvector of $J(n,w)$ with the eigenvalue $lambd{a}_i=(n-w-i)(w-i)-i$ has at least $2^i{(}_{w-i}^{n-2i})$ nonzeros and obtain a characterization of eigenvectors that attain the bound.

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

Recommendations

• MMS-type problems for Johnson scheme
• Minimum supports of functions on the Hamming graphs with spectral constraints
• Minimum supports of eigenfunctions in bilinear forms graphs
• On the minimum supports of some eigenfunctions in the Doob graphs
• The smallest eigenvalues of Hamming graphs, Johnson graphs and other distance-regular graphs with classical parameters

zbMATH Keywords

Johnson schemeeigenspacesupport of a function

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On the number of inequivalent steiner triple systems
• Title not available (Why is that?)
• Perfect Single Error-Correcting Codes in the Johnson Scheme
• Completely regular designs
• To the theory of \(q\)-ary Steiner and other-type trades
• On one transformation of Steiner quadruple systems \(S(\upsilon , 4, 3)\)
• Minimum supports of eigenfunctions of Hamming graphs
• On the structure of (v,k,t) trades
• Induced perfect colorings
• Combinatorial designs and algebras
• Combinatorial \(S_ n\)-modules as codes
• On the support size of null designs of finite ranked posets
• Minimal null designs of subspace lattices over finite fields

Cited In (14)

• Minimum supports of functions on the Hamming graphs with spectral constraints
• The EKR-module property of pseudo-Paley graphs of square order
• Eigenfunctions and minimum 1-perfect bitrades in the Hamming graph
• On reduction for eigenfunctions of graphs
• \(L_{\infty}\) norm minimization for nowhere-zero integer eigenvectors of the block graphs of Steiner triple systems and Johnson graphs
• Optimal functions with spectral constraints in hypercubes
• Embedding of eigenfunctions of the Johnson graph into eigenfunctions of the Hamming graph
• Inclusion matrices for rainbow subsets
• MMS-type problems for Johnson scheme
• Eigenfunctions supports of minimum cardinality in cubical distance-regular graphs
• On the minimum supports of some eigenfunctions in the Doob graphs
• Minimum supports of eigenfunctions in bilinear forms graphs
• On reconstruction of eigenfunctions of Johnson graphs
• Minimum supports of eigenfunctions of graphs: a survey

This page was built for publication: Minimum supports of eigenfunctions of Johnson graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1637129)