О многоцветных раскрасках гиперграфов
Автор: Тепляков С.М.
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Математика
Статья в выпуске: 1 (33) т.9, 2017 года.
Бесплатный доступ
В 1961 году Эрдеш и Хайнал поставили задачу об отыскании величины �(�), равной наименьшему количеству ребер в �-однородном гиперграфе с хроматическим числом больше двух. На текущий момент известны множество оценок данной величины, а также и ее обобщений. В данной статье мы рассмотрим два варианта обобщения данной величины: (�), введенное в 2004 году А.М. Райгородским и Д.А. Шабановым, и�� (�, �), которое мы определим по ходу статьи. В работе нам удалось получить верхние оценки указанных величин при близких к �/2 для первого обобщения и близких к �/� для второго обобщения. Кроме того, мы получили результаты, связанные со свойствами этих оценок.
Гиперграф, хроматическое число
Короткий адрес: https://sciup.org/142186168
IDR: 142186168
Список литературы О многоцветных раскрасках гиперграфов
- Kostochka A.V. Color-Critical Graphs and Hypergraphs with Few Edges: A Survey//More Sets, Graphs and Numbers (Ed. by E. Gy˝ori, G.O.H. Katona, L. Lov´asz). Budapest: Bolyai Society Mathematical Studies. 2006. V. 15. P. 175-198.
- Erd˝os P., Hajnal A. On a property of families of sets//Acta Mathematica of the Academy of Sciences. 1961. V. 12, N 1-2. P. 87-123.
- Райгородский А.М., Шабанов Д.А. Задача Эрдеша-Хайнала о раскрасках гиперграфов, ее обобщения и смежные проблемы//Успехи математических наук. 2011. Т. 66, вып. 5. С. 109-182.
- Radhakrishnan J., Srinivasan A. Improved bounds and algorithms for hypergraph two-coloring//Random Structures and Algorithms. 2000. V. 16, N 1. P. 4-32.
- Erd˝os P. On a combinatorial problem, II//Acta Mathematica of the Academy of Sciences. 1964. V. 15, N 3-4. P. 445-447.
- Шабанов Д.А. Об одной комбинаторной задаче Эрдеша//Доклады Академии наук. 2004. Т. 396, № 2. С. 166-169.
- Шабанов Д.А. Рандомизированные алгоритмы раскрасок гиперграфов//Математический сборник. 2008. Т. 199, № 7. С. 139-160.
- Розовская А.П. О двухцветных раскрасках общего вида для равномерных гиперграфов//Доклады Академии наук. 2009. Т. 429, № 3. С. 309-311.
- Тепляков С.М. Верхняя оценка в задаче Эрдеша-Хайнала о раскраске гиперграфа//Математические заметки. 2013. Т. 93, вып. 1. С. 148-151.
- Розовская А.П., Титова М.В., Шабанов Д.А. О половинных раскрасках гиперграфов//Фундаментальная и прикладная математика. 2009. Т. 15, вып. 7. С. 141-163.
- Тепляков С.М. Рекуррентные верхние оценки в задаче Эрдеша-Хайнала о раскраске гиперграфа и в ее обобщениях//Труды МФТИ. 2012. Т. 4, № 1(13). С. 141-150.
- Черкашин Д.Д., Куликов А.Б. О двухцветных раскрасках гиперграфов//Доклады Aкадемии наук. 2011. Т. 463, № 3. С. 316-319.
- Карацуба А.А. Основы аналитической теории чисел. М.: Эдиториал УРСС, 2004.
- Rosser B. The �-th Prime is greater than � log �. London: Proc. London. Math. Soc., 1938.
