Coloring chains for compression with uncertain priors

zbMATH Open1411.05088arXiv1707.03132MaRDI QIDQ668010FDOQ668010

Authors: Noah Golowich 

Publication date: 5 March 2019

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: Haramaty and Sudan considered the problem of transmitting a message between two people, Alice and Bob, when Alice's and Bob's priors on the message are allowed to differ by at most a given factor. To find a deterministic compression scheme for this problem, they showed that it is sufficient to obtain an upper bound on the chromatic number of a graph, denoted $U(N,s,k)$ for parameters $N,s,k$, whose vertices are nested sequences of subsets and whose edges are between vertices that have similar sequences of sets. In turn, there is a close relationship between the problem of determining the chromatic number of $U(N,s,k)$ and a local graph coloring problem considered by ErdH{o}s et al. We generalize the results of ErdH{o}s et al. by finding bounds on the chromatic numbers of graphs $H$ and $G$ when there is a homomorphism $phi:HightarrowG$ that satisfies a nice property. We then use these results to improve upper and lower bounds on $chi(U(N,s,k))$.

Full work available at URL: https://arxiv.org/abs/1707.03132

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Communication Lower Bounds Via the Chromatic Number
• The zero-error side information problem and chromatic numbers (Corresp.)
• Minimum entropy coloring
• Algorithms and Computation
• Deterministic compression with uncertain priors

zbMATH Keywords

chromatic numbernested sequence

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• On the Lambert \(w\) function
• Families of \(k\)-independent sets
• Coloring graphs with locally few colors
• Local chromatic number and Sperner capacity
• On directed local chromatic number, shift graphs, and Borsuk-like graphs
• Local chromatic number, Ky Fan's theorem, and circular colorings
• Locality in Distributed Graph Algorithms
• Locality based graph coloring
• Title not available (Why is that?)
• Explicit construction of exponential sized families of k-independent sets
• Deterministic compression with uncertain priors

Cited In (1)

• Deterministic compression with uncertain priors

This page was built for publication: Coloring chains for compression with uncertain priors

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