Eigenvalues of subgraphs of the cube

DOI10.1016/J.EJC.2017.12.007MaRDI QIDQ1746572zbMATH OpenOpenAlexFDO

Authors Béla Bollobás, Jonathan Lee, Shoham Letzter

Publication date 25 April 2018

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

largest eigenvalue of subgraphs of a hypercube

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Extremal problems in graph theory (05C35)

Abstract: We consider the problem of maximising the largest eigenvalue of subgraphs of the hypercube $Q_d$ of a given order. We believe that in most cases, Hamming balls are maximisers, and our results support this belief. We show that the Hamming balls of radius $o(d)$ have largest eigenvalue that is within $1+o(1)$ of the maximum value. We also prove that Hamming balls with fixed radius maximise the largest eigenvalue exactly, rather than asymptotically, when $d$ is sufficiently large. Our proofs rely on the method of compressions.

Recommendations

• On the largest eigenvalue of a random subgraph of the hypercube
• On induced subgraphs of the Hamming graph
• Induced subgraph and eigenvalues of some signed graphs
• On induced subgraphs of the cube
• Bounding the size of square-free subgraphs of the hypercube

Cites work

• scientific article; zbMATH DE number 3968623 (Why is no real title available?)
• scientific article; zbMATH DE number 740754 (Why is no real title available?)
• scientific article; zbMATH DE number 5807 (Why is no real title available?)
• scientific article; zbMATH DE number 3214389 (Why is no real title available?)
• scientific article; zbMATH DE number 3296361 (Why is no real title available?)
• scientific article; zbMATH DE number 3349875 (Why is no real title available?)
• A bound on the spectral radius of graphs with \(e\) edges
• A note on the edges of the n-cube
• Bounds of eigenvalues of graphs
• Bounds on graph eigenvalues
• Bounds on graph eigenvalues. I
• Bounds on graph eigenvalues. II
• Bounds on graph spectra
• Eigenvalues of neutral networks: interpolating between hypercubes
• Extrema of graph eigenvalues
• Generalized Alon--Boppana Theorems and Error-Correcting Codes
• Graphs with least eigenvalue \(-2\): ten years on
• Isoperimetric inequalities for faces of the cube and the grid
• On the distribution of the maximum eigenvalues of graphs
• On the largest eigenvalue of non-regular graphs
• On the spectral radius of (0,1)-matrices
• Optimal Assignments of Numbers to Vertices
• Optimal numberings and isoperimetric problems on graphs
• Some eigenvalue properties in graphs (conjectures of Graffiti -- II)
• The second largest eigenvalue of a tree
• Walks and the spectral radius of graphs
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators

Cited in

(13)

• Matrix Cubes Parameterized by Eigenvalues
• The maximum spectral radius of graphs without friendship subgraphs
• Spectral analysis of the quantum random energy model
• The spectral even cycle problem
• On the spectral radius of minimally 2-(edge)-connected graphs with given size
• The spectral radius of graphs with no odd wheels
• Eigenvalues of neutral networks: interpolating between hypercubes
• A Spectral Erdős-Sós Theorem
• Some results on \(\{K_2, C_{2i + 1} : i \geq 1\}\)-factor in a graph
• Ordering graphs with given size by their signless Laplacian spectral radii
• Three conjectures in extremal spectral graph theory
• On the largest eigenvalue of a random subgraph of the hypercube
• Spectral Turán problems for intersecting even cycles

This page was built for publication: Eigenvalues of subgraphs of the cube

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