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

Матем. заметки, 2020, том 107, выпуск 3, страницы 454–465 (Mi mzm12379)

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

О предписанном хроматическом числе полных многодольных гиперграфов и кратных покрытиях независимыми множествами

Д. А. Шабановabc, Т. М. Шайхееваb

a Московский физико-технический институт (государственный университет), г. Долгопрудный, Московская обл.
b Московский государственный университет имени М. В. Ломоносова
c Национальный исследовательский университет "Высшая школа экономики", г. Москва

Аннотация: Работа посвящена предписанным раскраскам однородных гиперграфов.
Пусть $H(m,r,k)$ – это полный $r$-дольный $k$-однородный гиперграф с равными размерами долей $m$, в котором каждое ребро содержит ровно по одной вершине из некоторых $k\leqslant r$ долей. С помощью результатов о кратных покрытиях независимыми множествами установлено, что для фиксированных $k$ и $r$ предписанное хроматическое число $H(m,r,k)$ равно $(1+o(1))\log_{r/(r-k+1)}(m)$ при $m\to\infty$.
Библиография: 22 названия.

Ключевые слова: гиперграфы, независимые множества, предписанные раскраски, кратные покрытия.

УДК: 519.179.1+519.174.7+519.174.3

Поступило: 17.03.2019
Исправленный вариант: 16.07.2019

DOI: 10.4213/mzm12379


 Англоязычная версия: Mathematical Notes, 2020, 107:3, 499–508

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


© МИАН, 2024