Аннотация:
Пусть $X$ — множество с двумя расстояниями $a$ и $b$ в евклидовом пространстве, а $\Gamma(Х)$ обозначает его граф, т.е. граф вершинами которого являются точки $Х$, а рёбрами – пары точек с расстоянием $a$. В докладе будет приведена классификация всех множеств $Х$ с двумя расстояниями, у которых $\Gamma(Х)$ является полным $k$-дольным графом.
Мы разберём теорему В. Куперберга о множествах $Х$ в $n$-мерном единичном шаре с квадратом минимального расстояния между точками не меньше чем $2$. Из этой теоремы вытекает, что если такое $Х$ – множество с двумя расстояниями, то $\Gamma(Х)$ является полным $k$-дольным графом. В частности, для простых $n$ все такие $Х$ являются подмножествами вершин $n$-мерного кросс-политопа.
В заключении мы коснёмся работы Эйнхорна и Шёнберга в которой по сути устанавливается взаимно-однозначное соответствие между графами и множествами с двумя расстояниями.
|
