Home

Пятница 10-го декабря, 18-00

Пятница, 10 декабря, ауд. 402. Начало в 18:00.

Докладчик: Ю. Беляева (Академический Университет).

Тема: Явная конструкция графов Рамсея без треугольников.

Abstract

Число Рамсея $ R(3,m) $ это минимальное число $ n $ такое что любой граф из $ n $ вершин содержит либо треугольник, либо независимое множество размера $ m $. Для чисел Рамсея $ R(3, m) $ при помощи вероятностного метода была доказана оценка $ \Theta(m^2/\log{m}) $. Представляет большой интерес задача построения примеров графов без треугольников, с числом независимости $ m $ и с как можно большим числом вершин. В докладе будет описана явная конструкция графа не содержащего треугольников и независимых множеств размера $ m $ с $ \Omega(m^{3/2}) $ вершинами приведённая в статье Noga Alon ``Explicit Ramsey graphs and orthonormal labelings''. Семейство таких графов это графы Кэли, полученные с использованием проверочных матриц БЧХ-кодов. Для доказательства оценки на размер независимого множества в полученном графе будет использована $ \theta $-функция Ловаса.