The Shannon capacity of a graph and the independence numbers of its powers

Abstract

The independence numbers of powers of graphs have been long studied, under several definitions of graph products, and in particular, under the strong graph product. We show that the series of independence numbers in strong powers of a fixed graph can exhibit a complex structure, implying that the Shannon Capacity of a graph cannot be approximated (up to a sub-polynomial factor of the number of vertices) by any arbitrarily large, yet fixed, prefix of the series. This is true even if this prefix shows a significant increase of the independence number at a given power, after which it stabilizes for a while.

Cited by in corpus (16)

• A Combinatorial Approach to Nonlocality and Contextuality
• Zero-error communication via quantum channels, non-commutative graphs and a quantum Lovasz theta function
• Exploring the Local Orthogonality Principle
• Entanglement between Two Uses of a Noisy Multipartite Quantum Channel Enables Perfect Transmission of Classical Information
• Observations on the Lovász $\theta$-Function, Graph Capacity, Eigenvalues, and Strong Products
• Observations on Graph Invariants with the Lovász $\vartheta$-Function
• Entanglement-assisted zero-error source-channel coding
• On the normalized Shannon capacity of a union
• Colouring Strong Products
• Multi-party zero-error classical channel coding with entanglement
• On a Diagonal Conjecture for Classical Ramsey Numbers
• Information storage and transmission under Markovian noise
• Symmetric Shannon capacity is the independence number minus 1
• Bounds on Shannon Capacity and Ramsey Numbers from Product of Graphs
• Visible Rank and Codes with Locality
• Graph Information Ratio