|
|
Научно-исследовательский семинар кафедры дискретной математики ФИВТ МФТИ
21 октября 2014 г., г. Москва, ул. Льва Толстого, д. 16, Яндекс, БЦ «Морозов», ауд. «7.Пятниц»
|
 |
|
 |
|
|
|
Гиперграфы с очень большим хроматическим числом
Д. А. Шабановab, И. А. Акользин
a Московский государственный университет им. М. В. Ломоносова, механико-математический факультет
b Московский физико-технический институт (государственный университет), г. Долгопрудный Московской обл.
|
| Количество просмотров: |
| Эта страница: | 250 |
|
Аннотация:
В докладе пойдет речь об известной проблеме Эрдеша-Хайнала о раскрасках гиперграфов. Пусть m(n,r) - это минимально возможное число ребер n-однородного гиперграфа с хроматическим числом больше r. Нами получены новые нижние и верхние оценки m(n,r) в случае, когда значение параметра r очень велико по сравнению с параметром однородности n. Кроме того, будет рассмотрена аналогичная постановка задачи для максимальной реберной степени гиперграфа. Доказательства основаны на недавней работе Д. Черкашина и Я. Козика, а также на конструкции А. Сидоренко для верхних оценок турановских плотностей.
|
|
Обратная связь: