Course Details
Listed below are the administrative details regarding the course.
Schedule
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.
Instructors
Martin Aigner
Arnimallee 3, Room 205
aigNOBOTSHEREner@math.fu-berHAHAHAHAHAHAHAlin.de
Shagnik Das
Arnimallee 3, Room 204
shagnNOBOTSHEREik@mi.fu-berHAHAHAHAHAHAHAlin.de
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.
Credits
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.
Topics
"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.
References
The following text is recommended for this course.
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.
Exercises
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 |
Presentations
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 |
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.