RUS  ENG
Полная версия
ЖУРНАЛЫ // Математический сборник // Архив

Матем. сб., 2008, том 199, номер 7, страницы 139–160 (Mi sm3931)

Эта публикация цитируется в 11 статьях

Рандомизированные алгоритмы раскрасок гиперграфов

Д. А. Шабанов

Московский государственный университет им. М. В. Ломоносова, механико-математический факультет

Аннотация: В работе исследуются обобщения классической задачи П. Эрдёша о свойстве $B$ гиперграфов. Согласно определению Эрдёша гиперграф обладает свойством $B$, если существует двухцветная раскраска множества его вершин, в которой ни одно ребро гиперграфа не является одноцветным. Требуется найти величину $m(n)$, равную минимально возможному количеству ребер в $n$-равномерном (каждое ребро содержит ровно $n$ вершин) гиперграфе, не обладающем свойством $B$. Рассматриваются более общие постановки проблемы, приводится ряд параметрических свойств гиперграфов и соответствующих им экстремальных величин. Основные результаты улучшают ранее известные нижние оценки этих экстремальных величин.
Библиография: 9 названий.

УДК: 519.179.1+519.157

MSC: Primary 05C15; Secondary 05C65, 05C85, 05D40

Поступила в редакцию: 06.08.2007

DOI: 10.4213/sm3931


 Англоязычная версия: Sbornik: Mathematics, 2008, 199:7, 1089–1110

Реферативные базы данных:


© МИАН, 2024