%\input amsppt.sty
%\documentstyle{amsppt}
%\nopagenumbers
\magnification=\magstep2
%\pagewidth{17 true cm}
%\vcorrection{-.5 true cm}
%\hcorrection{-.5 true cm}
\TagsOnRight
\pretitle{ \centerline{\bf { Научные труды ИвГУ. Математика. Вып.~2}}
\centerline{\bf {Иваново, 1999}}

\noindent --------------------------------------------------------------------------------------------------
\vskip .1cm
УДК 519.112.7+514.172.45
\vskip .2 cm
\centerline{\bf Е.~П.~Барановский}
\vskip .2 cm
%\leftheadtext{\it Е.~П.~Барановский}
%\rightheadtext{\it Строение Cut-политопов}
\topmatter
\title{\bf\noindent
К задаче о строении Cut-политопов и  Cut-конусов
}\endtitle
\abstract \nofrills
\vskip .2 cm\noindent
Предложен новый подход к описанию строения
Сut-политопов и получены некоторые новые дополнительные сведения
о  Cut-политопах $CP_{n+1}$ пpи $n\leq 5.$
\endabstract
\endtopmatter
\document
\pageno=1
\vskip .5 cm
\centerline{\bf 1. Предварительные сведения. Результаты}
\vskip 3pt
Обозначим через $K_{n+1}$ полный граф
с множеством вершин $X=\{0,1,...,n\}$, а через $E_{n+1}$
--- множество неупорядоченных пар $(k,l),$\break $ k,l=0,1,...,n;
\enskip k<l.$ Эти пары соответствуют ребрам графа и будут служить для их
обозначения.

Условимся  знаком $|Q|$ обозначать  кардинальное
число множества $Q.$

Через $R^N$ обозначим векторное (и точечное) евклидово
пространство размерности
$N={n(n+1)\over 2}$ с заданным в нем ортонормированным базисом
$$\{\bar e_{kl}\in R^N;\quad 0\leq k<l\leq n\}.$$
В этом базисе вектору (и точке)  соответствует координатная строка,
для которой будет использовано либо обозначение
$$(h_{01},h_{02},...,h_{0n},h_{12},...,h_{n-1,n}),\eqno(1)$$
либо обозначение
$$(z^1,z^2,...,z^N).\eqno(2)$$
В связи с обозначением (2) введем и соответствующие ему обозначения
векторов базиса: $\bar e_1,...,\bar e_N.$

Множеству $E\subseteq E_{n+1}$ поставим в пространстве $R^N$ в соответствие
вектор
(и точку)
$$\delta (E)=\sum_{(k,l)\in E}\bar e_{kl}.$$
Пустому множеству ставится в соответствие нулевой вектор
(и начало координат) $\delta (\emptyset)=(0,0,...,0).$

Пусть на множестве $X$ взяты подмножества $S$ и $T$. Положим:
$$D(S,T):=\{(k,l)\in E_{n+1}:k\in S, l\in T\},$$
$$D(S):=D(X,X-S).$$

{\it Cut-вектором} $\delta (S)$ множества $S\subseteq X$ называется
вектор множества $D(S)$, т.е. такой вектор, координата
$h_{kl}=\delta (S)_{kl}$ которого определяется по правилу:
$$\delta (S)_{kl}=|D(S)\cap (kl)|.$$

Таким образом, координаты Cut-вектора суть нули и единицы. Если ребра
графа $K_{n+1}$ разрезать так, чтобы вершины множества $S$
были отделены разрезом от всех других вершин графа, то 1 в
координатной строке Cut-вектора будет соответствовать разрезанному
ребру, а 0 --- целому. Следовательно, Cut-векторы суть элементы
векторного пространства размерности $N$ над двоичным полем $\{0,1\}$.
Множество их представляет собой двоичный линейный код вида
$[N,n,n].$

{\it Cut-политопом} $CP_{n+1}$ называется выпуклая оболочка множества всех
точек пространства $R^N$, радиусы-векторы которых суть
Cut-век\-то\-ры при данном $n$. (Заметим, что их всего $2^n.$)

{\it Cut-конусом,} или {\it конусом Хемминга}, $C_{n+1}$, называется
конус с вершиной в произвольной вершине Cut-политопа (обычно
берется вершина $\delta (\emptyset)=(0,...,0)$), образованный лучами,
соединяющими вершину со всеми остальными точками политопа.

Cut-конус является важным объектом теории гиперметрик
(см. работы [3, 5--10, 12--14]).
Cut-политоп введен в рассмотрение и подробно исследован
М.Деза и В.П.Гришухиным [8],[9]. В нашей статье предложен новый подход
к описанию строения Cut-политопов и
получены некоторые
дополнительные сведения о  Cut-политопах $CP_{n+1}$ при $n\leq 5$
 и, как их следствие, о
Cut-конусах соответствующих размерностей.
\vskip 3pt
\centerline{\bf 2. Строение политопов $CP_{n+1}$ при $n\leq 5$}
\vskip 2pt
Из определения
Cut-политопа непосредственно следует, что он \break одинаково расположен
относительно любой своей вершины и
что вершины его суть часть
вершин построенного на координатном репере пространства $R^N$
единичного куба $Q^N$, а сам он --- содержащийся в этом кубе выпуклый
$N$-мерный многогранник.
Следовательно, Cut-политоп является решеточным многогранником; как
показано в работе [9], он является $L$-многогранником построенной на нем
решетки.

Гиперграни Cut-конуса известны при $n\leq 6$ [5,6,12] .
Так как при $n\leq 5$ Cut-конус $C_{n+1}$ совпадает c гиперметрическим
конусом $HYP_{n+1}$ [6], то гиперграни для указанных размерностей
названы также в статье [2] как определяющие точки $L$-условий для
основного симплекса решетки.
В этом пункте мы получим описание строения Cut-политопов и
Cut-конусов при $n\leq 5$ другим способом, исходной базой которого
является следующая

\proclaim{\indent Теорема 1} Вершины  Cut-политопа $CP_{n+1}$ $(n\geq 1)$
расположены в $[{n+1\over 2}]+1$ гиперплоскостях, заданных
уравнениями
$$\sum_{i=1}^Nz^i=q(n+1-q),\enskip q=0,1,...,[{n+1\over 2}].\eqno (3)$$
Для данного $q$  количество вершин вида (1) равно $C_{n+1}^q,$ кроме
значения $q=[{n+1\over 2}]$ при $n$ нечетном, когда количество вершин
равно ${1\over 2}C_{n+1}^{n-1\over 2}.$
\endproclaim
%\vskip 3pt
\underbar{Доказательство}. Рассмотрим Cut-вектор $D(S)$, которому соответствует
множество $S$, содержащее $q$ вершин графа $K_{n+1}$. Для каждой
вершины множества $S$ из $n$ исходящих из нее ребер графа $q-1$ ребро
не разрезано, а $n-q+1$ ребро --- разрезано. Следовательно,
общее количество
разрезанных ребер множества $S$ равно $q(n+1-q)$. И именно столько единиц
 в строке координат того Cut-вектора, который соответствует
множеству. Отсюда и вытекают утверждения теоремы.

Отметим, что для Cut-вектора $\delta(i_1i_2...i_p)$ справедливо соотношение:
$$\delta(i_1i_2...i_p)=\delta(i_1)\oplus \delta(i_2)\oplus ...
\oplus \delta(i_p),$$
где через $\oplus$ обозначено сложение по mod 2. Из него видно, как
теорему 1 и ее доказательство можно формулировать на языке двоичных
линейных кодов.

Cut-векторы $\delta (i_1),\delta (i_1i_2),...,\delta (i_1i_2...i_p)$,
рассматривая их как вершины Cut-политопа,
будем называть соответственно вершинами первого, второго,\,\dots,\,p-го уровня.

Для данного $n$ расположим Cut-векторы $\delta(S)$, $|S|\leq [{n+1\over 2}]$
в порядке возрастания количества вершин в подграфах множества $S$
(т.е. в порядке возрастания уровней вершин),
а при одинаковом числе вершин --- в порядке возрастания чисел,
образованных упорядоченным списком вершин:
$$\delta(\emptyset),\delta(0),...,\delta(n),\delta(01),...,\delta(0n),
\delta(12),...,\delta(n-1,n),\delta(012),...\enskip.$$
Имея в виду такое упорядоченное расположение, припишем вершинам
Cut-политопа соответственно вторые обозначения:
$$C_0,C_1,C_2,...,C_{2^n-1}.$$

Введем обозначение:
$$\Phi(x^0,x^1,...,x^n):=-\sum_{0\leq k<l\leq n}h_{kl}x^kx^l.\eqno(4)$$
Геометрический смысл функции $\Phi$ можно найти в [2]. Здесь она
будет использована только формально ---
для записи уравнений гиперграней Cut-политопов и
Cut-конусов.

Переходим к отысканию устройства Cut-политопов, используя теорему 1.
При $n=1,N=1$ и $n=2,N=3$  результат очевиден: Cut-политоп
$CP_{1+1}$ --- отрезок, Cut-политоп $CP_{2+1}$ --- правильный тетраэдр.

Пусть $n=3,N=6.$ Согласно теореме 1 точки $C_1$ -- $C_4$ расположе-\break ны на
гиперплоскости $\sum_{i=1}^6z^i=3$, а точки $C_5$ -- $C_7$ ---  на
гиперплос-\break кости $\sum_{i=1}^6z^i=2$.
Нетрудно убедиться, что выпуклые оболочки точек
$C_1$ -- $C_4$ и точек $C_0,C_5$ -- $C_7$ представляют собой
правильные тетраэдры, расположенные в перпендикулярных 3-плоскостях,
точкой пересечения которых служит общий центр тетраэдров.
Следовательно, полиэдр $CP_{3+1}$ представляет собой известный [4]
многогранник комплекса переделивания $V^6_{33}.$ Это
бездиагональный многогранник со строкой Эйлера -- Пуанкаре (8,28,56,68,48,16),
являющийся $L$-многогранником
6-мерной решетки. Подробное описание
политопов $CP_{n+1}$, $n=1,2,3,$ и $L$-разбиений построенных на них
решеток дано в [9].

Переходим к случаю $n=4,N=10.$
Cогласно теореме 1 вершины $C_1$ -- $C_5$ полиэдра $CP_{4+1}$ расположены на
гиперплоскости $\sum z^i=4$, а вершины $C_6$ -- $C_{15}$ --- на
гиперплоскости
$\sum z^i=6$.
Легко видеть, что точки $C_6$ --- $C_{15}$ cуть вершины  правильного
9-мерного симплекса. Поскольку гиперплоскость, несущая этот симплекс,
удалена от вершины $C_0$ политопа дальше  гиперплоскостей,
несущих остальные его вершины,
 делаем вывод, что этот симплекс является
одной из гиперграней политопа $CP_{4+1}$. Ее уравнение запишем,
воспользовавшись обозначением (4): $\Phi(1,1,1,1,1)=-6.$

Так как Cut-политоп расположен одинаково относительно всех своих
вершин, то каждой из 16 вершин нашего политопа соответствует
аналогичная симплициальная грань. Уравнения соответствующих им
гиперплоскостей имеют вид $\Phi(1^4,-1^1)=-2$ или
$\Phi(1^3,-1^2)=0.$ Последние 10 уравнений соответствуют 10
гиперграням Cut-конуса $C_{4+1}$.

Отыскиваем гиперграни политопа, смежные по 8-мерным граням с
гипергранью в плоскости $\sum z^i=6.$ Эти грани имеют по 12 вершин и
расположены в гиперплоскостях вида $\Phi(1^3,0^2)=-2.$ Каждая из
гиперграней, смежная с какой-либо из
остальных симплициальных граней политопа,
или совпадает с одной из найденных, или принадлежит множеству из 30
аналогичных граней на
гиперплоскостях $\Phi(1^2,-1^1,0^2)=0.$ Убедившись, что найденное
множество гиперграней образует всю поверхность политопа $CP_{4+1},$
имеем

\proclaim{\indent Предложение 1} Поверхность
Cut-политопа $CP_{4+1}$ образована 16 симплициальными гранями,
расположенными на гиперплоскостях
$$\Phi(1^5)=-6, \ \Phi(1^4,-1^1)=-2, \ \Phi(1^3,-1^2)=0,\eqno(5)$$
и 40 двенадцативершинными гранями,
расположенными на гиперплоскостях
$$\Phi(1^3,0^2)=-2, \ \Phi(1^2,-1^1,0^2)=0.\eqno(6)$$
\endproclaim

Пусть $n=5.$ Согласно теореме 1  вершины Cut-политопа $C_1$ -- $C_6$
первого уровня, вершины $C_7$ -- $C_{21}$ второго уровня и вершины
$C_{22}$ -- $C_{35}$ третьего уровня расположены соответственно
на гиперплоскостях $\sum z^i=5, 8, 9$.
По длинам соединяющих вершины
политопа отрезков (ребер политопа) устанавливаем, что он
представляет собой выпуклую оболочку двух 15-мерных симплексов
$S_1=Conv\{C_0,C_7$ -- $C_{21}\}$ и
$S_2=Conv\{C_1$ -- $C_6,C_{22}$ -- $C_{31}\}.$

Очевидно, что 10-вершинная грань симплекса $S_2$ является и гра\-нью
самого политопа.
Дополняем эту грань до гиперграни политопа, используя в качестве
добавляемых вершин вершины симплекса $S_1$, расположенные на
гиперплоскости $\sum z^i=8.$ Устанавливаем, что существует 6 и только 6
вариантов такого дополнения, которыми оказываются 6 симплициальных
гиперграней политопа в
гиперплоскостях $\Phi(1^5,2^1)=-12.$ Каждой из этих гиперграней точка
$C_0$ служит единственной вершиной политопа, расположенной на наиболее
удаленном от гиперплоскости этой грани "слое", т.е. параллельной
для грани гиперплоскости. Снова пользуемся тем, что политоп одинаково
расположен относительно своих вершин, и находим аналогичные шестерки
гиперграней для всех вершин политопа, как это было сделано для вершины
$C_0.$ Тем самым получены 192 симплициальных граней, расположенных
на гиперплоскостях
$$\matrix{
\Phi(1^5,2^1)=-12, & \Phi(1^4,-1^1,2^1)=-6, & \Phi(1^3,-1^2,2^1)=-2,\cr
\Phi(1^5,-2^1)=-2, & \Phi(1^4,-1^1,-2^1)=0, & \Phi(1^2,-1^3,2^1)=0.
}
\eqno(7)
$$

Отыскав смежные с ними по 13-мерным  граням гиперграни и убедившись,
что поверхность политопа определена полностью, получаем

\proclaim{\indent Предложение 2.} Поверхность Cut-политопа $CP_{5+1}$
образована гипергранями
3 видов:

1) 192 симплициальными гранями, расположенными на гиперплоскостях (7);

