Established by: Faculty Board of Science and Technology, 2024-09-19
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.
