B. Bollobás

J. Lee

S. Letzter

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

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

Eigenvalues of subgraphs of the cube

Hypercube eigenvalues

Next generation structures and materials are key to aerospace, the built environment and exploring space. Hierarchical materials, fractal structures, and polydisperse systems offer dramatic gains in efficiency. Advances in 3D printing and self-assembly mean that these novel technologies can be practically manufactured.

Extreme materials

Silicon-based electronic computing is hitting energetic and technological barriers, and quantum computing remains a theoretical challenge of the future. To maintain an exponential increase in computing power, we require alternative frameworks. Two which we are studying are memristors and photonic computing.

Low-energy computing

Information science underpins modern society. Quantum information science is creating the next generation of information technology, where effects like superposition and entanglement are exploited to envisage qualitatively new technologies. This field also gives an alternative perspective on physics, wherein information takes centre stage.

Quantum information

Innovation is to organizations what evolution is to organisms: it is how organisations adapt to changes in the environment and improve. New mathematical models of component recombination and the building blocks of economic complexity offer fundamental insights into how firms, countries and technologies develop.

Science of innovation

The global behaviour of local processes depends on the geometry of their underlying space. Studying processes on ideal graphs and on irregular networks derived from real data uncovers surprising behaviour in biological, social and financial systems. The tools of this field include spectral, replica, community and combinatoric techniques.

Graph theory

Institutional risk originates from ordinary economic uncertainties. But when these risks propagate across inter-connected institutions, internal amplification can lead to dramatic exposures. These systemic risks can be mitigated by applying ideas from cascading failures, diversification and extreme value theory.