Балаж Паткош, доклад по экстремальной теории графов

18 декабря, 2019
Долгопрудный
МФТИ

Доклад Балажа Паткоша "Turán problems with dergee conditions"

18 декабря в 17:00 в аудитории 2.35 Цифра в рамках "Межкафедрального семинара по дискретной математике" венгерский математик Балаж Паткош сделает доклад по экстремальной теории графов. Балаж Паткош был приглашён лабораторией Комбинаторных и Геометрических структур Физтех-школы прикладной математики и информатики (ФПМИ) МФТИ.

18 декабря 17:00 2.35 Цифра

Лектор — Балаж Паткош, специалист в комбинаторике, научный сотрудник Института математики имени Реньи Венгерской академии наук в Будапеште (www.renyi.hu/~patkos/), был постдоком в Тель-Авивском и Билефельдском университетах по программе гранта Марии Склодовская-Кюри. Известен своими исследованиями задач вероятностной и экстремальной комбинаторики.

Abstract:

Turán problems ask for the maximum number $ex(n,F)$ of edges that an $n$-vertex graph $H$ can have without containing a copy of the forbidden graph $F$. These problems are the starting points of extremal graph theory and there have been an enormous amount of research in the area in the past century. There exist many generalizations and variants to this kind of problems. In my talk, I will survey some recently introduced notions and the first couple of results concerning these notions all of which involve the degrees of either all vertices of the graph $H$ or of all vertices of the copy of $F$ in $H$. More precisely, I will talk about the following problems.

A subgraph $H$ of $G$ is singular if the vertices of $H$ either have the same degree in $G$ or have pairwise distinct degrees in $G$. The largest number of edges of a graph on $n$ vertices that does not contain a singular copy of $H$ is denoted by $T_S(n,H)$. We also explore the connection to the so-called $H$-WORM colorings (colorings without rainbow or monochromatic copies of $H$) and obtain new results regarding the largest number of edges that a graph with an $H$-WORM coloring can have.

The regular Turán number $rex(n,F)$ is the maximum number of edges that an $n$-vertex regular graph $H$ can have without containing a copy of $F$.

Посетить доклад приглашаются все желающие. Язык доклада - английский. Доклад рассчитан на студентов старших курсов, аспирантов и исследователей в области комбинаторики.