2) 96 \ 20-вершинными гранями, по 10 вершин взяты из вершин каждого из
симплексов $S_i,i=1,2;$ уравнения содержащих их гиперплоскостей
$$\Phi(1^5,0^1)=-6, \ \Phi(1^4,-1^1,0^1)=-2, \ \Phi(1^3,-1^2,0^1)=0;\eqno(8)$$

3) 80 \ 24-вершинными гранями (12 вершин принадлежат одному из симплексов
$S_i,i=1,2,$ 12 --- другому); грани расположены на гиперплоскостях
$$\Phi(1^3,0^3)=-2,\quad \Phi(1^2,-1^1,0^3)=0.\eqno(9)$$
\endproclaim

Для геометрической характеристики гиперграней каждого из 3 типов названных
в предложении 2, мы назовем слоевое устройство политопа
относительно этих гиперграней. Первый слой --- гиперплоскость, на
которой лежит грань --- определяется некоторым уравнением
$f=f(z^i)=0,$ остальные слои, на которых расположены вершины политопа ---
уравнениями $f=Const.$

Для граней вида 1) 2-й, 3-й и 4-й, последний слой заданы
соответственно уравнениями $f=2,f=6,f=12.$  В последнем слое расположена
только одна вершина, скажем точка $\delta_1\in S_a, \enskip a\in \{1,2\}.$
На плоскости $f=6$ расположены 5 точек; выбранной нами точке будут
соответствовать 5 из 6 ближайших к ней вершин симплекса $S_b, b\in \{1,2\},
b\neq a.$  В слое $f=2$ лежат 6-я из
из этих вершин и еще 10 вершин симплекса $S_a$.

