Combinatorial methods and models. Rudolf Ahlswede's lectures on information theory 4. Edited by Alexander Ahlswede, Ingo Althöfer, Christian Deppe and Ulrich Tamm (Q526571)

The book under review is the fourth volume of Rudolf Ahlswede's lectures on Information Theory. The originality of this book is the fact that it focuses on Combinatorics and combinatorial approach to Information Theory while the classical approach is based on probabilistic models. The motivation for such an approach is that in many cases the structure of the coding problems are rather combinatorial than probabilistic. The fourth volume of Rudolf Ahlswede's lectures consists of two parts: Part I, Combinatorial methods for Information Theory, and Part II, Combinatorial models in Information Theory. Each part contains three chapters. References and further readings are given at the end of each chapter. Also, many problems left as an exercise or research for the reader are included in the text. The lectures in Part I are based on Rudolf Ahlswede's own research and the methods and techniques he introduced. Chapter 1 is an introduction to hypergraphs and covering, packing, and coloring techniques. Their applications and relation to zero error coding is also considered. A code can be regarded combinatorially as a hypergraph; and many coding theorems can be obtained by appropriate colourings or coverings of the underlying hypergraphs. Chapter 2 deals with codes produced by permutations. The idea is to built up bigger channel codes (that achieve given coding bound) from good smaller codes using suitable permutations. The existence of such constructions is given by Theorem 2.3. Chapter 3 concerns the Ahlswede's favourite research fields -- extremal problems in combinatorics. It starts with analysis of Kraft's inequality for prefix codes as the LYM property in the partially ordered set (poset) imposed by a tree. In this chapter Ahlswede discuses also several coding bounds. Part 2 is devoted to combinatorial models in Information Theory. Chapter 4 presents such models for multiple access channels: several senders are connected to the same receiver. A central problem is to assign codes to the senders so that they can communicate simultaneously with the receiver through a share channel. The most studied case is the binary adder channel. Large variety of code constructions for different models due to Ahlswede and many other authors are presented and discussed in this chapter. Interference channels and multiple access channels with noiseless feedback are also considered. The first two sections of Chapter 5 study binary codes correcting losses of \(\ell\) adjacent bits. The next section concerns codes over \(\mathbb{Z}_q\) capable to correct the most likely errors for amplitude and phase modulated channels. In this chapter it is also discussed in details the error correcting coding for binary channels with asymmetric errors, known as \(Z\)-channels. Chapter 6 is titled Orthogonal polynomials in Information theory. It is the most algebraic chapter in this volume and concerns a subject with many applications in different mathematical areas. Section 6.2 deals with relation between splitting of abelian groups and shift codes. The next section considers the role of Hankel matrices in coding theory and their relations with orthogonal polynomials. Application of Berlekamp-Massey algorithm to solving combinatorial problems (Catalan-like numbers) is also discussed here. An interesting topic addressed in this section is the computation of number of paths in an integer lattice not touching a given boundary. The lectures presented in this work are suitable for graduate students in Mathematics, Theoretical Computer Science, and Electrical Engineering with a background in basic Mathematics. The lectures can be used as the basis for courses or to supplement courses in many ways. Ph.D. students can find research problems, often with conjectures, that offer potential subjects for a thesis. Researchers may find questions which form the basis of entire research programs. The lectures also give detail information about the history of considered problems supplied with rich references.