Revised by: Faculty Board of Science and Technology, 2021-09-07
This course covers recent theoretical and algorithmic developments in combinatorics. It begins with an overview of classical probabilistic methods such as first- and second-moment methods and the local lemma, and of some fundamental notions and results in extremal combinatorics, such as set systems, sunflowers, antichains, graph partitions, and Turán-type problems. The courses then moves on to give an in-depth treatment of the following topics at the cutting-edge of research:
the Moser-Tardos algorithm, and derandomization of probabilistic algorithms more generally;
the method of Hypergraph Containers and its applications;
Vapnik-Chervonenkis dimension and its applications to statistical learning and computational geometry.
Expected learning outcomes
For a passing grade, the student must be able to
Knowledge and understanding
give a detailed account of the probabilistic method in combinatorics
state and prove classical theorems in extremal combinatorics (Sperner's theorem, the Erdős--Ko--Rado theorem, the Erdős--Rado sunflower lemma, Turán's theorem)
give a detailed account of the Moser-Tardos algorithm and its properties
describe a Container Algorithm, and give a detailed outline of the proof of a Hypergraph Container theorem
rigorously define the notion of Vapnik-Chervonenkis dimension, and state and prove the Sauer-Shelah lemma
Skills and abilities
apply classical probabilistic techniques to solve combinatorial problems
apply Turán's theorem, Sperner's theorem, the Erdős--Ko--Rado theorem and the Sunflower Lemma to problems in combinatorics and computer science
apply the method of Hypergraph Containers
apply Vapnik-Chervonenkis theory and the Sauer-Shelah lemma to problems in combinatorics and discrete geometry
independently solve advanced problems in combinatorics
Judgement and approach
perform mathematically stringent probabilistic and combinational reasoning
critically apply results and methods in extremal and probabilistic combinatorics to typical problems in the field
The course requires a minimum of 90 ECTS in Mathematics or Computer Science, of which at least 60 ECTS must be in Mathematics including a course in Discrete Mathematics of at least 7.5 ECTS and a course in Statistics of at least 7.5 ECTS which includes elementary Probability Theory. Proficiency in English and Swedish equivalent to the level required for basic eligibility for higher studies
Form of instruction
The teaching on this course consists of lectures and exercise classes.
The course is examined through a written assignment and a written examination. On both parts the following judgments is assigned:Fail (U), Pass (G) or Pass with distinction (VG). For the whole course, one of the following grades is assigned: Fail (U), Pass (G), Pass with distinction (VG). In order to receive the grade of Pass (G), a student must obtain a judgment G or VG on all parts of the assessment. In order to receive the grade of Pass with distinction (VG), a student must in addition obtain judgment VG on all examinable components.
Deviations from the syllabus examination form can be made for a student who has a decision on pedagogical support due to disability. Individual adaptation of the examination form shall be considered based on the student's needs. The examination form is adapted within the framework of the expected learning outcomes of the course syllabus. At the request of the student, the course coor-dinator, in consultation with the examiner, must promptly decide on the adapted examination form. The decision shall then be communicated to the stu-dent.
A student who has been awarded a passing grade for the course cannot be re-assessed for a higher grade. Students who do not pass a test or examination on the original date are given another date to retake the examination. A student who has sat two examinations for a course or a part of a course, without pass-ing either examination, has the right to have another examiner appointed, pro-vided there are no specific reasons for not doing so (Chapter 6, Section 22, HEO). The request for a new examiner is made to the Head of the Department of Mathematics and Mathematical Statistics. Examinations based on this course syllabus are guaranteed to be offered for two years after the date of the stu-dent's first registration for the course.
Credit transfer All students have the right to have their previous education or equivalent, and their working life experience evaluated for possible consideration in the corresponding ed-ucation at Umeå university. Application forms should be adressed to Student ser-vices/Degree evaluation office. More information regarding credit transfer can be found on the student web pages of Umeå university, http://www.student.umu.se, and in the Higher Education Ordinance (chapter 6). If denied, the application can be ap-pealed (as per the Higher Education Ordinance, chapter 12) to Överklagandenämnden för högskolan. This includes partially denied applications
In a degree, this course may not be included together with another course with a similar content. If unsure, students should ask the Director of Studies in Mathematics and Mathematical Statistics.