Пятница, 10 декабря, ауд. 402. Начало в 18:00.
Докладчик: Ю. Беляева (Академический Университет).
Тема: Явная конструкция графов Рамсея без треугольников.
Abstract
Число Рамсея
![$ R(3,m) $](../../../sites/default/files/tex/833d67223d432181525d3677b5b061d7e989f981/index.png)
это минимальное число
![$ n $](../../../sites/default/files/tex/31360359740de028d2dd0d2cc8087938c3b61794/index.png)
такое что любой граф из
![$ n $](../../../sites/default/files/tex/31360359740de028d2dd0d2cc8087938c3b61794/index.png)
вершин содержит либо треугольник, либо независимое множество размера
![$ m $](../../../sites/default/files/tex/05b806fb3a39e75606f12e544fec1ae578c32b0b/index.png)
. Для чисел Рамсея
![$ R(3, m) $](../../../sites/default/files/tex/3428b2ae97dd0f7a5f1f5c044033a49292eb28a9/index.png)
при помощи вероятностного метода была доказана оценка
![$ \Theta(m^2/\log{m}) $](../../../sites/default/files/tex/d528750e71b05294b267c0db0e8aec4a851c06bc/index.png)
. Представляет большой интерес задача построения примеров графов без треугольников,
с числом независимости
![$ m $](../../../sites/default/files/tex/05b806fb3a39e75606f12e544fec1ae578c32b0b/index.png)
и с как можно большим числом вершин.
В докладе будет описана явная конструкция графа не содержащего треугольников и независимых множеств размера
![$ m $](../../../sites/default/files/tex/05b806fb3a39e75606f12e544fec1ae578c32b0b/index.png)
с
![$ \Omega(m^{3/2}) $](../../../sites/default/files/tex/f9235e3ecfb0350fec8ee2a73444757c4c9707dd/index.png)
вершинами приведённая в статье Noga Alon ``Explicit Ramsey graphs and orthonormal labelings''. Семейство таких графов это графы Кэли, полученные с использованием проверочных матриц БЧХ-кодов. Для доказательства оценки на размер независимого множества в полученном графе будет использована
![$ \theta $](../../../sites/default/files/tex/b7f39e50f11fffced0448762045e57c36148f612/index.png)
-функция Ловаса.