Eigenvalues of subgraphs of the cube

DOI10.1016/J.EJC.2017.12.007zbMATH Open1384.05106arXiv1605.06360OpenAlexW2963490393MaRDI QIDQ1746572FDOQ1746572

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)

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.

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

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

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)

Cites Work

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

Cited In (13)

• The spectral radius of graphs with no odd wheels
• A Spectral Erdős-Sós Theorem
• On the largest eigenvalue of a random subgraph of the hypercube
• Spectral analysis of the quantum random energy model
• The spectral even cycle problem
• The maximum spectral radius of graphs without friendship subgraphs
• Matrix Cubes Parameterized by Eigenvalues
• Three conjectures in extremal spectral graph theory
• Spectral Turán problems for intersecting even cycles
• Eigenvalues of neutral networks: interpolating between hypercubes
• 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
• On the spectral radius of minimally 2-(edge)-connected graphs with given size

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)