Computer Science/Discrete Mathematics Seminar II

One of the central problems of coding theory is to determine the trade-off between the amount of information a code can carry (captured by its rate) and its robustness to resist message corruption (captured by its distance). One of the main methods to prove upper bounds on sizes of codes is via the Delsarte linear program of the Hamming and Johnson schemes. Since these bounds are known to not be tight, in a recent work with Fernando Jeronimo and Chris Jones, we provided a hierarchy of high-order Hamming schemes that is complete in the sense that in a high enough level their Delsarte linear programs provide tight bounds for linear codes.

The completeness of this hierarchy explores four different views of the underlying optimization problem: the first is the Lovász theta prime function on the associated graph, the second is the original view of the hierarchy in which we factor translation and permutation symmetries, the third is an alternative view in which we factor translation and linear combination symmetries and the final one builds on top of the third one by changing bases via Möbius inversion.

In this second lecture, I will cover all these views of the hierarchy and how they come together to prove its completeness.