401-3055-64L  Algebraic Methods in Combinatorics

SemesterAutumn Semester 2021
LecturersB. Sudakov
Periodicitytwo-yearly recurring course
Language of instructionEnglish



Courses

NumberTitleHoursLecturers
401-3055-64 VAlgebraic Methods in Combinatorics2 hrs
Wed10:15-12:00IFW A 36 »
B. Sudakov
401-3055-64 UAlgebraic Methods in Combinatorics1 hrs
Mon12:15-13:00ML F 34 »
13:15-14:00ML F 34 »
B. Sudakov

Catalogue data

AbstractCombinatorics is a fundamental mathematical discipline as well as an essential component of many mathematical areas, and its study has experienced an impressive growth in recent years. This course provides a gentle introduction to Algebraic methods, illustrated by examples and focusing on basic ideas and connections to other areas.
Learning objectiveThe students will get an overview of various algebraic methods for solving combinatorial problems. We expect them to understand the proof techniques and to use them autonomously on related problems.
ContentCombinatorics is a fundamental mathematical discipline as well as an essential component of many mathematical areas, and its study has experienced an impressive growth in recent years. While in the past many of the basic combinatorial results were obtained mainly by ingenuity and detailed reasoning, the modern theory has grown out of this early stage and often relies on deep, well-developed tools.

One of the main general techniques that played a crucial role in the development of Combinatorics was the application of algebraic methods. The most fruitful such tool is the dimension argument. Roughly speaking, the method can be described as follows. In order to bound the cardinality of of a discrete structure A one maps its elements to vectors in a linear space, and shows that the set A is mapped to linearly independent vectors. It then follows that the cardinality of A is bounded by the dimension of the corresponding linear space. This simple idea is surprisingly powerful and has many famous applications.

This course provides a gentle introduction to Algebraic methods, illustrated by examples and focusing on basic ideas and connections to other areas. The topics covered in the class will include (but are not limited to):

Basic dimension arguments, Spaces of polynomials and tensor product methods, Eigenvalues of graphs and their application, the Combinatorial Nullstellensatz and the Chevalley-Warning theorem. Applications such as: Solution of Kakeya problem in finite fields, counterexample to Borsuk's conjecture, chromatic number of the unit distance graph of Euclidean space, explicit constructions of Ramsey graphs and many others.

The course website can be found at
https://moodle-app2.let.ethz.ch/course/view.php?id=15757
Lecture notesLectures will be on the blackboard only, but there will be a set of typeset lecture notes which follow the class closely.
Prerequisites / NoticeStudents are expected to have a mathematical background and should be able to write rigorous proofs.

Performance assessment

Performance assessment information (valid until the course unit is held again)
Performance assessment as a semester course
ECTS credits6 credits
ExaminersB. Sudakov
Typesession examination
Language of examinationEnglish
RepetitionThe performance assessment is offered every session. Repetition possible without re-enrolling for the course unit.
Mode of examinationwritten 180 minutes
Written aidsStudents are allowed to bring ONLY a printed copy of the lecture notes with no extra writing (highlighting and blank post-its are allowed).
This information can be updated until the beginning of the semester; information on the examination timetable is binding.

Learning materials

 
Main linkMoodle of the course
Moodle courseMoodle-Kurs / Moodle course
Only public learning materials are listed.

Groups

401-3055-64 UAlgebraic Methods in Combinatorics
GroupsG-01
Mon12:15-13:00ML F 34 »
G-02
Mon13:15-14:00ML F 34 »

Restrictions

There are no additional restrictions for the registration.

Offered in

ProgrammeSectionType
Cyber Security MasterElective CoursesWInformation
Data Science MasterCore ElectivesWInformation
Doctoral Dep. of Information Technology and Electrical EngineeringDoctoral and Post-Doctoral CoursesWInformation
Doctoral Department of MathematicsGraduate SchoolWInformation
Electrical Engineering and Information Technology MasterSpecialisation CoursesWInformation
Electrical Engineering and Information Technology MasterRecommended SubjectsWInformation
Electrical Engineering and Information Technology MasterRecommended SubjectsWInformation
Electrical Engineering and Information Technology MasterRecommended SubjectsWInformation
Electrical Engineering and Information Technology MasterRecommended SubjectsWInformation
Electrical Engineering and Information Technology MasterSpecialisation CoursesWInformation
Electrical Engineering and Information Technology MasterSpecialisation CoursesWInformation
Electrical Engineering and Information Technology MasterSpecialisation CoursesWInformation
Electrical Engineering and Information Technology MasterRecommended SubjectsWInformation
Electrical Engineering and Information Technology MasterSpecialisation CoursesWInformation
Computer Science MasterElective CoursesWInformation
Computer Science MasterMinor in Theoretical Computer ScienceWInformation
Mathematics BachelorSelection: Mathematical Optimization, Discrete MathematicsWInformation
Mathematics MasterSelection: Mathematical Optimization, Discrete MathematicsWInformation