Eigenvalues of neutral networks: Interpolating between hypercubes

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

Discrete Mathematics 339, 1283 (2016)

T. Reeves, R. Farr, J. Blundell, A. Gallagher, T. Fink

Eigenvalues of neutral networks: Interpolating between hypercubes
Eigenvalues of neutral networks: Interpolating between hypercubes
Eigenvalues of neutral networks: Interpolating between hypercubes
Eigenvalues of neutral networks: Interpolating between hypercubes
Eigenvalues of neutral networks: Interpolating between hypercubes
Eigenvalues of neutral networks: Interpolating between hypercubes
Eigenvalues of neutral networks: Interpolating between hypercubes
Eigenvalues of neutral networks: Interpolating between hypercubes
Eigenvalues of neutral networks: Interpolating between hypercubes
Eigenvalues of neutral networks: Interpolating between hypercubes
Eigenvalues of neutral networks: Interpolating between hypercubes
Eigenvalues of neutral networks: Interpolating between hypercubes
Eigenvalues of neutral networks: Interpolating between hypercubes
Eigenvalues of neutral networks: Interpolating between hypercubes
Eigenvalues of neutral networks: Interpolating between hypercubes
Eigenvalues of neutral networks: Interpolating between hypercubes

A neutral network is a subgraph of a Hamming graph, and its principal eigenvalue determines its robustness: the ability of a population evolving on it to withstand errors. Here we consider the most robust small neutral networks: the graphs that interpolate pointwise between hypercube graphs of consecutive dimension (the point, line, line and point in the square, square, square and point in the cube, and so on). We prove that the principal eigenvalue of the adjacency matrix of these graphs is bounded by the logarithm of the number of vertices, and we conjecture an analogous result for Hamming graphs of alphabet size greater than two.

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.

  • European Journal of Combinatorics

    Hypercube eigenvalues

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

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