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

Дискрет. матем., 2020, том 32, выпуск 4, страницы 10–37 (Mi dm1621)

Новая нижняя оценка наименьшего числа ребер простого однородного гиперграфа без свойства $B_k$

Ю. А. Демидович

Московский физико-технический институт (национальный исследовательский университет)

Аннотация: Гиперграф $H=(V,E)$ обладает свойством $B_k$, если существует такая раскраска множества $V$ в два цвета, что в каждом ребре содержится по крайней мере $k$ вершин каждого цвета. Гиперграф называется простым, если любые два его ребра имеют не более одной общей вершины. В статье получена новая нижняя оценка для наименьшего количества ребер $n$-однородного простого гиперграфа, не обладающего свойством $B_k$.

Ключевые слова: простые гиперграфы, раскраски гиперграфов, свойство $B$.

УДК: 519.174, 519.179.1

Статья поступила: 30.07.2020

DOI: 10.4213/dm1621


 Англоязычная версия: Discrete Mathematics and Applications, 2022, 32:3, 155–176

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


© МИАН, 2024