Current Topics and Algorithms in Combinatorics, 7.5 Credits

Contents

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

Required Knowledge

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.

Examination modes

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

Other regulations

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.