๐ฎ
๐ฎ
The Ethereal
Shannon capacity and the categorical product
November 03, 2019 ยท The Ethereal ยท ๐ Electronic Journal of Combinatorics
"No code URL or promise found in abstract"
Evidence collected by the PWNC Scanner
Authors
Gรกbor Simonyi
arXiv ID
1911.00944
Category
math.CO: Combinatorics
Cross-listed
cs.CC,
cs.IT
Citations
5
Venue
Electronic Journal of Combinatorics
Last Checked
2 months ago
Abstract
Shannon OR-capacity $C_{\rm OR}(G)$ of a graph $G$, that is the traditionally more often used Shannon AND-capacity of the complementary graph, is a homomorphism monotone graph parameter satisfying $C_{\rm OR}(F\times G)\le\min\{C_{\rm OR}(F),C_{\rm OR}(G)\}$ for every pair of graphs, where $F\times G$ is the categorical product of graphs $F$ and $G$. Here we initiate the study of the question when could we expect equality in this inequality. Using a strong recent result of Zuiddam, we show that if this "Hedetniemi-type" equality is not satisfied for some pair of graphs then the analogous equality is also not satisfied for this graph pair by some other graph invariant that has a much "nicer" behavior concerning some different graph operations. In particular, unlike Shannon capacity or the chromatic number, this other invariant is both multiplicative under the OR-product and additive under the join operation, while it is also nondecreasing along graph homomorphisms. We also present a natural lower bound on $C_{\rm OR}(F\times G)$ and elaborate on the question of how to find graph pairs for which it is known to be strictly less, than the upper bound $\min\{C_{\rm OR}(F),C_{\rm OR}(G)\}$. We present such graph pairs using the properties of Paley graphs.
Community Contributions
Found the code? Know the venue? Think something is wrong? Let us know!
๐ Similar Papers
In the same crypt โ Combinatorics
๐ฎ
๐ฎ
The Ethereal
On cap sets and the group-theoretic approach to matrix multiplication
๐ฎ
๐ฎ
The Ethereal
Generalized Twisted Gabidulin Codes
๐ฎ
๐ฎ
The Ethereal
Tables of subspace codes
๐ฎ
๐ฎ
The Ethereal
Classification of weighted networks through mesoscale homological features
๐ฎ
๐ฎ
The Ethereal