Bounds on Shannon Capacity and Ramsey Numbers from Product of Graphs

Graphs, Hypergraphs, and Computing

06 May 14:00 - 15:00

Stanislaw P. Radziszowski - Rochester Institute of Technology, RIT

We study Shannon capacity of channels in the context of classical Ramsey numbers. We overview some of the results on capacity of noisy channels modelled by graphs, and how some constructions may contribute to our knowledge of this capacity.

We present an improvement to the constructions by Abbott and Song and thus establish new lower bounds for a special type of multicolor Ramsey numbers. We prove that our construction implies that the supremum of the Shannon capacity over all graphs with independence number 2 cannot be achieved by any finite graph power. This can be generalized to graphs with bounded independence number.

IEEE Transactions on Information Theory, 59(8) (2013) 4767-4770, Joint work with Xiaodong Xu, Guangxi Academy of Sciences, China
Magnus M. Halldorsson
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU


Klas Markström


For practical matters at the Institute, send an e-mail to