A hypergraph $H$ consists of a set $V$ of vertices and a set $E$ of hyperedges that are subsets of $V$. A $t$-tuple of $H$ is a subset of $t$ vertices of $V$. A $t$-tuple $k$-coloring of $H$ is a mapping of its $t$-tuples into $k$ colors. A coloring is called $(t,k,f)$-polychromatic if each hyperedge of $E$ that has at least $f$ vertices contains tuples of all the $k$ colors. Let $f_H(t,k)$ be the minimum $f$ such that $H$ has a $(t,k,f)$-polychromatic coloring. For a family of hypergraphs $\cal{H}$ let $f_{\cal{H}}(t,k)$ be the maximum $f_H(t,k)$ over all hypergraphs $H$ in $\cal{H}$. We present several bounds on $f_{\cal{H}}(t,k)$ for $t\ge 2$. - Let $\cal{H}$ be the family of hypergraphs $H$ that is obtained by taking any set $P$ of points in $\Re^2$, setting $V:=P$ and $E:=\{d\cap P\colon d\text{ is a disk in }\Re^2\}$. We prove that $f_\cal{H}(2,k)\le 3.7^k$, that is, the pairs of points (2-tuples) can be $k$-colored such that any disk containing at least $3.7^k$ points has pairs of all colors. - For the family $\mathcal{H}$ of shrinkable hypergraphs of VC-dimension at most $d$ we prove that $ f_\cal{H}(d{+}1,k) \leq c^k$ for some constant $c=c(d)$. We also prove that every hypergraph with $n$ vertices and with VC-dimension at most $d$ has a $(d{+}1)$-tuple $T$ of depth at least $\frac{n}{c}$, i.e., any hyperedge that contains $T$ also contains $\frac{n}{c}$ other vertices. - For the relationship between $t$-tuple coloring and vertex coloring in any hypergraph $H$ we establish the inequality $\frac{1}{e}\cdot tk^{\frac{1}{t}}\le f_H(t,k)\le f_H(1,tk^{\frac{1}{t}})$. For the special case of $k=2$, we prove that $t+1\le f_H(t,2)\le\max\{f_H(1,2), t+1\}$; this improves upon the previous best known upper bound. - We generalize some of our results to higher dimensions, other shapes, pseudo-disks, and also study the relationship between tuple coloring and epsilon nets.

The objects of study of this paper are communication channels in which the dominant type of noise are symbol shifts, the main motivating examples being timing and bit-shift channels. Two channel models are introduced and their zeroerror capacities and zero-error-detection capacities determined by explicit constructions of optimal codes. Model A can be informally described as follows: 1) The information is stored in an n-cell register, where each cell is either empty or contains a particle of one of P possible types and 2) due to the imperfections of the device each of the particles may be shifted several cells away from its original position over time. Model B is an abstraction of a single-server queue: 1) The transmitter sends packets from a P-ary alphabet through a queuing system with an infinite buffer and a first-in-first-out service procedure and 2) each packet is being processed by the server for a random number of time slots. More general models including additional types of noise that the particles/packets can experience are also studied, as are the continuous-time versions of these problems.

We introduce a novel and general approach for digitalization of line segments in the plane that satisfies a set of axioms naturally arising from Euclidean axioms. In particular, we show how to derive such a system of digital segments from any total order on the integers. As a consequence, using a well-chosen total order, we manage to define a system of digital segments such that all digital segments are, in Hausdorff metric, optimally close to their corresponding Euclidean segments, thus giving an explicit construction that resolves the main question of [1].

In this paper, we address the problem of distributed Raptor code design over information packets located across the network nodes. We propose a novel approach to this problem that consists of generating, encoding and dispersing Raptor packets across the network. Unlike recent node-centric proposals, where network nodes are responsible for collecting information packets and performing Raptor encoding, in the proposed packet-centric approach this task is assigned to Raptor packets. In a two-step encoding procedure that corresponds to precoding and LT-coding step of standard Raptor encoding, Raptor packets randomly traverse the network, collect and encode sufficient number of information packets following exactly a given degree distribution, and finish their paths in a random network node. The efficiency of the distributed Raptor coding scheme is confirmed by simulation results, where their performance is demonstrated to approach closely the performance of standard (centralized) Raptor codes.

Let m and b be positive integers, and let F be a hypergraph. In an $(m,b)$ Maker-Breaker game F two players, called Maker and Breaker, take turns selecting previously unclaimed vertices of F. Maker selects m vertices per move, and Breaker selects b vertices per move. The game ends when every vertex has been claimed by one of the players. Maker wins if he claims all of the vertices of some hyperedge of F; otherwise Breaker wins. An $(m,b)$ Avoider-Enforcer game F is played in a similar way. The only difference is in the determination of the winner: Avoider loses if he claims all of the vertices of some hyperedge of F; otherwise Enforcer loses. In this paper we consider the Maker-Breaker and Avoider-Enforcer versions of the planarity game, the k-colorability game, and the $K_t$-minor game.

We show that any comparison based, randomized algorithm to approximate any given ranking of n items within expected Spearman’s footrule distance n 2/ν(n) needs at least n (min{log ν(n), log n} – 6) comparisons in the worst case. This bound is tight up to a constant factor since there exists a deterministic algorithm that shows that 6n(log ν(n)+1) comparisons are always sufficient.