Семинар "Дискретная и вычислительная геометрия"

14 июня (вторник), 13⁴⁵, аудитория 307 ИППИ РАН   

Олег Мусин (University of Texas at Brownsville, ИППИ РАН)

Многодольные множества с двумя расстояниями 

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

В заключении мы коснёмся работы Эйнхорна и Шёнберга в которой по сути устанавливается взаимно-однозначное соответствие между графами и множествами с двумя расстояниями.  

страница семинара 

14.06.2016 |