|
|
Межкафедральный семинар МФТИ по дискретной математике
19 февраля 2014 г., г. Долгопрудный, МФТИ, Актовый зал Лабораторного корпуса
|
|
|
|
|
|
Гипотеза Шура в R^d
А. А. Полянский |
Количество просмотров: |
Эта страница: | 255 |
|
Аннотация:
Граф диаметров в \mathbb{R}^d — граф вершинами которого являются конечное множество точек в \mathbb{R}^d, а ребрами являются пары точек находящихся на расстоянии равном диаметру. Гипотеза Шура утверждает: максимальное число полных подграфов размера d (d-клик) в графе диаметров на n вершинах в d-мерном евклидовом пространстве равно n. В работе З. Шура, М.А. Пёлеса, X. Мартини, Я.С. Купитза гипотеза Шура была доказана для d=3. Кроме того, в этой же работе было доказано, что в графе диаметров множества в d-мерном пространстве не более одной (d+1)-клики. Дальнейшее продвижение в гипотезе Шура получили Ф. Мориц и Я. Пах. Они доказали, что если в графе диаметров на n вершинах в d-мерном пространстве любые две d-клики имеют не менее d-2 общих вершин, то число d-клик в этом графе не превосходит n. Не так давно А.Б. Купавским и А.А. Полянским была доказана гипотеза Шура в общем случае. А.А. Полянский расскажет план доказательства в случае \mathbb{R}^d, которое можно обобщить и на большие размерности.
|
|