First and Second Order Signatures of Extreme Uniform Hypergraphs and Their Relationship with Vectors of the Vertex Degrees

T. Yu. Goltsova; Гольцова Т. Ю.; E. K. Egorova; Егорова Е. К.; V. Yu. Leonov; Леонов В. Ю.; A. V.  Mokryakov; Мокряков А. В.

doi:10.31857/S0002338823040042

First and Second Order Signatures of Extreme Uniform Hypergraphs and Their Relationship with Vectors of the Vertex Degrees

Authors: Goltsova T.Y.¹, Egorova E.K.²^,3, Leonov V.Y.³, Mokryakov A.V.¹^,2
Affiliations:
1. Kosygin Russian State University (Technologies, Design, Art), Moscow, Russia
2. Moscow Aviation Institute (National Research University), Moscow, Russia
3. Federal Research Center “Computer Science and Control,” Russian Academy of Sciences, Moscow, Russia
Issue: No 4 (2023)
Pages: 84-97
Section: ДИСКРЕТНЫЕ СИСТЕМЫ
URL: https://journals.rcsi.science/0002-3388/article/view/136875
DOI: https://doi.org/10.31857/S0002338823040042
EDN: https://elibrary.ru/OCGQCV
ID: 136875

Cite item

Full Text

Open Access
Restricted Access

Access granted
Restricted Access

Subscription Access

Abstract
About the authors
References
Supplementary files
Statistics

Abstract

The adjacency matrices of extremal 3-uniform hypergraphs occupy a significant amount of computer memory. The solution of two problems is considered: to propose an efficient way of representing and storing such matrices and to find fast algorithms that allow us to operate just with vectors of the vertex degrees and signatures (characteristics of adjacency matrices), without using adjacency matrices in memory. As part of the first task, a second-order signature that uniquely defines an extremal 3-uniform hypergraph without using its adjacency matrix is described. A mechanism for compressing the second-order signature is also proposed, which contributes to greater storage efficiency. For the second problem, a number of algorithms are presented to describe the relationship between the vector of the vertex degrees and signatures of both the first and second orders. In addition, it is shown that an arbitrary second-order signature constructed under a number of constraints always has an extremal 3-uniform hypergraph corresponding to it.

References

Зыков А.А. Гиперграфы // УМН. 1974. Т. XXIX. № 6 (180). С. 89–154.
Попков В.К. О моделировании городских транспортных систем гиперсетями // АиТ. 2011. № 6. С. 179–189.
Миков А.И., Миков А.А. Свойства геометрических гиперграфов беспроводных компьютерных сетей // Информатизация и связь. 2020. № 4. С. 60–66. https://doi.org/10.34219/2078-8320-2020-11-4-60-66
Александров П.С. Комбинаторная топология. М.: Гостехтеориздат, 1947. 660 с.
Бобу А.В., Куприянов А.Э., Райгородский А.М. О числе ребер однородного гиперграфа с диапазоном разрешенных пересечением // Проблемы передачи информации. 2017. Т. 53. № 4. С. 16–42.
Балобанов А.Е., Шабанов Д.А. О числе независимых множеств в простых гиперграфах // Математические заметки. 2018. Т. 103. № 1. С. 38–48. https://doi.org/10.4213/mzm11508
Денисов И.О., Шабанов Д.А. О концентрации значений чисел независимости случайных гиперграфов // Дискретная математика. 2021. Т. 33. № 4. С. 32–46. https://doi.org/10.4213/dm1676
Захаров П.А., Шабанов Д.А. О максимальном разрезе в случайном гиперграфе // Доклады Российской академии наук. Математика, информатика, процессы управления. 2021. Т. 501. № 1. С. 26–30. https://doi.org/10.31857/S2686954321060187
Райгородский А.М., Черкашин Д.Д. Экстремальные задачи в раскрасках гиперграфов // УМН. 2020. Т. 75. № 1 (451). С. 95–154. https://doi.org/10.4213/rm9905
Бондаренко В.А., Николаев А.В. Об одном классе гиперграфов и о вершинах релаксаций разрезного многогранника // ДАН. 2012. Т. 442. № 3. С. 300–302.
Егорова Е.К., Мокряков А.В., Суворова А.А., Цурков В.И. Алгоритм передачи многомерных данных с использованием экстремальных однородных гиперграфов // Изв. РАН. ТиСУ. 2021. № 1. С. 73–78.
Каменев А.Р., Ирбитский И.С., Пашковская Е.А. Методы подбора ключа для алгоритмов шифрования на графах // Сб. тез. работ ММНК XLVIII Гагаринские чтения – 2022. М.: Перо, 2022. С. 252.
Лежинский М.В. Концепция топологически-ориентированных хэш-функций // Сб. тез. работ ММНК XLVIII Гагаринские чтения – 2022. М.: Перо, 2022. С. 252.
Mironov A.A. Minimax under Transportation Constraints. Dordrecht: Kluwer Acad. Publ., 1999. 309 p.
Миронов А.А. Равномерные обобщенные графы // ДАН. 1996. Т. 351. № 4. С. 465–468.
Мокрозуб В.Г., Немтинов В.А., Мордвин А.С., Илясов А.А. Применение -ориентированных гиперграфов и реляционных баз данных для структурного и параметрического синтеза технических систем // Прикл. информатика. 2010. № 4 (28). С. 115–122.
Суворова А.А., Берецкий И.С. Алгоритм потокового шифрования на экстремальных k-однородных гиперграфах // Сб. тез. работ ММНК Гагаринские чтения – 2020. М.: МАИ, 2020. С. 510–511.
Корельяно Л.Н., Разборов А.А. Семантические пределы плотных комбинаторных объектов // УМН. 2020. Т. 75. № 4(454). С. 45–152.https://doi.org/10.4213/rm9956
Prüfer H. Neuer Beweis eines Satzes Гjber Permutationen // Arch. Math. Phys. 1918. V. 27. P. 742–744.
Кузьмин О.В., Чернигова А.Г. Автоматизация комбинаторного кодирования и декодирования корневых деревьев // Современные технологии. Системный анализ. Моделирование. 2015. № 1 (45). С. 84–88.
Мокряков А.В. Представление гиперграфов в качестве алгебраической структуры // Изв. РАН. ТиСУ. 2011. № 5. С. 53–59.
Погребной В.К., Погребной А.В. Исследование полиномиальности метода вычисления интегрального описателя структуры графа // Изв. Томск. политехн. ун-та. 2013. Т. 323. № 5. С. 146–151.
Гольцова Т.Ю., Егорова Е.К., Мокряков А.В., Цурков В.И. Сигнатуры экстремальных 2-однородных гиперграфов // Изв. РАН. ТиСУ. 2021. Т. 6. № 6. С. 52–60.
Мокряков А.В., Цурков В.И. Восстановление 2-комплексов по целочисленному неотрицательному вектору // АиТ. 2011. № 12. С. 130–143.
Миронов А.А. Геометрия точек пространства , реализуемых в граф // УМН. 1977. Т. XXXII. № 6 (198). С. 232–233.
Костяной Д.С., Мокряков А.В., Цурков В.И. Алгоритмы восстановления гиперграфов по заданному вектору степеней вершин // Изв. РАН. ТиСУ. 2014. № 4. С. 43–48.