Пятница, 13 апреля, ауд. 106. Начало в 18:00.
Докладчик: Кирилл Савенков (СПбГУ).
Тема: Оценка количества рёбер в 3-плоском графе.
Abstract
Назовём граф $k$-плоским, если его можно изобразить на плоскости так, что каждое ребро пересекает не более $k$ других ребер. Основная задача - оценить сверху количество ребер в k-плоском графе на n вершинах без петель и кратных ребер. Известный результат на эту тему (J. Path, G. Toth, 1997):
В $k$-плоском графе $G$ выполняется $e(G) \le (k+3) (v(G) - 2)$ при $v(G) > 24, k \le 4$.
При $k = 0, 1$ и $2$ эта оценка точна. При $k = 3$ оценка не точна. Будет доказана оценка порядка $5.5 v(G)$, которая с точки зрения мультипликативной константы является точной.
