Пятница, 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$-функция Ловаса.
