On the Shannon capacity of sums and products of graphs
| Authors | |
|---|---|
| Publication date | 01-2023 |
| Journal | Indagationes Mathematicae |
| Volume | Issue number | 34 | 1 |
| Pages (from-to) | 37-41 |
| Organisations |
|
| Abstract | 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. |
| Document type | Article |
| Language | English |
| Published at | https://doi.org/10.1016/J.INDAG.2022.08.009 |
| Permalink to this page | |