Shannon capacity and the categorical product (Q2656906)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Shannon capacity and the categorical product
scientific article

    Statements

    Shannon capacity and the categorical product (English)
    0 references
    17 March 2021
    0 references
    Summary: Shannon OR-capacity \(C_{\mathrm{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 therefore \(C_{\mathrm{OR}}(F\times G)\leqslant\min\{C_{\mathrm{OR}}(F),C_{\mathrm{OR}}(G)\}\) holds 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 \textit{J. Zuiddam} [Combinatorica 39, No. 5, 1173--1184 (2019; Zbl 1449.05208)], 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 OR-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_{\mathrm{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_{\mathrm{OR}}(F),C_{\mathrm{OR}}(G)\}\). We present such graph pairs using the properties of Paley graphs.
    0 references
    Hedetniemi-type equality
    0 references
    finite asymptotic spectrum
    0 references
    Shannon capacity
    0 references
    fractional clique cover number
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references