Coloring chains for compression with uncertain priors
type: Item
instance of: scholarly article
title: Coloring chains for compression with uncertain priors
zbMATH Open document ID: 1411.05088
author: Noah Golowich
published in: The Electronic Journal of Combinatorics
publication date: 2019-03-05T00:00:00Z
full work available at URL: https://arxiv.org/abs/1707.03132
full work available at URL: v25i4p46
review text: A chain of length $k$ and size $t$ is a nested sequence of sets $A_0\subseteq A_0\subseteq\cdots \subseteq A_{k}\subseteq [N]=\{1,\dots,N\}$ where $|A_0|=1$ and $|A_{k}|=t$ and $N$ is a natural number. Such chains are denoted by $\left\langle \alpha, A_1,\dots,A_{k}\right\rangle$ where $A_0=\{\alpha\}$. Graph $U(N,t,k)$ contains as vertices all chains of length $k$ and size at most $t$. Two vertices $\left\langle \alpha, A_1,\dots,A_{k}\right\rangle$ and $\left\langle \beta, B_1,\dots,B_{k}\right\rangle$ of $U(N,t,k)$ are adjacent if $\alpha\neq\beta$, $A_i\subseteq B_{i+1}$ and $B_i\subseteq A_{i+1}$ for every $i\in\{0,\dots,k-1\}$. \par The chromatic number of $U(N,t,k)$ is strongly connected with a certain problem of transmitting a message between two persons. This work brings an improved upper and lower bounds on $\chi(U(N,t,k))$.
reviewed by: Iztok Peterin
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 7032052
zbMATH Keywords: chromatic number
zbMATH Keywords: nested sequence
MaRDI profile type: MaRDI publication profile
arXiv ID: 1707.03132
cites work: Explicit construction of exponential sized families of k-independent sets
cites work: On the Lambert \(w\) function
cites work: Coloring graphs with locally few colors
cites work: Q5596772
cites work: Deterministic compression with uncertain priors
cites work: Families of \(k\)-independent sets
cites work: Local chromatic number and Sperner capacity
cites work: Locality in Distributed Graph Algorithms
cites work: Local chromatic number, Ky Fan's theorem, and circular colorings
cites work: On directed local chromatic number, shift graphs, and Borsuk-like graphs
cites work: Locality based graph coloring
description: scientific article