Extremal and probabilistic combinatorics, 7.5 Credits

Contents

This course introduces powerful probabilistic methods, and their applications to fundamental problems in extremal combinatorics. It includes an overview of classical probabilistic methods such as first- and second-moment methods and the Lóvasz 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. In addition, the course will treat a selection of related topics at the cutting-edge of research. 

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)

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
• 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 written assignments and active seminar attendence. On either part, the following gradesare 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) for the whole course, the student must obtain grades G or VG on all parts of the assessment. In order to receive the grade of Pass with distinction(VG) for the whole course, the student must in addition obtain the grade VG on all examinable components.

A student who has been awarded a passing grade for the course cannot be reassessed 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 passing either examination, has the right to have anotherexaminer appointed, provided there are no specific reasons for not doing so (Chapter 6, Section 22, HEO). The request fora new examiner is made to the Head of the Department of Mathematics and Mathematical Statistics. Examinations basedon this course syllabus are guaranteed to be offered for two years after the date of the student's first registration for the course.

Examiners may decide to deviate from the modes of assessment in the course syllabus. Individual adaption of modes ofassessment must give due consideration to the student's needs. The adaption of modes of assessment must remainwithin the framework of the intended learning outcomes in the course syllabus. Students who require an adapted examination must submit a request to the department holding the course no later than 10 days before the examination.The examiner decides on the adaption of the examination, after which the student will be notified.

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 education at Umeå university. Application forms should be addressed to Student services/Degree evaluation office. More information regarding credit transfer can be found on the student webpages of Umeå university, http://www.student.umu.se, and in the Higher Education Ordinance (chapter 6). If denied, theapplication can be appealed (as per the Higher Education Ordinance, chapter 12) to Överklagandenämnden förhö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.

In the event that the syllabus ceases to apply or undergoes major changes, students are guaranteed at least three examinations (including the regular examination opportunity) according to the regulations in the syllabus that the student was originally registered on for a period of a maximum of two years from the time that the previous syllabus ceased to apply or that the course ended.