The Lovász number is not alone: a continuum of Rényi points in the entanglement-assisted spectrum of graphs
Abstract
Li and Zuiddam's entanglement-assisted asymptotic spectrum of graphs consists of the normalized graph parameters that are additive under disjoint unions, multiplicative under strong products and monotone under entanglement-assisted cohomomorphisms; the entanglement-assisted Shannon capacity is their pointwise minimum. To our knowledge, the Lovász number ϑ was its only known element. We find a continuum of others. Three quantities of Duan and Winter, log2ϑ, the minimal Holevo capacity Cmin and the logarithm of the no-signalling simulation cost Σ, are the smallest information radii of classical-quantum channels compatible with a graph, measured with Petz-Rényi divergences of orders $0$, $1$ and $2$. At order zero this is due to Schrijver (as credited by Dalai) and to Duan and Winter; at order one it is the min-max formula for the Holevo capacity. Interpolating in the order gives a family ϑα, 0≤α≤2, and we prove that every member lies in the spectrum. The main step, multiplicativity under strong products for channels that need not factor, follows from an exact nesting identity for compressions. Sandwiched Rényi radii of order β∈[1/2,∞] give the same family, at α=2−1/β. On the five-cycle the family takes every value in [√5,5/2]. A Hilbert-Schmidt inequality for the pentagon gives Cmin(C5)=log2(5/2), proving a conjecture of Duan and Winter. We also settle the two open links of their inequality chain: the graph-level no-signalling simulation rate always equals its single-letter value log2Σ(G), and a 32-vertex graph from the Mermin-Peres magic square has Cmin<log2Σ, certified in exact rational arithmetic. Finally, Σ never exceeds the projective rank of the complement; a rank inequality for the same square makes this strict on a 1440-vertex graph.
Related
- Sharp asymptotics for the Lovász number of random circulant graphs
- The Lovász Local Lemma Is Sharp for the Hat Guessing Number
- Verified Length Spectrum and Margulis number for Hyperbolic 3-Manifolds
- New distance bounds for one-generator quasi-cyclic codes with applications to Hermitian LCD codes and entanglement-assisted quantum codes
- Simultaneous Reduction of Observables and Measured Qudits in Entanglement-Assisted Quantum Local Recovery
BibTeX
@misc{mghirbi2026lovász,
title = {{The Lovász number is not alone: a continuum of Rényi points in the entanglement-assisted spectrum of graphs}},
author = {Nidhal Mghirbi and Seth Douglas},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.20775},
eprint = {2610.20775},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.20775},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The Lovász number is not alone: a continuum of Rényi points in the entanglement-assisted spectrum of graphs
AU - Nidhal Mghirbi
AU - Seth Douglas
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2610.20775
UR - https://arxiv.org/abs/2610.20775
AB - Li and Zuiddam's entanglement-assisted asymptotic spectrum of graphs consists of the normalized graph parameters that are additive under disjoint unions, multiplicative under strong products and monotone under entanglement-assisted cohomomorphisms; the entanglement-assisted Shannon capacity is their pointwise minimum. To our knowledge, the Lovász number ϑ was its only known element. We find a continuum of others. Three quantities of Duan and Winter, log_2ϑ, the minimal Holevo capacity C_min and the logarithm of the no-signalling simulation cost Σ, are the smallest information radii of classical-quantum channels compatible with a graph, measured with Petz-Rényi divergences of orders $0$, $1$ and $2$. At order zero this is due to Schrijver (as credited by Dalai) and to Duan and Winter; at order one it is the min-max formula for the Holevo capacity. Interpolating in the order gives a family ϑ_α, 0≤α≤2, and we prove that every member lies in the spectrum. The main step, multiplicativity under strong products for channels that need not factor, follows from an exact nesting identity for compressions. Sandwiched Rényi radii of order β∈[1/2,∞] give the same family, at α=2−1/β. On the five-cycle the family takes every value in [√5,5/2]. A Hilbert-Schmidt inequality for the pentagon gives C_min(C_5)=log_2(5/2), proving a conjecture of Duan and Winter. We also settle the two open links of their inequality chain: the graph-level no-signalling simulation rate always equals its single-letter value log_2Σ(G), and a 32-vertex graph from the Mermin-Peres magic square has C_min<log_2Σ, certified in exact rational arithmetic. Finally, Σ never exceeds the projective rank of the complement; a rank inequality for the same square makes this strict on a 1440-vertex graph.
ER -