Designs and Codes

Summer 2017

FU Berlin, Mathematics and Informatics

Thanks to John Hilliard for the GIF.

Course Details

Listed below are the administrative details regarding the course.


There will be one lecture per week, as detailed below.

Lectures: Tuesdays from 12:30 to 14:00 in Arnimallee 6, SR 031.

You are also encouraged to attend the exercise classes.

Exercises: Wednesdays from 12:30 to 14:00 in Takustraße 9, SR 005.


Martin Aigner
Arnimallee 3, Room 205

Shagnik Das
Arnimallee 3, Room 204

Office hours are by appointment, so please e-mail as needed.

Exams and Requirements

The final grade for this course will come from an oral exam. The first round of exams will take place between the 17th and 21st of July, with the second round between the 26th and the 29th of September. You may sign up here for the exam.

The full set of requirements and formalities for the course can be found here.


Master's students at the Freie Universität Berlin may take this course either as "Diskrete Mathematik III" or as an Ergänzungsmodul.

Phase I students from the Berlin Mathematical School may take this course as an advanced course in teaching area 4.

Return to top


"Code" has become a household word, and probably everybody knows (vaguely) that good codes determine much of modern life. Mathematically, a good code is a very regular arrangement of codewords, or what we call a design. In this course we treat the basics of designs and codes, discuss several important examples, and focus on the algebraic methods for constructing good designs with given parameters or proving their nonexistence.

Course contents: basic concepts of designs, projective planes, Hadamard matrices, non-existence results, Latin squares, Euler's conjecture, basics of coding theory, linear codes, perfect codes.


The following text is recommended for this course.

  • J. H. van Lint and R. M. Wilson, A Course in Combinatorics
  • Prerequisites

    This course is a third course in the Discrete Maths module. Successful completion of Discrete Maths I is required, and completion of a Discrete Maths II course is highly recommended.

    Firm knowledge of linear algebra and matrices is required, and a good background in finite fields would be very useful.

    Return to top


    There will be a new homework assignment every two weeks, and they will be due at the start of exercise classes on odd weeks. You will then have the opportunity to present and discuss solutions to the exercises during the class.

    Assignment Due date Comments
    Sheet 1 3/5/2017 [29/4: Ex 4 clarified, hints added]
    Sheet 2 17/5/2017 [16/5: Ex 4 corrected]
    Sheet 3 31/5/2017
    Sheet 4 14/6/2017
    Sheet 5 28/6/2017 [27/6: Reference in Ex 5(b) corrected]
    Sheet 6 12/7/2017
    Practice sheet Never ever
    Return to top


    On even weeks, when there is no homework assignment due, we will have an additional lecture during the Wednesday class, as listed in the schedule below. We would like these lectures to be given by you, the students, and you should volunteer by sending us an e-mail stating your interest.

    We will provide you with notes and references to help you prepare for the class, and you will earn credit towards the following week's homework assignment.

    Date Topic Speakers
    10/5/2017 Hadamard matrices and designs Ander and Patrick
    24/5/2017 Kirkman's schoolgirl problem Giulia and Simona
    7/6/2017 The 36 officers problem Eric and Mingyang
    21/6/2017 Gurvits's Theorem on permanents Alexandra and Julian
    5/7/2017 MacWilliams' Identity for linear codes Mohammad
    Return to top

    Course Progress

    As we make our way through the semester, we will provide below a brief review of the topics covered each week.

    Date Topics References
    18/4/2017 Combinatorial designs: introduction, definition, divisibility conditions and other general results [vLW] Ch 19
    25/4/2017 2-designs: Fisher's inequality, incidence matrices, symmetric and dual designs [vLW] Ch 19
    26/4/2017 Projective and affine planes: definition, equivalence to symmetric Steiner 2-designs, linear algebraic construction [vLW] Ch 19
    2/5/2017 The Bruck-Ryser-Chowla Theorem: statement, application to projective planes, sums of four squares, proof [vLW] Ch 19
    9/5/2017 The Wilson-Petrenjuk inequality: statement and proof; statement of Wilson's theorem on the existence of designs [vLW] Ch 19
    10/5/2017 Hadamard designs: connection to Hadamard matrices; Kronecker product construction; Paley's construction [vLW] Ch 18, 19
    16/5/2017 t-designs: proof of Wilson's existence theorem; survey of existence results: Wilson (t = 2), Teirlinck, Keevash
    23/5/2017 Latin squares (LS): definition, examples; mutually orthogonal Latin squares (MOLS): orthogonal arrays, nets [vLW] Ch 17, 22
    24/5/2017 Kirkman's schoolgirl problem: definition of Kirkman triples; constructions for v = 15; recursive constructions
    30/5/2017 MOLS: transversal designs; constructions: prime powers, recursive constructions; Euler's conjecture, disproof [vLW] Ch 22
    6/6/2017 MOLS: Bose-Shrikhande-Parker, asymptotics of N(n); Counting LS: edge-colouring, transversals, permanents [vLW] Ch 17, 22
    7/6/2017 Solving the 36 Officers' problem: non-existence of TD(4,6) [vLW] Ch 17, 22
    Eric's notes
    13/6/2017 Counting LS: bounding the permanent with Bregman's and Gurvits's theorems
    20/6/2017 Codes: applications, definitions, linear codes, generator and control matrices [vLW] Ch 20
    21/6/2017 Gurvits' theorem: the capacity of homogeneous H-stable polynomials with non-negative coefficients Julian's notes
    27/6/2017 Hamming codes; equivalent codes; punctured and extended codes; (R+1)-designs from R-perfect codes [vLW] Ch 20
    4/7/2017 Statement of the MacWilliams relation; the Assmus-Mattson theorem; the ternary Golay codes [vLW] Ch 20
    5/7/2017 The MacWilliams identity: statement and proof in the binary case [vLW] Ch 20
    11/7/2017 Tietäväinen's theorem: Lloyd polynomials and a sketch of a sketch of a proof

    There is a partial set of lecture notes, currently covering the section of the course on designs.

    Return to top