Рекуррентные верхние оценки в задаче Эрдеша-Хайнала о раскраске гиперграфа и в ее обобщениях
Автор: Тепляков Сергей Михайлович
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Раскраски гиперграфов
Статья в выпуске: 1 (13) т.4, 2012 года.
Бесплатный доступ
В 1961 году П. Эрдеш и А. Хайнал поставили задачу об отыскании величины m(n), равной наименьшему количеству ребер в n-однородном гиперграфе с хроматическим числом больше двух. Сейчас известны различные асимптоти- ческие оценки для m(n). Однако точные значения найдены лишь при n ≤ 3. При других малых n есть только рекуррентные оценки. Мы рассматриваем важное обобщение задачи, а именно, нас интересует величина mk(n), рав- ная минимальному числу ребер в n-однородном гиперграфе, не допускающем двухцветной раскраски множества своих вершин, при которой каждое ребро содержит не менее k вершин первого цвета и не менее k вершин второго цвета. Нам удается найти ряд рекуррентных оценок для mk(n), которые при многих n и k значительно уточняют все ранее доказанные результаты.
Гиперграф, хроматическое число
Короткий адрес: https://sciup.org/142186203
IDR: 142186203
Список литературы Рекуррентные верхние оценки в задаче Эрдеша-Хайнала о раскраске гиперграфа и в ее обобщениях
- Erdos P., Hajnal A. On a property of families of sets//Acta Mathematica of the Academy of Sciences, Hungary.-1961.-V. 12, N 1-2.-P. 87-123.
- Radhakrishnan J., Srinivasan A. Improved bounds and algorithms for hypergraph twocoloring//Random Structures and Algorithms.-2000.-V. 16, N 1.-P. 4-32.
- Erdos P. On a combinatorial problem, II//Acta Mathematica of the Academy of Sciences, Hungary.-1964.-V. 15, N 3-4, P. 445-447.
- Шабанов Д. А. Об одной комбинаторной задаче Эрдеша//Доклады РАН. -2004.-Т. 396, № 2.-С. 166-169.
- Розовская А. П. Экстремальные комбинаторные задачи для двухцветных раскрасок гиперграфов//Матем. заметки.-2011.-Т. 90, № 4.-С. 584-598.
- Райгородский А.М., Шабанов Д. А. Задача Эрдеша-Хайнала о раскрасках гиперграфов, ее обобщения и смежные проблемы//УМН. -2011.-Т. 66, вып. 5.-С. 109-182.
- Шабанов Д. А. Экстремальные задачи для раскрасок равномерных гиперграфов//Известия РАН. -Сер. математическая.-2007.-Т. 71, № 6.-С. 183-222.
- Abbott H. L., Moser L. On a combinatorial problem of Erd˝os and Hajnal//Canadian Mathematical Bullettin.-1964.-V. 7.-P. 177-181.
- Abbott H. L., Hanson D. On a combinatorial problem of Erd˝os//Canadian Mathematical Bullettin.-1969.-V. 12.-P. 823-829.
- Toft B. On color critical hypergraphs//Infinite and Finite Sets, eds. A. Hajnal et. al.-Amsterdam: North Holland, 1975.-P. 1445-1457.
- Розовская А. П., Титова М. В., Шабанов Д. А. О половинных раскрасках гиперграфов//Фундаментальная и прикладная математика.-2009.-Т. 15, №7.-С. 141-163.
- Kostochka A. V. Color-Critical Graphs and Hypergraphs with Few Edges: A Survey//More Sets, Graphs and Numbers. Bolyai Society Mathematical Studies, eds. E. Gyori, G.O.H.Katona, L. Lovasz.-V. 15.-Springer, 2006.-P. 175-198.
- Райгородский А.М. Системы общих представителей в комбинаторике и их приложениях.-М.: МЦНМО, 2009.
