Course Details in 2025/26 Session

Module Title	Combinatorics and Communication Theory
School	Mathematics
Department	Mathematics
Module Code	06 19608
Module Lead	Deryk Osthus
Level	Masters Level
Credits	20
Semester	Semester 2
Pre-requisites	LC Algebra & Combinatorics 1 - (06 25659)
Co-requisites
Restrictions	Optional for all MSci programmes in Mathematics and MSci JH programmes including mathematics
Contact Hours	Lecture-46 hours Tutorial-10 hours Total: 56 hours
Exclusions
Description	The first part of the module will give an introduction to several combinatorial structures, which have applications in different areas. Topics are likely to include combinatorial games, applications of counting principles to discrete probability and basic Ramsey theory. (Here Ramsey theory can be viewed as a formalization of the notion that `complete disorder is impossible’ – this surprising phenomenon will be investigated for graph colourings and arithmetic properties of the integers). The second part of the module consists of an introduction to information theory and coding theory. The aim here is to transmit information (i) efficiently and (ii) reliably over a noisy channel. For (i), the main result will be Shannon’s noiseless coding theorem, which relates coding efficiency to the entropy of a source. For (ii), we will discuss error correcting codes, including several linear codes, such as Hamming codes. Both parts of the module are linked by the methods and ideas that are used.
Learning Outcomes	By the end of the module the student should be able to: Apply counting principles in various settings, including discrete probability Be familiar with basic combinatorial structures and arguments, be able to prove simple results in Ramsey theory. Understand and be able to apply fundamental results on codes and communication over a noisy channel. Apply the basic coding techniques such as Huffman codes and linear codes. Level M students will explore the subject beyond the taught syllabus.
Assessment	19608-01 : Raw Module Mark : Coursework (100%)
Assessment Methods & Exceptions	3 hour Written Unseen Examination (80%); In-course Assessment (20%).
Other
Reading List	Welsh, D. 1988. Codes and Cryptography. Oxford University Press. Jukna, S. 2001. Extremal Combinatorics. Springer-Verlag.