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

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

Бородин С. О., Тараненко А. А.
Дискретный анализ и исследование операций, 31, 3, 54–78 (2024)
Скачать статью

УДК 519.179.1+519.174.7 
DOI: 10.33048/daio.2024.31.784

Аннотация:

Гиперграфом подматриц $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.

Литература:
  1. Дельсарт Ф. Алгебраический подход к схемам отношений теории кодирования. М.: Мир, 1976. 134 с.
     
  2. Godsil C. Compact graphs and equitable partitions // Linear Algebra Appl. 1997. V. 255, No. 1–3. P. 259–266. DOI: 10.1016/S0024-3795(97)83595-1.
     
  3. Визинг В. Г. Дистрибутивная раскраска вершин графа // Дискрет. анализ и исслед. операций. 1995. Т. 2, № 4. С. 3–12.
     
  4. Пузынина С. А. Периодичность совершенных раскрасок бесконечной прямоугольной решётки // Дискрет. анализ и исслед. операций. Сер. 1. 2004. Т. 11, № 1. С. 79–92.
     
  5. Krotov D. S. Perfect colorings of the infinite square grid: Coverings and twin colors // Electron. J. Comb. 2023. V. 30, No. 2. Paper ID P2.4. 59 p. DOI: 10.37236/10005.
     
  6. Axenovich M. A. On multiple coverings of the infinite rectangular grid with balls of constant radius // Discrete Math. 2003. V. 268, No. 1–3. P. 31–49. DOI: 10.1016/S0012-365X(02)00744-6.
     
  7. Августинович С. В., Могильных И. Ю. Совершенные раскраски графов Джонсона $J(8, 3)$ и $J(8, 4)$ в два цвета // Дискрет. анализ и исслед. операций. 2010. Т. 17, № 2. С. 3–19.
     
  8. Хорошилова Д. Б. О циркулярных совершенных раскрасках в два цвета // Дискрет. анализ и исслед. операций. 2009. Т. 16, № 1. С. 80–92.
     
  9. Handbook of combinatorics. V. 1. Amsterdam: Elsevier, 1995. 2198 p.
     
  10. Потапов В. Н., Августинович С. В. Комбинаторные дизайны, разностные множества и бент-функции как совершенные раскраски графов и мультиграфов // Сиб. мат. журн. 2020. Т. 61, № 5. С. 1087–1100.
     
  11. Taranenko A. A. Perfect colorings of hypergraphs. Ithaca, NY: Cornell Univ., 2022. 20 p. (Cornell Univ. Libr. e-Print Archive; arXiv:2208.03447). DOI: 10. 48550/arXiv.2208.03447.
     
  12. Handbook of combinatorial designs. Boca Raton: Chapman & Hall/CRC, 2007. 1018 p.

Исследование выполнено за счёт Российского научного фонда (проект № 22– 11–00266, rscf.ru/project/22-11-00266).

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

E-mail: s.borodin@g.nsu.ru

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

E-mail: taa@math.nsc.ru

Статья поступила 4 сентября 2023 г.
После доработки — 7 февраля 2024 г.
Принята к публикации 22 марта 2024 г.

Abstract:

A submatrix hypergraph $G_{n \times m}$ is a hypergraph whose vertices are entries of an $n \times m$ matrix and hyperedges are submatrices of order $2$. In this paper, we consider perfect colorings of submatrix hypergraphs and study their parameters. We provide several constructions of perfect colorings of $G_{n \times m}$ and prove that the incidence matrices of $2$-designs are perfect colorings of the submatrix hypergraph. Moreover, we describe all perfect $2$-colorings of hypergraphs $G_{2 \times m}$ and $G_{3 \times m}$. 
Illustr. 1, bibliogr. 12. 

References:
  1. P. Delsarte, An Algebraic Approach to the Association Schemes of Coding Theory (N. V. Philips’ Gloeilampenfabrieken, Eindhoven, 1973; Mir, Moscow, 1976 [Russian]).
     
  2. C. Godsil, Compact graphs and equitable partitions, Linear Algebra Appl. 255 (1–3), 259–266 (1997), DOI: 10.1016/S0024-3795(97)83595-1.
     
  3. V. G. Vizing, Distributive coloring of graph vertices, Diskretn. Anal. Issled. Oper. 2 (4), 3–12 (1995) [Russian].
     
  4. S. A. Puzynina, Periodicity of perfect colorings of an infinite rectangular grid, Diskretn. Anal. Issled. Oper., Ser. 1, 11 (1), 79–92 (2004) [Russian].
     
  5. D. S. Krotov, Perfect colorings of the infinite square grid: Coverings and twin colors, Electron. J. Comb. 30 (2), ID P2.4 (2023), DOI: 10.37236/10005.
     
  6. M. A. Axenovich, On multiple coverings of the infinite rectangular grid with balls of constant radius, Discrete Math. 268 (1–3), 31–49 (2003), DOI: 10. 1016/S0012-365X(02)00744-6.
     
  7. S. V. Avgustinovich and I. Yu. Mogilnykh, Perfect colorings of the Johnson graphs $J(8, 3)$ and $J(8, 4)$ with two colors, Diskretn. Anal. Issled. Oper. 17 (2), 3–19 (2010) [Russian] [J. Appl. Ind. Math. 5 (1), 19–30 (2011)].
     
  8. D. B. Khoroshilova, On two-colour perfect colourings of circular graphs, Diskretn. Anal. Issled. Oper. 16 (1), 80–92 (2009) [Russian].
     
  9. Handbook of Combinatorics, Vol. 1 (Elsevier, Amsterdam, 1995).
     
  10. V. N. Potapov and S. V. Avgustinovich, Combinatorial designs, difference sets, and bent functions as perfect colorings of graphs and multigraphs, Sib. Mat. Zh. 61 (5), 1087–1100 (2020) [Russian] [Sib. Math. J. 61 (5), 867–877 (2020)].
     
  11. A. A. Taranenko, Perfect colorings of hypergraphs (Cornell Univ., Ithaca, NY, 2022) (Cornell Univ. Libr. e-Print Archive, arXiv:2208.03447), DOI: 10. 48550/arXiv.2208.03447.
     
  12. Handbook of Combinatorial Designs (Chapman & Hall/CRC, Boca Raton, 2007).