Bollobás, B;
Lee, J;
Letzter, S;
(2018)
Eigenvalues of subgraphs of the cube.
European Journal of Combinatorics
, 70
pp. 125-148.
10.1016/j.ejc.2017.12.007.
Preview |
Text
cube-eigenvalues-6-oct-17.pdf - Accepted Version Download (460kB) | Preview |
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.
| Type: | Article |
|---|---|
| Title: | Eigenvalues of subgraphs of the cube |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1016/j.ejc.2017.12.007 |
| Publisher version: | https://doi.org/10.1016/j.ejc.2017.12.007 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher's terms and conditions. |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics |
| URI: | https://discovery-pp.ucl.ac.uk/id/eprint/10107277 |
Archive Staff Only
 |
View Item |
