RUS  ENG
Полная версия
СЕМИНАРЫ

Семинар отдела дискретной математики МИАН
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$ — некоторая константа.


© МИАН, 2024