Repeated communication and Ramsey graphs

Noga Mordechai Alon, Alon Orlitsky

Research output: Contribution to conferencePaperpeer-review


We study the savings afforded by repeated use in two zero-error communication problems. Channel coding: Proving a correspondence between Ramsey numbers and independence numbers of normal graph powers, we show that some channels can communicate exponentially more bits in two uses than they can in one use, and that this is essentially the largest possible increase. Using probabilistic constructions of self-complementary Ramsey graphs, we show that similar results hold even when the number of transmissible bits is large relative to the channel's size. Dual-source coding: Using probabilistic colorings of directed line graphs, we show that there are dual sources where communicating one instance requires arbitrarily many bits, yet communicating many instances requires at most two bits per instance. For dual sources where the number of bits required for a single instance is comparable to the source's size, we employ probabilistic constructions of self-complementary Ramsey graphs that are also Cayley graphs to show that conveying two instances may require only a logarithmic number of additional bits over that needed to convey one instance.

Original languageEnglish (US)
StatePublished - Dec 1 1994
Externally publishedYes
EventProceedings of the 1994 IEEE International Symposium on Information Theory - Trodheim, Norw
Duration: Jun 27 1994Jul 1 1994


OtherProceedings of the 1994 IEEE International Symposium on Information Theory
CityTrodheim, Norw

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics


Dive into the research topics of 'Repeated communication and Ramsey graphs'. Together they form a unique fingerprint.

Cite this