The Asymptotic Spectrum of Graphs and the Shannon Capacity
| Authors | |
|---|---|
| Publication date | 11-2019 |
| Journal | Combinatorica |
| Volume | Issue number | 39 | 5 |
| Pages (from-to) | 1173-1184 |
| Number of pages | 12 |
| Organisations |
|
| Abstract |
We introduce the asymptotic spectrum of graphs and apply the theory of asymptotic spectra of Strassen (J. Reine Angew. Math. 1988) to obtain a new dual characterisation of the Shannon capacity of graphs. Elements in the asymptotic spectrum of graphs include the Lovász theta number, the fractional clique cover number, the complement of the fractional orthogonal rank and the fractional Haemers bound. |
| Document type | Article |
| Note | Funding Information: The author thanks Harry Buhrman, Matthias Chri-standl, Péter Vrana, Jop Briët, Dion Gijswijt, Farrokh Labib, Māris Ozols, Michael Walter, Bart Sevenster, Monique Laurent, Lex Schrijver, Bart Lit-jens and the members of the A&C PhD & postdoc seminar at CWI for useful discussions and encouragement. The author is supported by NWO (617.023.116) and the QuSoft Research Center for Quantum Software. The author initiated this work when visiting the Centre for the Mathematics of Quantum Theory (QMATH) at the University of Copenhagen. Funding Information: The author thanks Harry Buhrman, Matthias Chri-standl, P?ter Vrana, Jop Bri?t, Dion Gijswijt, Farrokh Labib, M?ris Ozols, Michael Walter, Bart Sevenster, Monique Laurent, Lex Schrijver, Bart Lit-jens and the members of the A&C PhD & postdoc seminar at CWI for useful discussions and encouragement. The author is supported by NWO (617.023.116) and the QuSoft Research Center for Quantum Software. The author initiated this work when visiting the Centre for the Mathematics of Quantum Theory (QMATH) at the University of Copenhagen. Publisher Copyright: © 2019, János Bolyai Mathematical Society and Springer-Verlag Berlin Heidelberg. Copyright: Copyright 2019 Elsevier B.V., All rights reserved. |
| Language | English |
| Published at | https://doi.org/10.1007/s00493-019-3992-5 |
| Other links | https://www.scopus.com/pages/publications/85068827195 |
| Permalink to this page | |
