Семинары: Ю. А. Будников, Асимптотическая верхняя оценка хроматического индекса случайных гиперграфов

СЕМИНАРЫ


Семинар отдела дискретной математики МИАН 15 марта 2011 г. 16:00, г. Москва, МИАН, комн. 511 (ул. Губкина, 8)

Асимптотическая верхняя оценка хроматического индекса случайных гиперграфов Ю. А. Будников
Аннотация: Показано, что хроматический индекс случайного однородного гиперграфа $G(n)$ асимптотически с вероятностью 1 не превосходит $cD(n)\log k(n)$, $n\to\infty$, где $n$ — число вершин $G(n)$, $D(n)$ — математическое ожидание степени вершины $G(n)$, $k(n)=o(n)$ — число вершин на любом ребре $G(n)$, $c>1$ — некоторая константа.