Repeated communication and Ramsey graphs

Noga Mordechai Alon, Alon Orlitsky

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Studies the savings afforded by repeated use in two zero-error communication problems. 1. Channel coding: proving a correspondence between Ramsey numbers and independence numbers of normal graph powers, the authors 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, the authors show that similar results hold even when the number of transmissible bits is large relative to the channel's size. 2. Dual-source coding: using probabilistic colorings of directed line graphs, the authors 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, they 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)
Title of host publicationProceedings - 1994 IEEE International Symposium on Information Theory, ISIT 1994
Number of pages1
DOIs
StatePublished - Dec 1 1994
Externally publishedYes
Event1994 IEEE International Symposium on Information Theory, ISIT 1994 - Trondheim, Norway
Duration: Jun 27 1994Jul 1 1994

Other

Other1994 IEEE International Symposium on Information Theory, ISIT 1994
CountryNorway
CityTrondheim
Period6/27/947/1/94

Fingerprint

Communication
Directed line
Graph in graph theory
Graph Powers
Channel Coding
Source Coding
Ramsey number
Independence number
Line Graph
Cayley Graph
Directed Graph
Colouring
Logarithmic
Correspondence
Channel coding
Zero
Conveying
Coloring

All Science Journal Classification (ASJC) codes

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

Cite this

Alon, N. M., & Orlitsky, A. (1994). Repeated communication and Ramsey graphs. In Proceedings - 1994 IEEE International Symposium on Information Theory, ISIT 1994 [394703] https://doi.org/10.1109/ISIT.1994.394703
Alon, Noga Mordechai ; Orlitsky, Alon. / Repeated communication and Ramsey graphs. Proceedings - 1994 IEEE International Symposium on Information Theory, ISIT 1994. 1994.
@inproceedings{f9f8e9766b9e4515be1963b1b4d220fc,
title = "Repeated communication and Ramsey graphs",
abstract = "Studies the savings afforded by repeated use in two zero-error communication problems. 1. Channel coding: proving a correspondence between Ramsey numbers and independence numbers of normal graph powers, the authors 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, the authors show that similar results hold even when the number of transmissible bits is large relative to the channel's size. 2. Dual-source coding: using probabilistic colorings of directed line graphs, the authors 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, they 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.",
author = "Alon, {Noga Mordechai} and Alon Orlitsky",
year = "1994",
month = "12",
day = "1",
doi = "https://doi.org/10.1109/ISIT.1994.394703",
language = "English (US)",
isbn = "0780320158",
booktitle = "Proceedings - 1994 IEEE International Symposium on Information Theory, ISIT 1994",

}

Alon, NM & Orlitsky, A 1994, Repeated communication and Ramsey graphs. in Proceedings - 1994 IEEE International Symposium on Information Theory, ISIT 1994., 394703, 1994 IEEE International Symposium on Information Theory, ISIT 1994, Trondheim, Norway, 6/27/94. https://doi.org/10.1109/ISIT.1994.394703

Repeated communication and Ramsey graphs. / Alon, Noga Mordechai; Orlitsky, Alon.

Proceedings - 1994 IEEE International Symposium on Information Theory, ISIT 1994. 1994. 394703.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Repeated communication and Ramsey graphs

AU - Alon, Noga Mordechai

AU - Orlitsky, Alon

PY - 1994/12/1

Y1 - 1994/12/1

N2 - Studies the savings afforded by repeated use in two zero-error communication problems. 1. Channel coding: proving a correspondence between Ramsey numbers and independence numbers of normal graph powers, the authors 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, the authors show that similar results hold even when the number of transmissible bits is large relative to the channel's size. 2. Dual-source coding: using probabilistic colorings of directed line graphs, the authors 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, they 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.

AB - Studies the savings afforded by repeated use in two zero-error communication problems. 1. Channel coding: proving a correspondence between Ramsey numbers and independence numbers of normal graph powers, the authors 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, the authors show that similar results hold even when the number of transmissible bits is large relative to the channel's size. 2. Dual-source coding: using probabilistic colorings of directed line graphs, the authors 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, they 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.

UR - http://www.scopus.com/inward/record.url?scp=84894339498&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84894339498&partnerID=8YFLogxK

U2 - https://doi.org/10.1109/ISIT.1994.394703

DO - https://doi.org/10.1109/ISIT.1994.394703

M3 - Conference contribution

SN - 0780320158

SN - 9780780320154

BT - Proceedings - 1994 IEEE International Symposium on Information Theory, ISIT 1994

ER -

Alon NM, Orlitsky A. Repeated communication and Ramsey graphs. In Proceedings - 1994 IEEE International Symposium on Information Theory, ISIT 1994. 1994. 394703 https://doi.org/10.1109/ISIT.1994.394703