Пятница 13 апреля, 18-00, ауд. 106

Пятница, 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)$, которая с точки зрения мультипликативной константы является точной.