RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретный анализ и исследование операций // Архив

Дискретн. анализ и исслед. опер., 2024, том 31, выпуск 3, страницы 54–78 (Mi da1353)

Совершенные раскраски гиперграфа подматриц

С. О. Бородин, А. А. Тараненко

Институт математики им. С. Л. Соболева, пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

Аннотация: Гиперграфом подматриц $G_{n\times m}$ назовём гиперграф, вершинами которого являются элементы матрицы размера $n\times m,$ а гиперрёбрами  — все возможные подматрицы порядка $2$. В настоящей работе рассматриваются совершенные раскраски гиперграфов $G_{n\times m}$ и условия на их параметры инцидентности. Предложено несколько конструкций совершенных раскрасок $G_{n\times m}$ и доказано, что матрицы инцидентности $2$-схем являются совершенными раскрасками гиперграфа подматриц. Кроме того, описаны совершенные $2$-раскраски гиперграфов $G_{2\times m}$ и $G_{3\times m}.$ Ил. 1, библиогр. 12.

Ключевые слова: гиперграф, симметричная 2-схема, совершенная раскраска.

УДК: 519.179.1+519.174.7

Статья поступила: 04.09.2023
Переработанный вариант: 07.02.2024
Принята к публикации: 22.03.2024

DOI: 10.33048/daio.2024.31.784


 Англоязычная версия: Journal of Applied and Industrial Mathematics, 2024, 18:3, 424–440


© МИАН, 2025