Раскраски би-однородных гиперграфов
Автор: Ахмеджанова М.Б.
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Информатика и управление
Статья в выпуске: 3 (51) т.13, 2021 года.
Бесплатный доступ
Рассматриваются би-однородные гиперграфы, т.е. такие гиперграфы, в которых размеры ребер бывают двух типов. Для гиперграфа H пусть f(H) равно математическому ожиданию количества одноцветных ребер, когда синий и красный цвет присваивается каждой вершине независимо с вероятностью 1/2. Известно, что если минимальный размер ребра в неоднородном гиперграфе равен k и f(H) C log k, то такой гиперграф H можно правильно раскрасить в два цвета. В работе мы улучшаем оценку на функцию f(H) рассматривая раскраску, при которой в би-однородном гиперграфе H = (V, E1, E2) нет красных ребер из E1 и одновременно нет синих ребер из E2.
Гиперграф, правильная раскраска, неоднородные гиперграфы
Короткий адрес: https://sciup.org/142231009
IDR: 142231009 | DOI: 10.53815/20726759_2021_13_3_23
Список литературы Раскраски би-однородных гиперграфов
- Beck J. On three-chromatic hypergraphs // Discrete Math. 1978. N 29. P. 127-137.
- Duraj L., Gutowski G., Kozik J. A note on two-colorability of nonuniform hypergraphs // ICALP. 2018. N 46. P. 1-13.
- Duraj L., Kozik J., Shabanov D. Random hypergraphs and property B // Eur. J. Comb. 2021. N 91. P. 103205.
- Erd˝os. P. On a combinatorial problem. II // Acta Math. Acad. Sci. Hungar. 1964. N 15:3-4. P. 445-447.
- Erd˝os P., Hajnal A. On a property of families of sets // Acta Math. Acad. Sci. Hungar. 1961. N 12:1-2. P. 87-123.
- Erd˝os P., Lova'sz L. Problems and results on 3-chromatic hypergraphs and some related questions // Infinite and Finite Sets, Colloquia Mathematica Societatis Janos Bolyai. 10, Amsterdam: North Holland, 1973. P. 609-627.
- Gebauer H. On the construction of 3-chromatic hypergraphs with few edges // Journal of Combinatorial Theory. Series A. 2013. N 120:7. P. 1483-1490.
- Kozik J. Improving Gebauer's Construction of 3-Chromatic Hypergraphs with Few Edges // Proceedings of the 48th International Colloquium on Automata, Languages, and Programming. 2021.
- Radhakrishnan J., Srinivasan A. Improved bounds and algorithms for hypergraph two-coloring // Random Structures and Algorithms. 2000. N 16:1. P. 4-32.
- Shabanov D. Around Erd˝os-Lovasz problem on colorings of non-uniform hypergraphs // Discrete Math. 2015. N 338:11. P. 1976-1981.
