2022-08-31
On the Shannon capacity of sums and products of graphs
Publication
Publication
Indagationes Mathematicae , Volume 34 - Issue 1 p. 37- 41
Let Θ(G) denote the Shannon capacity of a graph G. We give an elementary proof of the equivalence, for any graphs G and H, of the inequalities Θ(G⊔H)>Θ(G)+Θ(H) and Θ(G⊠H)>Θ(G)Θ(H). This was shown independently by Wigderson and Zuiddam (2022) using Kadison–Dubois duality and the Axiom of choice.
| Additional Metadata | |
|---|---|
| , , | |
| doi.org/10.1016/j.indag.2022.08.009 | |
| Indagationes Mathematicae | |
| Organisation | CWI management |
|
Schrijver, L. (2022). On the Shannon capacity of sums and products of graphs. Indagationes Mathematicae, 34(1), 37–41. doi:10.1016/j.indag.2022.08.009 |
|
