8 - Codes and Related Structures

Summary

A lot of mathematical objects are closely related to each other. While studying certain aspects of a mathematical object, one tries to find a way to “view” the object in a way that is most suitable for a specific problem. Or in other words, one tries to find the best way to model the problem. Many related fields of mathematics have evolved from one another this way. In practice, it is very useful to be able to transform your problem into other terminology: it gives a lot more available knowledge that can be helpful to solve a problem.

In this chapter we give a broad overview of fields closely related to error-correcting codes. From various methods of determining the weight enumerator, as treated in Chapter 3, we naturally run into other ways to view an error-correcting code. We will introduce and link the following mathematical objects:

• linear codes and their weight enumerator (Chapter 3);

• arrangements and their characteristic polynomial (§3.2.1, §8.5);

• graphs and their chromatic polynomial (§8.1);

• matroids and their Tutte polynomial (§8.2);

• posets and their Möbius function (§8.4);

• geometric lattices and their coboundary polynomial (§8.4, §8.5).

A nice example to show the power of these connections are the MacWilliams identities, which relate the polynomials associated to an object and its dual. This will be treated in Section 8.2.7. Several examples and counterexamples are given in Section 8.5.6 and an overview is given to show which polynomials determine each other in Section 8.5.7.

This chapter is self-contained, but we refer to the Notes at the end for various references to further reading and background knowledge.

Graphs and Codes

Colorings of a Graph

Definition A graph Γ is a pair (V,E) where V is a nonempty set and E is a set disjoint from V. The elements of V are called vertices, and members of E are called edges. Edges are incident to one or two vertices, which are called the ends of the edge. If an edge is incident with exactly one vertex, then it is called a loop. If u and v are vertices that are incident with an edge, then they are called neighbors or adjacent.