Лекции по комбинаторике

Габор Тардош – крупнейший специалист в комбинаторике, дискретной геометрии и теоретических вычислительных науках, научный сотрудник Института математики имени Реньи Венгерской академии наук в Будапеште. Один из его самых известных результатов – алгоритмическая версия локальной леммы Ловаса (совместно с Мозером). В 1992 году Габор Тардош получил премию Европейского математического общества для молодых исследователей. В 2018 году был приглашенным докладчиком на Международном математическом конгрессе.

Название цикла лекций: Extremal theory of vertex- and edge-ordered graphs

The basic question of Turan type extremal graph theory is the maximum number of edges in a simple graph on n vertices that does not contain a specified "forbidden" subgraph (or any one of several forbidden subgraphs). This is a classical topic of combinatorics with many deep results and lot of questions that are still open.

In my survey talk I will focus on extensions of this theory to simple graphs with an additional structure, namely a linear order on the set of vertices or edges. A single simple graph has several vertex order and by forbidding just one of them we obtain different extremal questions. Introducing either a vertex- or an edge-order makes the theory richer and more suitable to (mostly geometric) applications.

I will highlight several specific open problems about both vertex- and edge-ordered graphs. I will mention results from numerous researchers, among them Balazs Keszegh, Daniel Korandi, Jesse Geneson, Daniel Gerbner, Adam Marcus, Abhishek Methuku, Daniel Nagy, Janos Pach, Seth Pettie, Domotor Palvolgyi, Istvan Tomon, Mate Vizer, Creig Weidert, etc.

Расписание лекций:

• 26 ноября (вторник) 16:00 - 17:00, Поточная аудитория Физтех.Арктики;

• 27 ноября (среда) 16:00 - 17:00, Поточная аудитория Физтех.Арктики;

• 28 ноября (четверг) 17:00 - 18:00, Поточная аудитория Физтех.Арктики.

Иштван Томон — молодой и яркий специалист в комбинаторике, младший научный сотрудник (постдок) Швейцарской высшей технической школы Цюриха. Известен своими результатами в экстремальной комбинаторике и исследованиями частично упорядоченных множеств. Трижды участвовал в Международной олимпиаде школьников: в 2006 году получил серебряную медаль, в 2008 и 2009 годах стал золотым медалистом.

Название цикла лекций: Intersection graphs of geometric objects

The intersection graph of some family of geometric objects (e.g. line segments, axis parallel rectangles, convex sets) is the graph, whose vertices correspond to the elements of this family, and two vertices are joined by an edge if the corresponding objects have a nonempty intersection. In the past 60 years, graph theoretic properties of such intersection graphs are extensively studied both from a theoretical and a practical point of view. In this mini-course, I will survey some classical and recent results about Ramsey and coloring properties of geometric intersection graphs, along with numerous open problems.

Расписание лекций:

• 29 ноября (пятница) 17:00 - 18:30, Поточная аудитория Физтех.Арктики;

• 2 декабря (понедельник) 17:00 - 18:30, 414 ГК.