Относительно граней вида 2) вершины политопа расположены в трех слоях.
Во втором слое $f=2$ лежит 10 вершин политопа, 5 из них принадлежат
одному симплексу, 5 --- другому; их выпуклая оболочка --- 5-мерная призма,
в основании которой правильные 4-симплексы. В третьем слое $f=6$
расположены две вершины, из разных симплексов.

Относительно граней вида 3) политоп $CP_{4+1}$ двуслоен, во втором слое
$f=2$ лежат 8 вершин, взятых поровну из вершин каждого симплекса $S_a.$

\vskip .5 cm
\centerline{\bf Список использованной литеpатуpы}
\vskip .3 cm
\noindent
1. {\it Барановский Е.П.} Объемы $L$-симплексов пятимерных решеток// Мат.
\linebreak \phantom{ны}
заметки. 1973. Т.~13. $\No$~5. C.~771 -- 782.

\noindent
2. {\it Барановский Е.П.} \ Симплексы \ $L$-разбиений \ евклидовых \ про-
\linebreak \phantom{ны}
странств//Там же. 1971. Т.~10. $\No$~6. C.~659 -- 670.

\noindent
3. {\it Деза М. (Тылкин М.Е.)} О геометрии Хэмминга единичных
кубов//
\linebreak \phantom{ны}
ДАН СССР. 1960. Т.~134. С.~1037 -- 1040.

