Shannon capacity and the categorical product

DOI10.37236/9113zbMATH Open1459.05092OpenAlexW3137995099MaRDI QIDQ2656906FDOQ2656906

Authors Gábor Simonyi

Publication date 17 March 2021

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1911.00944

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Shannon capacityfinite asymptotic spectrumfractional clique cover numberHedetniemi-type equality

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph operations (line graphs, products, etc.) (05C76) Applications of graph theory to circuits and networks (94C15)

Abstract: Shannon OR-capacity $C_{mOR}(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_{mOR}(FimesG)lemin{C}_{mOR}(F),C_{mOR}(G)$ for every pair of graphs, where $FimesG$ 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_{mOR}(FimesG)$ 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}_{mOR}(F),C_{mOR}(G)$. We present such graph pairs using the properties of Paley graphs.

Recommendations

• On product of association schemes and Shannon capacity
• Capacity lower bounds via productization
• On the Shannon capacity of sums and products of graphs
• The Shannon capacity of a union
• Generalization of Shannon entropy of capacities on set systems
• scientific article; zbMATH DE number 3997696
• On graphs in which the Shannon capacity is unachievable by finite product
• Shannon's entropy as an index of product variety
• Shannon entropy: axiomatic characterization and application
• scientific article; zbMATH DE number 4191768

Cites work

• scientific article; zbMATH DE number 3728320 (Why is no real title available?)
• scientific article; zbMATH DE number 3465328 (Why is no real title available?)
• scientific article; zbMATH DE number 3501547 (Why is no real title available?)
• scientific article; zbMATH DE number 487720 (Why is no real title available?)
• scientific article; zbMATH DE number 1131873 (Why is no real title available?)
• scientific article; zbMATH DE number 1787227 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• scientific article; zbMATH DE number 3893303 (Why is no real title available?)
• scientific article; zbMATH DE number 3194323 (Why is no real title available?)
• A bound on the Shannon capacity via a linear programming variation
• A nontrivial lower bound on the shannon capacities of the complements of odd cycles
• A note on Hedetniemi's conjecture, Stahl's conjecture and the Poljak-Rödl function
• A note on the Poljak-Rödl function
• A survey on Hedetniemi's conjecture
• All self-complementary symmetric graphs
• Approximate graph coloring by semidefinite programming
• Bounds on Entanglement-Assisted Source-Channel Coding via the Lovász \(\vartheta \) Number and Its Variants
• Combinatorial Relations and Chromatic Graphs
• Counterexamples to Hedetniemi's conjecture
• Graphs and geometry
• Hedetniemi's conjecture is asymptotically false
• Hedetniemi's conjecture---a survey
• Hide and Seek, Data Storage, and Entropy
• Hom complexes and homotopy theory in the category of graphs
• I. Schur, C. E. Shannon and Ramsey numbers, a short story
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Information theory. Coding theorems for discrete memoryless systems
• Kneser's conjecture, chromatic number, and homotopy
• Motivations and history of some of my conjectures
• Multiplicative graphs and semi-lattice endomorphisms in the category of graphs
• On Some Problems of Lovász Concerning the Shannon Capacity of a Graph
• On a Fractional Version of Haemers’ Bound
• On inverse powers of graphs and topological implications of Hedetniemi's conjecture
• On the Shannon capacity of a graph
• On the Shannon capacity of triangular graphs
• On topological relaxations of chromatic conjectures
• Ramsey bounds for graph products
• Refined estimates concerning sumsets contained in the roots of unity
• Relatively small counterexamples to Hedetniemi's conjecture
• Repeated communication and Ramsey graphs
• Resource convertibility and ordered commutative monoids
• Sabidussi versus Hedetniemi for three variations of the chromatic number
• Self-complementary symmetric graphs
• Squares and difference sets in finite fields
• Star chromatic numbers and products of graphs
• The Shannon capacity of a union
• The asymptotic spectrum of graphs and the Shannon capacity
• The asymptotic spectrum of tensors.
• The chromatic number of the product of two 4-chromatic graphs is 4
• The fractional chromatic number of the categorical product of graphs
• The fractional version of Hedetniemi's conjecture is true
• The level of nonmultiplicativity of graphs
• Vector coloring the categorical product of graphs

Cited in

(4)

• scientific article; zbMATH DE number 4127270 (Why is no real title available?)
• scientific article; zbMATH DE number 4118412 (Why is no real title available?)
• A unified construction of semiring-homomorphic graph invariants
• On the Shannon capacity of sums and products of graphs

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Shannon capacity and the categorical product

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2656906)