Eigenvalues of subgraphs of the cube

Hamming balls, subgraphs of the hypercube, maximise the graph’s largest eigenvalue exactly when the dimension of the cube is large enough.

European Journal of Combinatorics 70, 125 (2018)

B. Bollobás, J. Lee, S. Letzter

Eigenvalues of subgraphs of the cube

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..

More in Spectre of hypercubes

  • Forum of Mathematics, Sigma

    Erdős-Ko-Rado theorem analogue

    A random analogue of the Erdős-Ko-Rado theorem sheds light on its stability in an area of parameter space which has not yet been explored.

  • Journal of Physics A

    Spin systems on Bethe lattices

    Exact equations for the thermodynamic quantities of lattices made of d-dimensional hypercubes are obtainable with the Bethe-Peierls approach.

  • Discrete Mathematics

    Eigenvalues of neutral networks

    The principal eigenvalue of small neutral networks determines their robustness, and is bounded by the logarithm of the number of vertices.