\noindent
4. {\it Рышков С.С., Барановский Е.П.} С-типы $n$-мерных решеток и пя-
\linebreak \phantom{ны}
тимерные примитивные параллелоэдры:(С приложением к теории
\linebreak \phantom{ны}
покрытий)//
Тр. МИАН СССР. 1976. Т.~137. С.~3 -- 131.

\noindent
5. {\it Assouad P.} Sur  les inegalites valides dans $L^1$// Europ.~J.
Comb. 1984.
\linebreak \phantom{ны}
Vol.~5. P.~99 -- 112.

\noindent
6. {\it Avis D., Mutt.} All facets of the six point Hamming cone//
Ibid. 1989.
\linebreak \phantom{ны}
Vol.~10. P.~309 -- 312.

\noindent
7. {\it Deza M.} Matrices \ de \ formes quadratiques \ non negatives pour des
\linebreak \phantom{ны}
arguments binares// Comp. rend. l`Acad. Sc. Paris, 1973. Vol.~277(A).
\linebreak \phantom{ны}
P.~873 -- 875.

\noindent
8. {\it Deza M., Grishukhin V.P.} Cut polytope and its lattices:
Rapport de
\linebreak \phantom{ны}
recherche LIENS-94-8/ Ecole Norm. Super. Paris, 1994.

