Shannon capacity and the categorical product

DOI10.37236/9113zbMATH Open1459.05092arXiv1911.00944OpenAlexW3137995099MaRDI QIDQ2656906FDOQ2656906

Authors: Gábor Simonyi 

Publication date: 17 March 2021

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

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.

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

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

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 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)

Cites Work

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

Cited In (3)

• On the Shannon capacity of sums and products of graphs
• Title not available (Why is that?)
• Title not available (Why is that?)

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)