Repeated communication and Ramsey graphs

DOI10.1109/18.412676MaRDI QIDQ4859754zbMATH OpenOpenAlexFDO

Authors Noga Alon, Alon Orlitsky

Publication date 12 February 1996

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/59cef85b83ac47185d1467f8c4264fc321867e87

zbMATH Keywords

channelinformationRamsey graphsrandom sourceszero-error communication

Mathematics Subject Classification ID

Applications of graph theory (05C90) Communication theory (94A05) Source coding (94A29) Channel models (including quantum) in information and communication theory (94A40)

Recommendations

• Three results on interactive communication
• The Shannon capacity of a communication channel, graph Ramsey number and a conjecture of Erdős
• On interactive communication
• Interactive Communication of Balanced Distributions and of Correlated Files
• Privileged users in zero-error transmission over a noisy channel

Cited in

(28)

• The Shannon capacity of a communication channel, graph Ramsey number and a conjecture of Erdős
• Random subgraphs of properly edge-coloured complete graphs and long rainbow cycles
• Probabilistic refinement of the asymptotic spectrum of graphs
• On a diagonal conjecture for classical Ramsey numbers
• New lower bounds for the Shannon capacity of odd cycles
• Algorithmic and explicit determination of the Lovász number for certain circulant graphs
• Asymptotic values of the Hall-ratio for graph powers
• The chromatic number of random Cayley graphs
• Shannon capacity and the categorical product
• On colorful edge triples in edge-colored complete graphs
• Random cyclic triangle-free graphs of prime order
• On the number of zero-patterns of a sequence of polynomials
• Grothendieck-type inequalities in combinatorial optimization
• Random Latin square graphs
• Lovász, vectors, graphs and codes
• Difference sets and positive exponential sums. I: General properties
• On the normalized Shannon capacity of a union
• Quadratic forms on graphs
• Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture
• List Ramsey numbers
• Colouring strong products
• Toward better depth lower bounds: a KRW-like theorem for strong composition
• An improved lower bound on the Shannon capacities of complements of odd cycles
• Sumsets in the hypercube
• Short monochromatic odd cycles
• Algebraic bounds on the chromatic number and independent sets of graphs
• Abelian groups without 3-chromatic Cayley graphs
• Large sets in finite fields are sumsets

This page was built for publication: Repeated communication and Ramsey graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4859754)