Shannon capacity and the categorical product

DOI10.37236/9113zbMath1459.05092arXiv1911.00944OpenAlexW3137995099MaRDI QIDQ2656906

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

zbMATH Keywords

Shannon capacityfinite asymptotic spectrumfractional clique cover numberHedetniemi-type equality

Mathematics Subject Classification ID

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

Uses Software

• OEIS

Cites Work

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