Home

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