\noindent
9. {\it Deza M., Grishukhin V.P.} Delaunay polytopes of \ cut lattices//
Lin.
\linebreak \phantom{ны}
Alg. and its  Applic. 1995. Vol.~226/228. P.~667 -- 685.

\noindent
10. {\it Deza M., Grishukhin V.P., Laurent M.} \ Hypermetrics \ in \ geometry \ of
\linebreak \phantom{ны}
numbers// DIMAS Series in Disc. Math. and Theor. Comput. Science.
\linebreak \phantom{ны}
1995. Vol.~20. P.~1 -- 109.

\noindent
11. {\it Deza M., Grishukhin V.P., Laurent M.} The \ hypermetric \ cone \ is poly-
\linebreak \phantom{ны}
hedral// Combinatorica. 1993. Vol.~13(4). P.~397 -- 411.

\noindent
12. {\it Grishukhin V.P.} All facets of \ the \ cut \ cone $C_n$ for $n=7$
are  known//
\linebreak \phantom{ны}
Europ. J. Comb. 1990. Vol.~11. P.~115 -- 117.

\noindent
13. {\it Grishukhin V.P.} Computing \ extreme rays \ of \ the \ metric cone for  seven
\linebreak \phantom{ны}
points// Ibid. 1992. Vol.~13. P.~153 -- 165.

\noindent
14. {\it Kelly J.} \ Hypermetric \ spaces// Lecture \ Notes \ in Math. 1974. Vol.~490.
\linebreak \phantom{ны}
 P.~17 -- 31.

\end
