An advanced school for young researchers featuring three minicourses in vibrant areas of mathematics and computer science. The target audience includes graduate, master, and senior bachelor students of any mathematical speciality.
|Maria Chudnovsky||Fedor Fomin||Madhu Sudan|
|Princeton University||University of Bergen||Harvard University|
The study of the structure of graphs with certain induced subgraphs forbidden has been an active area of research in graph theory in recent years, after the long standing Strong Perfect Graph Conjecture was proved using structural methods. The goal of this course is to cover some of the recent developments in the area. We will start with simple theorems about forbidden induced subgraphs, and work our way up to the latest research results. The topics will include perfect graphs, claw-free graphs, coloring graphs with forbidden induced subgraphs, algorithms for detecting induced subgraphs and others.
The theorems of Bollobás (1965) and Lovász (1977) about set pairs are fundamental results in extremal set theory. In this tutorial, we discuss some algorithmic applications of these classical theorems. In particular, we learn about representative families and their role in kernelization, enumeration, and parameterized algorithms.
In this series of talks, we will quickly introduce the mathematical notions of an error-correcting code, and the associated notions of Encoding and Decoding Algorithms. After reviewing some of the classical results on the existence, construction and limits on error-correcting codes, we will zoom in on two results in the field.
Both results come with polynomial time algorithms!
The school is supported by a grant from the Government of the Russian Federation, agreements 075-15-2019-1619 and 075-15-2019-1620.