%VERSION REVISEE 
% revised version for SIOPT  prepared in May 2001 with SIAM Macros

\documentclass[final]{siamltex}
\usepackage{amsfonts}

\topmargin 0pt
\textheight 8in
\textwidth 5.4in
\evensidemargin 1mm

\newcommand{\oR}{{\rm\bf R}}
\newcommand{\oQ}{{\rm\bf Q}}
\newcommand{\oZ}{{\rm \bf Z}}



\bibliographystyle{plain}
\newcommand{\ds}{\displaystyle}
\newcommand{\conv}{{\rm conv}}
 \def\1set{{\rm \hbox{1\hskip-0.37em 1}}}
 \newcommand{\FRAC}{{\rm FRAC}}
 \newcommand{\STAB}{{\rm STAB}}
 \newcommand{\ODD}{{\rm ODD}}
 \newcommand{\TTH}{{\rm TH}}
\newcommand{\dd}{\delta}
\newcommand{\RR}{{\cal R}}
\newcommand{\PP}{{\cal P}}
%\newcommand{\SSS}{{\cal S}}
\newcommand{\BB}{{\cal B}}
\newcommand{\AAA}{{\cal A}}
\newcommand{\LL}{{\cal L}}
\newcommand{\GG}{{\cal G}}
\newcommand{\mr}{{\rm mr}}
\newcommand{\MR}{{\rm MR}}
%\newcommand{\rank}{{\rm rank}}
%\newcommand{\diag}{{\rm diag}}
\newcommand{\CC}{{\cal C}}
\newcommand{\EE}{{\cal E}}
\newcommand{\CCt}{\tilde {\cal C}}
\newcommand{\MM}{{\cal M}}
\newcommand{\FF}{{\cal F}}
\newcommand{\MMt}{\tilde {\cal M}}
\newcommand{\svec}{{\rm svec}}
\newcommand{\svecol}{{\rm svec}}
\newcommand{\smatol}{{\rm smat}}
\newcommand{\CUT}{{\rm CUT}}
\newcommand{\MET}{{\rm MET}}
\newcommand{\gap}{{\rm gap}}
\newcommand{\Sym}{{\cal S}}
\newcommand{\Symm}{{\cal S}^1}
\newcommand{\PSD}{{\rm PSD}}

 

 
 \begin{document}
\title{Tighter Linear and  Semidefinite Relaxations for Max-Cut Based on   the Lov\'asz-Schrijver Lift-and-Project Procedure}

 \author{Monique Laurent
\thanks{CWI, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands
 ({\tt monique@cwi.nl}).}}

\maketitle


\begin{abstract}
We study how the lift-and-project method introduced by
Lov\'asz and Schrijver \cite{LS91}
applies to the cut polytope. 
We show that the cut polytope of a graph can be found in $k$ iterations 
if there exist $k$ edges whose contraction produces a graph with no $K_5$-minor.
Therefore, 
for a graph $G$ with $n\ge 4$ nodes with stability number $\alpha(G)$, $n-4$ iterations 
suffice instead of the $m$ (number of edges) iterations required in general and,
under some assumption, 
$n-\alpha(G)-3$ iterations suffice.
The exact number of needed iterations is determined  for small $n\le 7$
by a detailed analysis of the new relaxations.
If positive semidefiniteness is added to the construction, then one finds in one
iteration
a relaxation of the cut polytope which is tighter than its basic
semidefinite relaxation and than another one introduced recently by
Anjos and Wolkowicz \cite{AW00}.
We also show how the Lov\'asz-Schrijver relaxations  for the stable set polytope of $G$ 
can be strenghtened  using the corresponding relaxations for the cut polytope
of the graph $G^\nabla$ obtained from $G$ by adding a node adjacent to
all nodes of $G$.
\end{abstract}

\begin{keywords}
linear relaxation, semidefinite relaxation,
lift and project, cut polytope, stable set polytope
 \end{keywords}

 \begin{AMS}
  05C50, 15A57, 52B12, 90C22, 90C27
   \end{AMS}

   \pagestyle{myheadings}
   \thispagestyle{plain}


\markboth{M. LAURENT}{LIFT AND PROJECT RELAXATIONS FOR MAX-CUT}



\section{Introduction}
Lov\'asz and Schrijver \cite{LS91} have introduced a 
method for constructing a higher dimensional convex set
whose projection $N(K)$ approximates the convex hull $P$ of
the $0-1$ valued points in a polytope $K$ defined by 
 a given system of linear inequalities. If the 
linear system is in $d$ variables, the convex set 
consists of symmetric matrices of order $d+1$
satisfying certain linear conditions. A fundamental 
property of the projection $N(K)$ is that one can optimize over it in polynomial time and, thus, 
find an approximate solution to the original problem in polynomial time.
Moreover, after $d$ iterations of the operator $N$, one finds
the polytope $P$.
Lov\'asz and Schrijver  \cite{LS91}
also introduce some  strengthenings of the basic construction; in particular, 
adding positive semidefinite constraints  leads to the operator $N_+$ 
and adding stronger linear conditions in the definition 
of the higher dimensional set of matrices leads 
to the operators $N'$ and $N'_+$.
They study in detail how  the method applies 
  to the stable set polytope. Starting with $K=\FRAC(G)$
(the {fractional stable set polytope} defined by nonnegativity and the edge constraints),
they show that in one iteration of the $N$ operator one obtains all
odd hole  inequalities (and no more) while, in one iteration of the $N_+$
operator, one obtains many inequalities including odd wheel, clique, odd antihole inequalities and orthogonality constraints;
therefore, the  relaxation $N_+(\FRAC(G))$
is tighter than the basic semidefinite relaxation of the stable set polytope 
by the theta body $\TTH(G)$. In 
particular, the
method permits  to solve the maximum stable set problem 
in a $t$-perfect graph or in a perfect graph in polynomial time.
They also show that the stable set polytope of $G$ is found after
at most $n-\alpha(G)-1$ iterations of the
$N$ operator (resp. $\alpha(G)$ iterations of the $N_+$ operator) 
applied to $\FRAC(G)$ if $G$ has at least one edge.

On the other hand, there exist `easy' polytopes $P$ 
(meaning that their linear description is known and one can optimize over them in polynomial time)
for which  the number of iterations of the $N$ or $N_+$ operators
needed in order to find $P$ grows linearly with the dimension of $P$. For example, 
Stephen and Tun\c{c}el \cite{ST99} show that $n$ iterations
are needed for finding the matching polytope
of $K_{2n+1}$ (starting with the polytope defined by nonnegativity and the degree constraints)
using the $N_+$ operator. Recently, Cook and 
Dash \cite{CD00} and Goemans and Tun\c{c}el \cite{GT00}
construct examples where positive semidefiniteness does not help;
namely, the same number $d$ of iterations is needed for finding
some $d$-dimensional polytope $P$ using the $N$ or the $N_+$ operator.
This is the case, for instance, for the 
polytope $P:=\{x\in \oR^d\mid \sum_{i=1}^dx_i\ge 1\}$ if we start 
from its relaxation $K:=\{x\in \oR^d\mid \sum_{i=1}^dx_i\ge {1\over 2}\}$. 

In this paper we study how the method applies to the   cut polytope
when starting with its linear relaxation by the metric polytope
$\MET(G)$ (to be defined later).
When using the operator $N_+$, one obtains in one iteration  a semidefinite relaxation
of the cut polytope which is tighter than its basic
semidefinite relaxation 
as well as than a refinement of it introduced
recently by Anjos and Wolkowicz \cite{AW00}. 
One can, in fact, refine the relaxation $N(\MET(G))$
by first applying the $N$ operator to the metric polytope
of the complete graph and then projecting on the edge set of the graph;
the relaxation denoted as $N(G)$ obtained in this way satisfies:
$\CUT(G)\subseteq N(G)\subseteq N(\MET(G))$.
We consider in this paper both constructions $N(G)$ and $N(\MET(G))$,
also for the stronger operators $N_+,N',N'_+$ and their iterates.

We show that $\CUT(G)=N^k(\MET(G))$ if there 
exist $k$ edges in $G$  whose contraction produces
a graph with no $K_5$-minor. In particular,
the cut polytope of a graph on $n$ nodes  
can be found after $n-4$  (resp. $n-5$) 
iterations of the $N$ (resp. $N'$)  operator  if $n\ge 4$ (resp. $n\ge 6$)
(while the cut polytope has dimension $m$, the number of edges of the graph).
Moreover, if $G$ has stability number $\alpha(G)$, then
$\CUT(G)=N^k(G)$ where $k:=\max(0,n-\alpha(G)-3)$; equality
$\CUT(G)=N^k(\MET(G))$ holds if there exists a maximum stable set in $G$ whose complement induces a graph with at most three connected 
components.
The upper bound $n-\alpha(G)-3$ is similar 
to the upper bound  of \cite{LS91} for the stable set polytope.
It is well known that the stable set polytope
$\STAB(G)$ can be realized as a face 
of the cut polytope $\CUT(G^\nabla)$, where $G^\nabla$ is obtained by
adding a new node to $G$ adjacent to all nodes of $G$; moreover,
an analogue relation exists between their basic linear and positive semidefinite relaxations.
We study how this fact extends to their relaxations obtained via the 
Lov\'asz-Schrijver procedure.
Namely, we show that $N^k(\MET(G^\nabla))$ (resp.
$\nu^k(\MET(G^\nabla))$) 
yields a relaxation of $\STAB(G)$ which is tighter than 
$N^{k+1}(\FRAC(G))$ (resp. $\nu^k(\FRAC(G))$ for $\nu=N_+,N',N_+'$).

Although the inclusion $N_+(\MET(G))\subseteq N(\MET(G))$ is strict
for certain graphs (e.g., for any complete graph on $n\ge 6$ nodes),
we do not know an example of a graph $G$ for which the number of iterations needed
for finding $\CUT(G)$ is smaller when using the operator $N_+$ than when 
using the operator $N$.
This contrasts with the case of the stable set polytope where, for instance,
$\STAB(K_n)$ is found in one iteration of the $N_+$ operator applied to
$\FRAC(G)$ while $n-2$ iterations 
of the $N$ operator are needed. 


\medskip
The paper is organized as follows.
We give in Section \ref{secLS} a general description of the
Lov\'asz-Schrijver (LS) procedure and 
Section \ref{secrelax} contains a presentation of the various relaxations of the cut polytope
considered in the paper. In Section \ref{secprop},
we  study the index of a graph (the smallest number 
of iterations of the LS procedure needed for finding its cut polytope);
upper bounds are proved in Sections \ref{secbound} and \ref{secboundN'},
the behaviour of the index under taking graph  minors and clique sums 
is investigated in Section \ref{secminor} and Section \ref{sectool} 
contains a number of needed technical tools.
We study in Section \ref{secvalidity} the validity of hypermetric inequalities 
for the new relaxations, which enables us to determine the 
  exact value of the index of a graph on $n\le 7$ nodes; 
some technical proofs are delayed till Section \ref{secproof}.
We finally study in Section \ref{secstable} the links between the LS relaxations
for the cut polytope and  the original LS relaxations
for the stable set polytope.

\section{The Lov\'asz-Schrijver Procedure}\label{secLS}

Let $F\subseteq \{\pm 1\}^d$, let $P:=\conv(F)$ be the 
integral polytope whose linear description one wishes to find, and let
$$K=\{x\in \oR^d\mid Ax\ge b\}$$ be a linear relaxation of
$P$ such that $K\subseteq [-1,1]^d$ and $K\cap \{\pm 1\}^d=F$
($K$ is a {\em linear programming formulation} for $P$).

Starting from $K$, the LS method constructs a hierarchy of linear 
relaxations for $P$ which in $d$ steps finds the exact description 
of $P$. The basic idea is as follows:
If we multiply an inequality $a^Tx\ge \beta$ valid for $F$ by
$1\pm x_i\ge 0$ we obtain two nonlinear inequalities which remain 
 valid for $F$.
Applying this to all the inequalities from the system $Ax\ge b$, substituting
$x_i^2$ by 1 and linearizing $x_ix_j$ by a new variable $y_{ij}$ for $i\ne j$, 
we obtain a polyhedron in the $d+1\choose 2$-space whose projection 
$N(K)$ on the 
original $d$-space contains $P$ and is contained in $K$.
The method was described in \cite{LS91} in terms of 0-1 variables, but for our application to the max-cut problem it is more
convenient to work with $\pm 1$ variables which is why we present it here in this setting.
%The above described construction is identical to the first step 
%of the method of Sherali and Adams \cite{SA90}; however the two methods differ
%in the way of iterating the basic step.

It is useful to reformulate the construction in matrix terms. 
First we introduce some notation.
As it is often more convenient to work with homogeneous systems of inequalities, i.e.,
with cones rather than polytopes, one embeds the $d$-space 
into $\oR^{d+1}$ as the hyperplane: $x_0=1$.
%The following notation will be useful:
For a polytope $P$ in $\oR^d$,
$\tilde P:=\{\lambda(1,x)\mid x\in P,\lambda \ge 0\}$ denotes the 
cone in $\oR^{d+1}$ obtained by homogenization of $P$; thus
$P=\{x\in \oR^d\mid (1,x)\in \tilde P\}$.
%and, for a cone $K$ in $\oR^{d+1}$, $\tilde K:=\{x\mid (1,x)\in K\}$ 
%is a polytope in $\oR^d$; thus,  $\tilde {\tilde P}=P$ and $\tilde {\tilde K}=K$.
Given a cone $K$, its  {\em dual cone} $K^*$  
is defined as
$$K^*=\{y\mid y^Tx\ge 0 \ \forall x\in K\}.$$
Consider the cube $Q:=[-1,1]^d$ and its homogenization
$\tilde Q=\{(x_0,x)\in \oR^{d+1}\mid -x_0\le x_i\le x_0 \ \forall i=1,\ldots,d\}$.
Thus the dual cone of $\tilde Q$ is generated 
by the $2d$ vectors $e_0\pm e_i$ ($i=1,\ldots,d$), where
$e_0,e_1,\ldots,e_d$ denote the standard unit vectors in $\oR^{d+1}$.

Given two polytopes $K_1\subseteq K_2\subseteq Q$,
let $M(K_1,K_2)$ 
 denote the set of symmetric   matrices 
$Y=(y_{ij})_{i,j=0}^d$ satisfying the following conditions (\ref{reli})-(\ref{relii}):
\begin{equation}\label{reli}
 y_{i,i}=y_{0,0} \mbox{ for } i=1,\ldots,d,
 \end{equation}
 \begin{equation}\label{relii}
 Y {\tilde K_2}^* \subseteq {\tilde K_1}
% Y(e_0\pm e_i)\in \tilde K \mbox{ for } i=1,\ldots,d
\end{equation} 
and set 
$$N(K_1,K_2):=\{x\in \oR^d\mid (1,x)=Ye_0 \ \mbox{ for some } Y\in M(K_1,K_2)\}.$$
One can easily verify that 
$$K_1\cap \{\pm 1\}^d \subseteq N(K_1,K_1)\subseteq N(K_1,K_2) \subseteq N(K_1,Q)\subseteq K_1.$$
Therefore, the choice $(K_1,K_2)=(K,K)$ 
provides the best relaxation $N(K,K)$ for $P$. However, 
it is also interesting to consider the choice $(K_1,K_2)=(K,Q)$ giving
the weaker relaxation $N(K,Q)$
as it behaves better algorithmically.
Indeed, as observed in \cite{LS91}, 
if one can solve in polynomial time the (weak) separation problem over $K$,
then the same holds for $M(K,Q)$ and thus also for its projection
$N(K,Q)$; this
property holds for $N(K,K)$ under the more restrictive assumption that an explicit linear
description is known for $K$ whose size is polynomial (details will be given
later in this section).

One can obtain tighter relaxations for $P$ by iterating the constructions
$N(K,Q)$ and $N(K,K)$. One can iterate the construction $N(K,Q)$ by the sequence
$N(K,Q)$, $N(N(K,Q),Q)$, etc. 
A first way in which the construction $N(K,K)$ can be iterated is by
considering the
 sequence $N(K,K)$, $N(N(K,K),N(K,K))$, etc. 
 A major drawback is then that, even if $K$ is given by an explicit
 linear system of polynomial length,
then it is not clear whether this holds for the next iterate 
$N(K,K)$. A more tractable way is 
 to consider the sequence
$N(K,K)$, $N(N(K,K),K)$, etc. 
For simplicity in the notation, for a polytope $H\subseteq K\subseteq Q$, 
set 
$$M(H):=M(H,Q),\ M'(H):=M(H,K),\ N(H):=N(H,Q),\ N'(H):=N(H,K).$$
The sequences $K,N(K,Q),N(N(K,Q),Q),\ldots$ 
and $K,N(K,K),N(N(K,K),K),\ldots$ can then be defined iteratively by
$$N^0(K)=(N')^0(K):=K,\  N^k(K):=N(N^{k-1}(K),Q), \ (N')^k(K):=N((N')^{k-1}(K),K)$$
for  $k\ge 1.$
Thus $x\in \nu^k(K)$ if and only if
 $(1,x)=Ye_0$ for some
 $Y\in \mu(\nu^{k-1}(K))$ where $\mu=M$ (resp. $M'$) if $\nu=N$ (resp. $N'$).

One can reinforce the operators $N$ and $N'$ by adding positive semidefiniteness constraints. 
For a polytope $H\subseteq Q$, define $M_+(H)$ (resp. $M'_+(H)$) 
as the set of {\em positive semidefinite} matrices $Y\in M(H)$ 
(resp. $Y\in M'(H)$);
the projections $N_+(H)$ and $N'_+(H)$ and their iterates 
are then defined in
the obvious way.
The following hierarchy  holds:
\begin{equation}\label{relhierarchy}
P\subseteq N'_+(K)\subseteq N'(K)\subseteq N(K)\subseteq K, \
P\subseteq N'_+(K)\subseteq N_+(K)\subseteq N(K)\subseteq K.
\end{equation}
For membership in $M(K)$,  condition (\ref{relii}) can be rewritten as
\begin{equation}\label{reliiN}
Y(e_0\pm e_i)\in \tilde K \ \mbox{ for } i=1,\ldots,d.
\end{equation}
As $Ye_0={1\over 2}(Y(e_0+e_i)+Y(e_0-e_i))$, we deduce that
\begin{equation}\label{relN}
N(K)\subseteq \conv(K\cap \{x\mid x_i=\pm 1\}) \ \mbox{ for any } i=1,\ldots,d.
\end{equation}
Using  this fact and induction,  one can prove 
that after $d$ iterations 
of the operator $N$ one finds the polytope $P$.

\begin{theorem}
\label{theoLS}
{{\rm \cite{LS91}} $N^d(K)=P$.}
\end{theorem}

\noindent
Obviously, the same holds for the operators $N_+$,  $N'$ or $N_+'$  but the
corresponding sequences  of relaxations 
may converge faster to $P$.

%            \begin{figure}[ht]
%	    \mbox{
%       {\def\epsfsize#1#2{0.4#1}\epsfbox{diagram.eps}}}
%
%\label{hierarchy}
% \end{figure}

\medskip\noindent
{\bf Comparison with other lift and project methods.}
Other lift and project methods have been proposed in the literature, in particular,
by Balas, Ceria and Cornu\'ejols \cite{BCC93}, by 
Sherali and Adams \cite{SA90} and,  recently,
by Lasserre \cite{Las00,Las01b}.
Each of these methods produces a hierarchy of linear or
semidefinite (in the case of Lasserre) relaxations:
$P\subseteq K^d\subseteq \ldots \subseteq K^1\subseteq K$ such that
$P=K^d$.
For $k\ge 1$, the $k$-th iterate $S_k(K)$ in the Sherali-Adams hierarchy 
is obtained by multiplying the system $Ax\ge b$ by each of the products 
$\prod_{i\in I}(1+x_i)\prod_{j\in J}(1-x_j)$ for $I,J\subseteq [1,d]$ disjoint 
with $|I\cup J|=k$ and, then, replacing each square $x_i^2$ by $1$, 
linearizing each product $\prod_{i\in I}x_i$ and projecting back 
on $\oR^d$; hence, the first step is identical to the first step of the Lov\'asz-Schrijver
method, i.e., $S_1(K)=N(K)$.
 It is shown in \cite{LS91} that $S_t(K)\subseteq N^k(K)$ (see \cite{La01} for a simple proof).

 The first relaxation $P_i(K)$ in the Balas-Ceria-Cornu\'ejols 
 hierarchy is obtained by multiplying $Ax\ge b$ by $1\pm x_i$ for some given $i\in [1,d]$
 (and then linearizing and projecting back on $\oR^d$); the next 
 relaxations are defined iteratively by
 $P_{i_1\ldots i_k}(K):=P_{i_k}(P_{i_1\ldots i_{k-1}}(K))$.
 It is shown in \cite{BCC93} that 
 $P_{i_1\ldots i_k}(K)=\conv(K\cap\{x\mid x_{i_1},\ldots,x_{i_k}=\pm 1\})$.
 Setting
 \begin{equation}\label{relN0}
 N_0(K):=\bigcap _{i=1}^dP_i(K)=\bigcap_{i=1}^d \conv(K\cap\{x\mid x_i=\pm 1\})
 \end{equation}
 we deduce from   (\ref{relN}) that 
 \begin{equation}\label{relNN0}
 N(K)\subseteq N_0(K)
 \end{equation}
 and, thus, $N^k(K)\subseteq N_0^k(K)=\bigcap_{i_1\ldots i_k}P_{i_1\ldots i_k}(K)$ 
 for $k\ge 1$.
 In fact, $N_0(K)$ can be seen as the `noncommutative' 
 analogue of $N(K)$ as $N_0(K)=\{x\in \oR^d\mid (1,x)=Ye_0 \ \mbox{ for some } 
 Y\in M_0(K)\}$ where 
 $M_0(K)$ is the set of matrices (not necessarily symmetric) 
 satisfying  (\ref{reli}) and (\ref{reliiN}).

Using facts about moment sequences and representations 
of positive polynomials as sums of squares, 
Lasserre \cite{Las00,Las01b} introduces a new hierarchy 
 of semidefinite relaxations $Q_k(K)$ of $P$.
 It is shown in \cite{La01} that it refines the Lov\'asz-Schrijver hierarchy; that is,
 $Q_k(K)\subseteq N^k_+(K)$ and its relation to the Sherali-Adams 
 hierarchy is explained. 
 

\medskip\noindent
{\bf Algorithmic aspects.}
Given a convex body $B\subseteq \oR^d$, the {\em separation problem}
for $B$ is the problem of deciding whether a given point $y\in \oR^d$ belongs to $B$ and, if not, of finding a hyperplane 
separating $y$ from $B$; the {\em weak separation problem}
is the analogue problem where one allows for numerical errors. An important 
application of the ellipsoid method is that, if one can solve in polynomial time the 
weak separation problem for $B$, then one can  optimize any linear objective 
function over $B$ in polynomial time (with an arbitrary precision)
and vice versa.
(One should assume some technical information over $B$, like the knowledge of a ball contained in 
$B$ and of a ball containing $B$.) See \cite{GLS88} for details.


An important property of the Lov\'asz-Schrijver construction is that,
if one can solve in polynomial time the weak 
separation problem for $K$, then the same holds for $M(K)$ and $M_+(K)$ and, thus, for their projections
$N(K)$ and $N_+(K)$. Therefore, for any fixed $k$,
one can optimize in polynomial time a linear objective function
over the relaxations $N^k(K)$ and  $N_+^k(K)$;
the same holds for the  relaxations $S_k(K)$ and $P_{i_1\ldots i_k}(K)$ of Sherali-Adams and
of Balas-Ceria-Cornu\'ejols.
For the 
operators $N'$ and $N'_+$ and for the Lasserre hierarchy, an analogue 
result holds under the more restrictive assumption that an explicit linear description 
is known for $K$ whose size is part of the input data.

\medskip\noindent
{\bf Identifying valid inequalities for $N(K)$ and $N_+(K)$.}
We mention   two results from \cite{LS91}
permitting to construct inequalities valid for 
$N(K)$ and
$N_+(K)$;
the first one follows directly from (\ref{relN}) and we prove the second one for completeness.

\begin{lemma}\label{lemvalid1}
Suppose that, for some $i=1,\ldots,d$,  the inequality $a^Tx\ge \beta $ 
is valid for $K\cap \{x\mid x_i=\pm 1\}$, then the inequality
$a^Tx\ge \beta$ is valid for $P_i(K)$ and, thus, for 
$N_0(K)$ and $N(K)$.
 \qquad \end{lemma}


\begin{lemma}\label{lemvalid2}
Suppose that $a_i\ge 0$ for $i=1,\ldots,d$ and $\beta\le 0$.
If the inequality $a^Tx\ge \beta$ is valid for $K\cap\{x\mid x_i=-1\}$
for every $i$ for which $a_i>0$, then the inequality $a^Tx\ge \beta$
is valid for $N_+(K)$.
\end{lemma}

\begin{proof}
Set $b:=(-\beta,a)\in \oR^{d+1}$; thus $b\ge 0$. Let $Y\in M_+(K)$.
We show that $b^TYe_0\ge 0$. By the assumption, we know that
$b^TY(e_0-e_i) \ge 0$ if $a_i>0$.
Multiplying both sides of the inequality by $a_i$ and summing over $i=1,\ldots,d$
yields:
$$(\sum_{i=1}^da_i)b^TYe_0 \ge b^TY(\sum_{i=1}^d a_ie_i)=b^TY(b+\beta e_0)$$
and, thus, $(\sum_{i}a_i-\beta)b^TYe_0\ge b^TYb$.
The result now follows since $b^TYb\ge 0$ (as $Y$ is positive semidefinite) and 
$\sum_ia_i-\beta>0$ (else, there is nothing to prove).
 \qquad \end{proof}

\medskip\noindent
{\bf Comparing $N_+(K)$ with the basic semidefinite relaxation 
in the equality case.}
The relaxation $N_+(K)$ is often stronger than some basic semidefinite relaxation 
one can think of for the problem at hand; this is the case for the stable set problem and for max-cut (see later)
and, as we see now, when $K$ is defined by an equality system.
Suppose that $K=\{x\in \oR^d\mid Ax=b\}$. The set $\hat K$ consisting 
of the  vectors
$x\in \oR^d$ for which there exists a positive semidefinite matrix 
$Y=\left(\matrix{1 & x^T\cr x & X}\right)$ satisfying $X_{ii}=1$ ($i=1,\ldots,d$)
and ${\rm Tr}(A^TAX)=b^Tb$, is a natural semidefinite 
relaxation for $P$ which is contained in $K$.
(This relaxation can be obtained
 by taking the dual of the Lagrange dual of the formulation:
$Ax=b$, $x_i^2=1$ ($i=1,\ldots,d$),
and $(Ax-b)^T(Ax-b)=0$; cf. \cite{PRW95},\cite{LO99}).

\begin{proposition}
$N_+(K)\subseteq \hat K.$
\end{proposition}

\begin{proof}
Let $x\in N_+(K)$ and $Y\in M_+(K)$ such that $(1,x)=Ye_0$.
Then, $Y(e_0\pm e_i)\in {\widetilde K}$ which means
that $Ax=b$ and $AXe_i=bx_i$ ($i=1,\ldots,d$) (setting $X:=(Y_{i,j})_{i,j=1}^d$).
Since $b=Ax=\sum_{i=1}^d (Ae_i)x_i$, then
${\rm Tr}(A^TAX)-b^Tb = \ds\sum_{i=1}^d (Ae_i)^TAXe_i -\ds \sum_{i=1}^d(Ae_i)^Tbx_i 
= \ds\sum_{i=1}^d (Ae_i)^T(AXe_i-bx_i) =0$, implying 
 $x\in \hat K$.
  \qquad \end{proof}


\section{The Cut Polytope and Some Relaxations}\label{secrelax}

\subsection{The cut polytope and the metric polytope}

Given an integer $n\ge 3$, set 
$V_n:=\{1,\ldots,n\}$,
$E_n:=\{ij\mid 1\le i<j\in V_n\}$, and 
$d_n:=|E_n|= {n\choose 2}$.
Let $\Sym_n$ denote the set of $n\times n$ symmetric matrices.
For $X\in \Sym_n$, $X\succeq 0$ means that $X$ is positive semidefinite
(abbreviated as {\em sdp}).
Set
$$\Symm_n:=\{X\in \Sym_n\mid x_{ii}=1 \ \forall i\in V_n\}, \
\EE_n:=\{X\in \Symm_n\mid X\succeq 0\}.$$
Given a vector $x\in \oR^{E_n}$, let $\smatol(x)$ denote the 
matrix $X\in \Symm_n$ whose off-diagonal entries are given by $x$; conversely,
given  a symmetric matrix $X=(x_{ij})_{i,j=1}^n$, 
$\svecol(X):=(x_{ij})_{1\le i<j\le n}$
denotes the vector consisting of the upper
triangular  entries of $X$.
Hence, $\smatol$ and $\svecol$ are inverse   bijections between the sets 
$\oR^{E_n}$ and $\Symm_n$. 

Given $x\in \{\pm 1\}^n$, $xx^T$ is called a {\em cut matrix} and 
$\svecol (xx^T)\in \oR^{E_n}$ is the associated {\em cut vector}
of the complete graph $K_n=(V_n,E_n)$. Thus, $\svecol(xx^T)$ is the
$(\pm 1)$-incidence vector
of the {\em cut} $\delta(S):=\{ij\in E_n\mid |S\cap \{i,j\}|=1\}$ where 
$S:=\{i\mid x_i=1\}$.

Let $G=(V_n,E)$ be a graph  where $E\subseteq E_n$.
The cut polytope $\CUT(K_n)$ of the complete graph 
$K_n$  is defined as the convex hull of the cut vectors
$\svecol(xx^T)$ for $x\in \{\pm 1\}^n$ and the cut polytope
$\CUT(G)$ of $G$ is then defined as the 
projection of $\CUT(K_n)$ on the subspace $\oR^E$ indexed by the edge set of $G$.
As linear programming formulation for $\CUT(G)$ we consider the 
{\em metric polytope} $\MET(G)$ defined by the conditions
$x\in [-1,1]^E$ and the {\em circuit inequalities}:
\begin{equation}\label{circuit}
\sum_{ij\in D}x_{ij}-\sum_{ij\in C\setminus D}x_{ij} \ge 2-|C|
\end{equation}
for all circuits $C$ of $G$ and all subsets $D\subseteq C$ with 
$|D|$ odd.
It is known that $\CUT(G)=\MET(G)$ if and only if $G$ has no $K_5$-minor
\cite{BM86}.
In the linear description of $\MET(G)$, it
 suffices   to consider the circuit inequalities for {\em chordless}
circuits \cite{BM86}. Therefore, $\MET(K_n)$ is defined by the $4{n\choose 3}$
{\em triangle inequalities}:
\begin{equation} \label{relt}
\begin{array}{l} x_{ij}+x_{ik}+x_{jk}\ge -1,\
x_{ij}-x_{ik}-x_{jk}\ge -1
%-x_{ij}+x_{ik}-x_{jk}\ge -1,\ -x_{ij}-x_{ik}+x_{jk}\ge -1
\end{array} 
\end{equation}

\noindent
for all distinct $i,j,k\in V_n$.
The polytope  $\MET(G)$ coincides with the projection of $\MET(K_n)$ 
on the subspace $\oR^E$ \cite{Ba93}; therefore,
one can optimize a linear objective function  over $\MET(G)$
in polynomial time and, thus,
solve the separation problem for $\MET(G)$ in polynomial time.
For a direct proof of the latter  fact see \cite{BM86}.


\subsection{Semidefinite relaxations}

We present here a number of semidefinite relaxations for the cut polytope.

\medskip \noindent
{\bf The basic sdp relaxation.}  As every cut matrix  $xx^T$ 
($x\in \{\pm 1\}^n$) belongs to $\EE_n$, 
we have:
$$\smatol(\CUT(K_n)) \subseteq \EE_n.$$
The set $\EE_n$ is the basic semidefinite relaxation of the cut polytope
underlying the approximative algorithm for max-cut 
of Goemans and Williamson \cite{GW95}.

\medskip\noindent
{\bf The Anjos-Wolkowicz sdp relaxation.}
In what follows matrices in $\Sym_{d_n+1}$ or $\EE_{d_n+1}$ are assumed to
be indexed by the set $E_n\cup\{0\}$ and $e_0,e_{ij}$ ($ij\in E_n$) denote 
the standard unit vectors in $\oR^{d_n+1}$. 
For $x\in \{\pm 1\}^n$, let
 $y:=(1,\svecol(xx^T))$ be the associated cut vector in 
 $\widetilde \CUT(K_n)$ and set
$Y:=yy^T$.
 Then,  $\svecol(xx^T)=(Y_{0,ij})_{ij\in E_n}$.
 Moreover,
 $Y$ belongs to $\EE_{d_n+1}$ and satisfies the equations:
\begin{equation}\label{relY}
Y_{ik,jk}=Y_{0,ij} \mbox{ for all distinct } i,j,k\in V_n,
\end{equation}
\begin{equation}\label{relYY}
Y_{ij,hk}=Y_{ih,jk}=Y_{ik,jh} \mbox{ for all distinct } i,j,h,k \in V_n.
\end{equation}
Anjos and Wolkowicz \cite{AW00} used condition (\ref{relY}) for 
defining  the following
sets $\FF_n$ and $F_n$:
$$\FF_n:=\{Y\in \EE_{d_n+1}\mid Y \mbox{ satisfies } {\rm (\ref{relY})}\}, \
F_n:=\{(Y_{0,ij})_{ij\in E_n}\mid Y\in \FF_n\}.$$
The set $\FF_n$ is obviously contained in the set ${\cal G}_n$ of matrices $Y\in 
\EE_{d_n+1}$ satisfying
$$Y_{0,ij}={1\over n-2}\sum_{k\in V_n,\ k\ne i,j} Y_{ik,jk} \ (ij \in E_n);$$
the relaxation ${\cal G}_n$ is introduced in \cite{AW00} as bidual (dual of the Lagrange dual)
of some formulation of max-cut.

\begin{proposition}\label{propAW}
{\rm \cite{AW00}} 
$\CUT(K_n)\subseteq F_n \subseteq \MET(K_n)
\cap \svecol(\EE_n)$.
\end{proposition}

\begin{proof}
The inclusion $\CUT(K_n)\subseteq F_n$ has already been observed above.
The inclusion $F_n\subseteq \svecol(\EE_n)\cap \MET(K_n)$ can be verified as follows.
For $Y\in \FF_n$, set $y:=(Y_{0,ij})_{ij\in E_n}$ and
$X:=\smatol(y)$.
By the relation (\ref{relY}), the matrix $X$ coincides with 
 the principal submatrix of
$Y$ with row and column indices in the set  $\{0,12,\ldots,1n\}$.
Therefore, $X\in \EE_n$ and, thus, $y\in \svecol(\EE_n)$.
In order to show the triangle inequality $y_{12}+y_{13}+y_{23}\ge -1$,
consider the principal submatrix $Z$ of $Y$ indexed by the set $\{0,12,13,23\}$ and 
let $\sigma$ denote the sum of the entries of $Z$.
As $Z\succeq 0$, we have $\sigma\ge 0$ 
which implies that 
$y_{12}+y_{13}+y_{23}\ge -1$.
The other triangle inequalities follow by the same argument after suitably flipping signs in $Z$.
%(cf. the switching operation later in this section).
 \qquad \end{proof}

%\vspace*{-5mm}\noindent
%Therefore, $F_n$ is a relaxation of the cut polytope which is tighter than the basic psd  relaxation $\EE_n$ intersected with the metric polytope.
For $n\le 4$, equality $\MET(K_n)=\CUT(K_n)$ holds.
It is shown in \cite{AW00} that both  inclusions in  Proposition \ref{propAW}
are strict for $n\ge 5$; for instance, 
the minimum of the linear objective function
$\sum_{ij \in E_5}x_{ij}$ over $\CUT(K_5)$ is $-2$
while its minimum over $F_5$ is $ -2.5$.


\medskip\noindent
{\bf New sdp relaxations based on the LS procedure.}
If we apply the Lov\'asz-Schrijver  construction to the cut
 polytope $\CUT(G)$ starting with its linear relaxation by the metric polytope $\MET(G)$, we obtain the 
relaxations $N(\MET(G))$, $N_+(\MET(G))$,
$ N'(\MET(G))$ and $N'_+(\MET(G))$ satisfying the hierarchy
(\ref{relhierarchy}).
% $$\CUT(G)\subseteq N'_+(\MET(G))\subseteq N_+(\MET(G))\subseteq N(\MET(G))\subseteq \MET(G), $$

As $G=(V_n,E)$ is a subgraph of the complete graph $K_n=(V_n,E_n)$, we have that 
$\CUT(G)=\pi_E(\CUT(K_n))$ and
$\MET(G)=\pi_E(\MET(K_n))$, where 
 $\pi_E:\oR^{E_n}\longrightarrow \oR^E$ denotes the projection
onto the subspace indexed by the
edge set of $G$.
Let $\nu$ stand for one of the operators $N,$ $N_+$, $N'$ or $N'_+$ 
and let $\mu$ denote the corresponding operator $M$, $M_+$, $M'$, $M'_+$
(i.e., $\mu=M$ if $\nu=N$, etc.).
Taking projections at both sides of the inclusion $\CUT(K_n)\subseteq
\nu(\MET(K_n))$, we obtain:
$$\CUT(G)\subseteq \pi_E(\nu(\MET(K_n))).$$

%\vspace*{-3mm}
\begin{lemma}\label{leminclusion}
$\pi_E(\nu(\MET(K_n))) \subseteq \nu(\MET(G)).$
\end{lemma}

\begin{proof}
Let $y\in \pi_E(\nu(\MET(K_n)))$. Then,
$(1,y)=\pi_E(Ye_0)$ where $Y\in \mu(\MET(K_n))$. Let $X$ denote the 
principal submatrix of $Y$ indexed by the set $\{0\}\cup E$.
Then, $X\in \mu(\MET(G))$ (this follows from the fact that
each column of $X$ is the projection on $\oR^{\{0\}\cup E}$ of the corresponding
column of $Y$ and $\MET(G)=\pi_E(\MET(K_n))$).
Therefore, $y=((Xe_0)_f)_{f\in E}$ belongs to $\nu(\MET(G))$.
 \qquad\end{proof}

Equality holds obviously in the inclusion of Lemma \ref{leminclusion}
when $G=K_n$.
We do not know whether equality holds in general,
i.e., whether the two operators $\nu$ and $\pi_E$ commute.
Note that not every matrix 
$Y\in M(\MET(G))$ can
be extended to a matrix of
$M(\MET(K_n))$; for example, the matrix
$$Y:=\bordermatrix{& 0 & 12 & 23 & 34 & 14 \cr
0 & 1 & 0 & 0 & 0 & 0 \cr
12 & 0 & 1 & 1 & 1 & 1 \cr
23 & 0 & 1 & 1 & 0 & 0\cr
34 & 0 & 1 & 0 & 1 & 0\cr
14 & 0 & 1 & 0 & 0 & 1\cr}$$ belongs to
$M(\MET(G))$ where $G$ is the circuit $(1,2,3,4)$ but 
$Y$ cannot be extended to a matrix of $M(\MET(K_4))$
(because $Y_{12,23}\ne Y_{14,34}$, cf. Proposition \ref{prop12} (i)).
For simplicity in the notation, we set
$$\nu(G):= \pi_E(\nu(\MET(G))).$$
Iterates are defined in the obvious manner:
$\nu^k(G):= \pi_E(\nu^k(\MET(K_n)))$.  The inclusion from Lemma \ref{leminclusion}
will be extended to higher iterates in Corollary \ref{corsubgraph}.


It seems preferable to work with the relaxation
$\nu(G)$ rather than $\nu(\MET(G))$, as it provides a better
relaxation for $\CUT(G)$. Moreover, one can optimize a linear objective function
over $\nu(G)$ in polynomial time for any graph and $\nu=
N,\ldots,N'_+$. In contrast,
this is true for $\nu(\MET(G))$ for any graph $G$ if $\nu=N,N_+$ and,
if $\nu=N',N'_+$, for any graph
$G$ for which the list of circuit inequalities (\ref{circuit}) (for chordless circuits) 
has a polynomial length (thus, for instance, if $G$ is a complete
graph or more generally a chordal graph).
One more attractive feature of the relaxation $\nu(G)$ is that the class 
of graphs $G$ for which $\CUT(G)=\nu(G)$ is well behaved; e.g., it is closed under taking 
deletion minors 
while it is not clear whether this property holds 
for the relaxation
$\nu(\MET(G))$ (cf. Section \ref{secminor}).
On the other hand, it will be convenient to work with the relaxation $\nu(\MET(G))$ in order to establish 
results about valid inequalities (cf. Section \ref{sectool}).


\medskip\noindent
{\bf Permutation and switching.} 
Every permutation $\sigma $   acts 
 in a natural way on an  $n\times n$ 
symmetric matrix $X$ 
and on a vector $x\in \oR^{E_n}$, producing 
the vector
$x^\sigma:=(x_{\sigma(i)\sigma(j)})_{ij\in E_n}$.
As $\sigma$ induces a permutation of $E_n$, it also
acts on a matrix $Y\in \Sym_{d_n+1}$ producing  the matrix
$Y^\sigma \in \Sym_{d_n+1}$ defined by
\begin{equation}\label{perm}
Y^\sigma_{0,ij}:= Y_{0,\sigma(i)\sigma(j)},\ 
Y^\sigma_{ij,rs}:=Y_{\sigma(i)\sigma(j), \sigma(r)\sigma(s)}\
\mbox{ for } ij,rs\in E_n.
\end{equation}
Permutation preserves the cut polytope of the complete graph $K_n$ and all its relaxations considered in the paper.
%The sets considered in the paper ($\CUT(K_n)$, $\MET(K_n)$, $F_n$, $\EE_n$, $N(K_n), \ldots,N'_+(K_n)$, etc.) are obviously invariant under permutation.

Given a subset $S\subseteq V_n$ and 
$X\in \Sym_n$, let 
$X^S$ denote the matrix  obtained from $X$ by changing  the signs of its rows and columns indexed by $S$;
in other words,  one switches the signs of the
entries of
$X$ indexed by edges in the cut $\delta(S)$.
Switching extends naturally to matrices $Y\in \Sym_{d_n+1}$ and produces
$Y^{\delta(S)}$ obtained from $Y$ by changing signs of its rows and columns
indexed by the set $\delta(S)$.
Switching also applies to vectors $x\in \oR^E$ ($E\subseteq E_n$):
simply change the signs of the entries of $x$ indexed by the set $\delta(S)\cap E$.

Clearly, $X^S\in \smatol(\CUT(K_n))$ (resp. $X^S\in \EE_n$)
 if and only if $X\in \smatol(\CUT(K_n))$
(resp. $X\in \EE_n$).
For $X,Y\in \Sym_n$, one has:
$\langle X,Y\rangle =\langle X^S,Y^S\rangle$. (Here $\langle X,Y\rangle=\sum_{i,j=1}^nx_{ij}y_{ij}$ 
denotes the usual inner product in $\Sym_n$.)
Therefore, if an inequality $\langle A,X\rangle \ge \beta$ is valid for $\smatol(\CUT(K_n))$, 
its switching $\langle A^S,X\rangle \ge \beta$ remains valid 
for $\smatol(\CUT(K_n))$. Note that the classes of triangle inequalities 
and of circuit inequalities are 
closed under switching.
Switching preserves all the  relaxations of the cut polytope  considered in the paper.

\subsection{Basic properties of the new relaxations}

The following is an easy but important property of the metric polytope
that will be repeatedly used  in the paper. 

\begin{proposition}\label{propmetprop}
If $y\in \MET(G)$ satisfies $y_{uv}=\epsilon$ for some 
edge $uv\in E$ and $\epsilon\in \{\pm 1\}$, then 
\begin{equation}\label{propmet}
y_{ui}=\epsilon y_{vi}  \ \mbox{ for every node } i \mbox{ adjacent to both } u \mbox{ and } v.
\end{equation}
\end{proposition}

%\vspace*{-8mm}
\begin{proof}
Apply  the triangle inequalities (\ref{relt})
to the triple $uvi$.
 \qquad\end{proof}

As a first application, we find that the equations (\ref{relY}) and (\ref{relYY}) are valid
for $M(\MET(G))$ and $M'(\MET(G))$, respectively.

\begin{proposition}\label{prop12}
\begin{description}
\item[(i)] If $Y\in M(\MET(G))$, then
$Y_{ik,jk}=Y_{0,ij}$ for all distinct pairwise adjacent $i,j, k\in V_n$.
\item[(ii)] 
If $Y\in M'(\MET(G))$,  then 
$Y_{ij,hk}=Y_{ih,jk}=Y_{ik,jh}$ for all distinct pairwise adjacent $i,j,h,k\in V_n$.
 \end{description}
 \end{proposition}


%\vspace*{-8mm}
\begin{proof}
(i) Let $1,2,3$ be   pairwise adjacent nodes and  
 $Y\in M(\MET(G))$.
By assumption, the vector  $y:=Y(e_0-e_{12})$
belongs to $\widetilde {\MET(G)}$.
As $y_0=-y_{12}$, we have from (\ref{propmet})  that 
$y_{13}=-y_{23}$ which implies 
$$Y_{0,13}+Y_{0,23}=Y_{12,13}+Y_{12,23}.$$
Similarly,  using the fact that $Y(e_0-e_{13}),Y(e_0-e_{23})\in \widetilde {\MET(G)}$, we obtain 
$$Y_{0,12} +Y_{0,23}=Y_{13,12}+Y_{13,23} \mbox{ and } 
Y_{0,12}+Y_{0,13}=Y_{23,12}+Y_{23,13}.$$
From this follows that
$Y_{0,12}=Y_{23,13}$, which shows (i).\\
(ii) Let $1,2,3,4$ be pairwise adjacent nodes in $G$ and $Y\in M'(\MET(G))$.
By assumption,  the vector $y:=Y(e_0+e_{12}+e_{13}+e_{23})$
belongs to $\widetilde{\MET(G)}$ and, thus, satisfies the triangle 
inequalities $-y_{12}+y_{14}-y_{24}\ge -y_0$ and
$-y_{12}-y_{14}+y_{24}\ge -y_0$.
Using the above result (i),
we find that that $y_{12}=y_0$. Now (\ref{propmet}) implies that
$y_{14}=y_{24}$ which, using again (i),
yields  $Y_{14,23}=Y_{13,24}$.
 \qquad\end{proof}


%\vspace*{-5mm}
\begin{corollary}\label{relinclusion}
$N_+(K_n)\subseteq F_n.$
 \qquad 
\end{corollary}

%\vspace*{-8mm}\noindent
We will see later that  $N_+(K_5)=\CUT(K_5)$;
therefore, 
the inclusion $N_+(K_n)\subseteq F_n$ 
is strict for $n\ge 5$.



\section{The Index of a Graph}\label{secprop}

The {\em $N$-index} $ \ \eta_N(G)$
of a graph $G$ is defined as the smallest integer $k$ for which
$\CUT(G)=N^k(\MET(G))$ and its {\em projected $N$-index}
$\eta^\pi_N(G)$ is the smallest $k$ for which $\CUT(G)=N^k(G)$;
the indexes $\eta_\nu$ and $\eta^\pi_\nu$ are defined analogously 
with respect to the other operators $\nu=N_+,\ N'$ or $N'_+$.
Obviously, $\eta^\pi_\nu(G)\le \eta_\nu(G)$.
By Theorem \ref{theoLS}, the $N$-index of $G$ is bounded by the number of edges of $G$;
in Section \ref{secbound}, we show some sharper upper bounds
which, in fact,  remain valid for the $N_0$-index since they are 
obtained using Lemma \ref{lemvalid1}. 
In particular, we show that $\eta_N(G)\le n-4$ for a graph $G$ on $n\ge 4$ nodes and
we prove in Section \ref{secboundN'} the upper bound $n-5$ for the $N'$-index of a graph on $n\ge 6$ nodes.
In Section \ref{secminor}, we study how the 
index of a graph behaves  
with respect to the graph operations of taking minors and clique 
sums.
Section \ref{sectool} contains  some technical results needed 
for establishing the upper bounds on the $N'$-index and 
for proving the minor monotonicity of the index of a graph.

\subsection{Upper bounds for the $N$-index of a graph}\label{secbound}

Let $G=(V_n,E)$ be a graph. We show here a linear upper bound in $O(n)$
for the $N$-index of $G$ (in place of the bound $|E|$).
The basic idea is to use Lemma \ref{lemvalid1} and 
to reformulate validity of an inequality 
$a^Tx\ge \beta$ for 
 $\MET(G)\cap \{x\mid x_{uv}=\epsilon\}$
in terms of validity of a transformed inequality 
for $\MET(G\slash uv)$, the metric polytope
of the contracted graph $G\slash uv$.

We need some definitions.
 For $u\in V_n$, $N_G(u)$ denotes the set of
  nodes adjacent to $u$ in $G$.
Given an edge $uv\in E$, let $H:=G\slash uv$ denote the graph obtained from $G$ by contracting 
$uv$; its node set is $V_n\setminus \{u,v\}\cup\{w\}$ where $w$ is the new
node created by contraction of edge $uv$ and denote by $F$ its 
edge set (multiple edges are erased).
Clearly $F$ is in bijection with the subset 
$\hat F:=\{\hat f\mid f\in F\}$ of $E$ where, for $f\in F$, 
\begin{equation}\label{fhat}
\begin{array}{l}
\hat f:=f \mbox{ if } w\not\in f, \ 
\hat f:=ui \mbox{ if } f=wi \mbox{ with } i\in N_G(u),\\
\hat f:=vi \mbox{ if } f=wi \mbox{ with } i\in N_G(v)\setminus N_G(u).
\end{array}
\end{equation}

Given $y\in \oR^{E}$ satisfying $y_{uv}=\epsilon \in \{\pm 1\}$ 
and (\ref{propmet}), 
its {\em $\epsilon$-restriction} $y^{F,\epsilon}\in \oR^{F}$
is defined by 
\begin{equation}\label{relyF}
\begin{array}{c}
%y^{F,\epsilon}_0:=y_0,\
y^{F,\epsilon}_f:=y_{\hat f} \mbox{ for all } f\in F 
\mbox{ except } 
  y^{F,\epsilon}_{wi}:= \epsilon y_{vi} \ \mbox{ for } i\in N_G(v)\setminus N_G(u).
   \end{array}\end{equation}
Conversely, relation (\ref{relyF}) permits to define for
any vector $x\in \oR^{F}$  its {\em $\epsilon$-extension}
$y\in \oR^{E}$ in such a way that
$y_{uv}=\epsilon$ and $y^{F,\epsilon}=x$.
Note that for $\epsilon =-1$, $y^{F,-1}$ coincides with the 
$1$-restriction of the vector $y'$ obtained from $y$ by switching the signs of its entries
indexed by edges in the cut $\delta(v)$.
Our objective is to show that membership of $y$ in
some iterate $\nu^k(\MET(G))$ is equivalent to membership
of its $\epsilon$-restriction in the corresponding iterate 
$\nu^k(\MET(G\slash uv))$ of the contracted graph ($\nu$ being any
of the operators $N,\ldots,N'_+$). We treat here the 
case  $k=0$ and  the general case will be treated in the next subsection.
It will be convenient to use the following correspondence 
between the  circuits of $G$ and those of  $H=G\slash uv$:
\begin{equation}\label{circuiti}
\begin{array}{l}
\mbox{To any circuit } C \mbox{ of } H \mbox{ corresponds the circuit }
C' \mbox{ of } G \mbox{ where } \\
C':=\hat C\cup\{uv\} 
\mbox{ if } w\in C 
\mbox{ and its neighbours } a,b  \mbox{ on } C
\mbox{ satisfy }\\  a\in N_G(u),\ b\in N_G(v)\setminus N_G(u) 
\mbox{ and } C':=\hat C \mbox{ otherwise}
\end{array}\end{equation}
(setting $\hat C:=\{\hat f\mid f\in C\}$, where $\hat f$ is defined by (\ref{fhat})).

\begin{lemma}\label{lemmabasic1}
Let $x\in \oR^F$ and $y\in \oR^E$ its $\epsilon$-extension 
where $\epsilon=\pm 1$.
Then,
\begin{description}
\item[(i)] 
 $x\in \MET(G\slash uv)$ $\Longleftrightarrow$ $y\in \MET(G)$
\item[(ii)]  $x \in \CUT(G\slash uv)$ $\Longleftrightarrow$ $y\in \CUT(G)$.
\end{description}
\end{lemma}

%\vspace*{-8mm}
\begin{proof}
(i) We let $\epsilon=1$ as the case $\epsilon=-1$ can be derived from it 
by applying switching. Obviously, $y\in [-1,1]^E$ 
if and only if $x\in [-1,1]^F$.
Suppose first that $y\in {\MET(G)}$; we show that $x\in \MET(H)$.
For this let $C$ be a circuit in $H$ and let $D\subseteq C$ be a subset of odd cardinality; we show that $x(D)-x(C\setminus D)\ge 2-|C|$.
Let $\hat D:=\{\hat f\mid f\in D\}$ and let $C'$ be the circuit
in $G$ derived from $C$ as indicated in (\ref{circuiti}).
Then, $x(D)-x(C\setminus D)=y(\hat D)-y(\hat C\setminus \hat D)$.
If $C'=\hat C$, then $y(\hat D)-y(\hat C\setminus \hat D)\ge 2-|C'|=2-|C|$;
if $C'=\hat C\cup \{uv\}$, then 
$y(\hat D)-y(\hat C\setminus \hat D) \ge 2-|C'| +y_{uv}=2-|C|$
using the assumption $y_{uv}=1$.
We omit the proof for the reverse implication which is similar.
The assertion (ii) follows from the fact that the extension/restriction operation 
maps the cut vectors of $H$ to cut vectors of $G$.
 \qquad\end{proof}


Given $a\in \oR^E$ and $\epsilon=\pm 1$, let  $a_\epsilon\in \oR^F$ be defined by
\begin{equation}\label{aeps}
\begin{array}{l}
(a_\epsilon)_{wi}:=a_{ui}  \mbox{  for } i\in N_G(u)\setminus N_G(v),\ \
(a_\epsilon)_{wi}:=\epsilon a_{vi}  \mbox{  for } i\in N_G(v)\setminus N_G(u),\\
(a_\epsilon)_{wi}:= a_{ui}+\epsilon a_{vi}  \mbox{ for }
i\in N_G(u)\cap N_G(v),\ \
(a_\epsilon)_{ij}:=a_{ij}  \mbox{ for } ij\in E$, $i,j\ne u,v.
\end{array}
\end{equation}
It follows from the definitions that
\begin{equation}\label{relaxF}
a^Ty=a_\epsilon ^T x +\epsilon a_{uv} \
\mbox{ for } x\in \oR^F \mbox{ and its  } \epsilon\mbox{-extension } y\in \oR^E.
\end{equation}

\begin{lemma}\label{lemmabasic2}
Let $a\in \oR^E$, $\epsilon\in \{\pm 1\}$,  $a_\epsilon\in \oR^F$ as in
{\rm (\ref{aeps})} and $\beta\in \oR$ be given. Then,\\
$\begin{array}{l}
a^Ty\ge \beta \mbox{ is valid for } \MET(G)\cap\{y\mid y_{uv}=\epsilon\} \Longleftrightarrow 
a_\epsilon^Tx\ge \beta-\epsilon \ a_{uv}
\mbox{ is valid for }\MET(G\slash uv),\\
a^Ty\ge \beta \mbox{ is valid for } \CUT(G)\cap\{y\mid y_{uv}=\epsilon\} \Longleftrightarrow 
a_\epsilon^Tx\ge \beta-\epsilon \ a_{uv}
\mbox{ is valid for }\CUT(G\slash uv).
\end{array}$
\end{lemma}

\begin{proof}
Apply Lemma \ref{lemmabasic1} and (\ref{relaxF}).
 \qquad\end{proof}

\begin{theorem}
\label{theoN0}
{Let $G$ be a graph and $e_1,\ldots, e_k$ be distinct edges in $G$.
Then, $$\CUT(G)=\conv(\MET(G)\cap\{x\mid x_{e_1},\ldots,x_{e_k}=\pm 1\})$$
if and only if the graph $G\slash \{e_1,\ldots,e_k\}$ has no $K_5$ minor.}
\end{theorem}

\begin{proof}
The proof is by induction on $k\ge 0$.
The result holds for $k=0$ since it is shown in \cite{BM86} that $\CUT(G)=\MET(G)$ if and only if $G$ has no $K_5$ minor. 
Let $k\ge 1$ and suppose that the result from Theorem \ref{theoN0} holds for $k-1$; we show that it also holds for $k$.
Applying the induction assumption to the graph $G\slash e_k$,
we obtain that \\
$\CUT(G\slash e_k)=\conv(\MET(G\slash e_k)\cap
\{x\mid x_{e_1},\ldots,x_{e_{k-1}}=\pm 1\})$ if and only if 
$G\slash \{e_1,\ldots,e_k\}$ has no $K_5$ minor.
Therefore, it  remains to show that  the following two statements: 
$$\begin{array}{c}
\CUT(G\slash e_k)=\conv(\MET(G\slash e_k)\cap  \{x\mid x_{e_1},\ldots,x_{e_{k-1}}=\pm 1\}),\\
\CUT(G)=\conv(\MET(G)\cap\{x\mid x_{e_1},\ldots,x_{e_k}=\pm 1\})
\end{array}$$ \\
are equivalent, which is a simple verification 
using Lemma \ref{lemmabasic1}.
 \qquad\end{proof}


%\vspace*{-5mm}
\begin{corollary}\label{corindex0}
If a graph $G$ has a set of $k$ edges whose contraction produces a graph with no $K_5$ minor,
then 
$\CUT(G)=N_0^k(G)=N^k(G)$.
In particular, $\CUT(G)=N^{n-4}(\MET(G))$ if $G$ has $n\ge 4$ nodes.
\end{corollary}

\begin{proof}
The first statement is a direct application of Theorem \ref{theoN0} and
(\ref{relN0}), (\ref{relNN0}).
We now  show that in a graph $G$ on $n$ nodes, 
there exist at most $n-4$ edges whose contraction produces a graph with no $K_5$ minor. 
If $G$ is connected, let $T$ be a spanning tree
in $G$ and let $u,v,w\in V_n$ for which 
$T':=T\backslash \{u,v,w\}$ is still a tree
(such nodes can be easily found if $T$ is a path and, otherwise, 
choose three leaves of $T$). Then the  graph obtained from $G$ by
contracting the $n-4$ edges of $T'$ has no $K_5$ minor. If $G$ is
not connected apply the same reasoning to each connected component of $G$.
 \qquad\end{proof}

Given an integer $r\ge 1$, let $\alpha_r(G)$ denote the maximum cardinality of a subset $S\subseteq V_n$
for which the induced subgraph $G[S]$ has no $K_{r+1}$ minor;  thus,
$\alpha_1(G)$ is the stability number $\alpha(G)$ of $G$,
and $\alpha_{r+1}(G)\ge \alpha_r(G)+1$ if
$\alpha_r(G)\le n-1$. As a consequence of Corollary \ref{corindex0}, 
we can show the following.

\begin{corollary}\label{corindexr}
Let $r\in \{1,2,3\}$ and $G=(V_n,E)$ be a graph on $n$ nodes.  Then,
\begin{equation}\label{alphap}
\eta^\pi_N(G)\le \max(0,n-\alpha_r(G)+r-4).
\end{equation}
If there
exists a subset $S\subseteq V_n$ for which $G[S]$ has no $K_{r+1}$
minor, $G[V_n\setminus S]$ has at most $4-r$ connected components 
and $|S|=\alpha_r(G)$, then
\begin{equation}\label{alpha}
\eta_N(G) \le \max(0,n-\alpha_r(G)+r-4).
\end{equation}
\end{corollary}

%\vspace*{-5mm}
\begin{proof}
We use the following observation:
The graph $G^*$ obtained from $G[S]$ by adding to it $4-r$
pairwise adjacent nodes that are adjacent to all nodes of $S$,
has no $K_5$ minor and, thus, the same holds for
any subgraph of $G^*$.
We first verify that (\ref{alpha}) holds. For this, suppose that 
$S\subseteq V_n$ with $|S|=\alpha_r(G)$, $G[S]$ has no $K_{r+1}$ minor and $G[V_n\setminus S]$ has at most $4-r$ connected components;
we show that a graph with no $K_5$ minor can be obtained from $G$ by contracting at most 
$k_r:= \max(0,n-\alpha_r(G)+r-4)$ edges.
Indeed, using the assumption that $G[V_n\setminus S]$ has at most
$4-r$ components, one can find at most $k_r$ edges in $G[V_n\setminus S]$
whose contraction transforms $G[V_n\setminus S]$ into a graph on at most $4-r$ nodes.
We now verify (\ref{alphap}).
If  $G[V_n\setminus S]$ has $t$ components, 
 let
$G'$ be the graph obtained from  $G$ by adding $t-1$ edges between
the components  of $G[V_n\setminus S$ so as to make $G'[V_n\setminus S]$
connected. We just saw that $\eta_N(G')\le k_r$
and, thus, 
$\CUT(G')=N^{k_r}(G')$. By projecting out the added edges, we obtain that
$\CUT(G)=N^{k_r}(G)$, that is, $\eta_N^\pi(G)\le k_r$.
 \qquad\end{proof}


In particular, the $N$-index of the graph $G^\nabla$ obtained from $G$  by adding a new node adjacent to all nodes of $G$, 
is at most $n-\alpha(G)-2$.
Some rationale for the similitude between this upper bound and the 
known upper bound $n-\alpha(G)-1$ for the $N$-index of the stable set polytope of $G$ will be given 
in Section \ref{secstable}.

Consider, for example,  the complete bipartite graph $K_{4,5}$;
then $\eta^\pi_N(K_{4,5})=1$ (by (\ref{alphap})) but the upper bound 
from (\ref{alpha})  does not apply (since 
the complement of a maximum stable set induces 
a graph with four connected components). It would be interesting to determine whether
$\eta_N(K_{4,5})=1$. If not, then $K_{4,5}$ would be 
an example of a graph  for which 
the inclusion $N(G)\subseteq N(\MET(G))$ is strict;
moreover, this would show that the $N$-index is not monotone with respect to 
deletion of edges, since the $N$-index of the graph obtained 
from $K_{4,5}$ by adding one edge is equal to 1.




As another  consequence of Corollary \ref{corindex0}, 
we have found a compact representation for the cut polytope of a graph having $k$ 
edges whose contraction produces a graph with no $K_5$ minor. Therefore,
the max-cut problem can be solved in polynomial time for such graphs 
(for fixed $k$).
This result can, however, be checked directly using a branching strategy. 
For instance, if $G\slash uv$ has no $K_5$-minor and one wishes 
to find the maximum weight $W$ of a cut in $G$ with respect to some weight function $a$,
then $W=\max(W_1,W_{-1}+a(\delta_G(v)))$ where,
for $\epsilon=\pm 1$,  $W_\epsilon$ is the maximum weight   
of a cut in $G\slash uv$  
with respect to the weight function $a_\epsilon$ (defined as in (\ref{aeps})).
(This idea is also present, e.g.,  in \cite{PR95}.)


\subsection{Validity for the new relaxations via contraction}\label{sectool}

We saw in Lemma \ref{lemmabasic2} that validity of an inequality 
$a^Tx\ge \beta$ for $\MET(G)\cap\{x\mid x_{uv}=\epsilon\}$ can be reformulated in terms of the validity of the
transformed inequality $a_\epsilon^Tx\ge \beta-\epsilon \ a_{uv}$
for $\MET(G\slash uv)$. 
We  extend here  this result for 
any iterate $\nu^k(\MET(G))$, where $\nu=N,\ldots,N'_+$ and $k\ge 1$.
For this we need to extend the notions of $\epsilon$-extension and restriction to matrices.
We begin with an application of (\ref{propmet}) to matrices in $M(\MET(G))$.

\begin{proposition}\label{prop3}
Let $Y\in M(\MET(G))$ and assume that 
$Y_{0,uv}=\epsilon Y_{0,0}$ for some edge $uv\in E$ and $\epsilon=\pm 1$.
Then, $Y$ satisfies
\begin{equation}\label{relYF}
Ye_0=\epsilon Ye_{uv}, \ Ye_{ui}=\epsilon Ye_{vi} \mbox{ for every node  } 
i \in N_G(u)\cap N_G(v);
\end{equation}
that is, $Y$ has the following  block decomposition:
\begin{equation}\label{figYF}
Y=\bordermatrix{& I & K & J \cr I & A & B^T & \epsilon A\cr
K & B &  C & \epsilon B \cr J & \epsilon A & \epsilon B^T & A\cr}
\end{equation}
setting 
 $I:=\{0\}\cup\{ui\mid i\in  N_G(u)\cap N_G(v)\}$, 
 $J:=\{uv\}\cup\{vi\mid i\in  N_G(u)\cap N_G(v)\}$  and $K:=E\setminus (I\cup J)$.
 \end{proposition}


\begin{proof}
As $y:=Y(e_0-\epsilon e_{uv})\in \widetilde{\MET(G)}$ with  $y_0=0$, we have that
$-y_0\le y_f\le y_0$ which yields $y_f=0$ for all $f\in E$ and,
thus, $Ye_0=\epsilon Ye_{uv}$. 
Let $i$ be a node adjacent to both $u$ and $v$. 
As $x:=Ye_0\in \widetilde{\MET(G)}$ with $x_0=\epsilon x_{uv}$, we have
from (\ref{propmet}) that 
$x_{ui}=\epsilon x_{vi}$, i.e., $Y_{0,ui}=\epsilon Y_{0,vi}$.
Given $f\in E$, set $z:=Y(e_0-e_f)$; then $z\in \widetilde{\MET(G)}$ and 
$z_0=\epsilon z_{uv}$ by the above. By (\ref{propmet}) this implies that 
 $z_{ui}=\epsilon z_{vi}$ and, thus, $Y_{ui,f}=\epsilon Y_{vi,f}$. This shows that
$Ye_{ui}=\epsilon Ye_{vi}$.
 \qquad\end{proof}





Let $Y$ be a symmetric matrix indexed by $\{0\}\cup E$ and satisfying 
(\ref{relYF}) for some $\epsilon=\pm 1$ and $uv\in E$; then, $Y$ has the
form (\ref{figYF}).
We define its {\em $\epsilon$-restriction} 
$Y^{F,\epsilon}$ in the following manner: 
If $\epsilon=1$,  $Y^{F,1}$ is the principal submatrix $\left(\matrix{ A & B^T\cr B & C}\right)$  of $Y$ 
indexed by the subset $\{0\}\cup \hat F=I\cup K$;
if $\epsilon=-1$, let $Y'$ be the matrix obtained 
from $Y$ by 
switching  the signs of its rows/columns indexed 
by edges in the cut $\delta(v)$, then $Y^{F,-1}$ is the principal submatrix
of $Y'$ indexed by $I\cup K$.
As $F$ is in bijection with $\hat F$ we
can view $Y^{F,\epsilon}$ as being indexed by $\{0\}\cup F$.
Conversely, one can define the {\em $\epsilon$-extension }
$Y$ of a matrix $X$ indexed by $\{0\}\cup F$ in such a way that
$Y_{0,0}=\epsilon Y_{0,uv}$ and $Y^{F,\epsilon}=X$.
Clearly,
\begin{equation}\label{sdpYF}
Y \succeq 0 \Longleftrightarrow Y^{F,\epsilon}\succeq 0.
\end{equation}
Recall that the dual cone of the cone $\widetilde{\MET(G)}$
is spanned by the vectors $e_0\pm e_f$ ($f\in E$) and
$$\xi^{C,D}:=(|C|-2)e_0+\sum_{f\in D}e_f-\sum_{f\in C\setminus D}e_f$$
for all chordless circuits $C$ of $G$ and all odd subsets $D\subseteq C$.


\begin{proposition}\label{propYF}
Let $k\ge 0$ be an integer and let  $Y$ be a symmetric matrix indexed
by $\{0\}\cup E$ satisfying {\rm (\ref{relYF})} for some
$\epsilon=\pm 1$ and $uv\in E$, and let $Y^{F,\epsilon}$ be its $\epsilon$-restriction.
Let $\nu$ be one of the operators $N,\ldots,N'_+$ and $\mu$ the corresponding operator
from $M,\ldots,M'_+$.
Then, $$Y\in \mu(\nu^k(\MET(G))) \Longleftrightarrow 
Y^{F,\epsilon}\in \mu(\nu^k (\MET(G\slash uv))).$$
 \end{proposition}


%\vspace*{-7mm}
\begin{proof}
Let $\epsilon=1$ as the case $\epsilon=-1$ can be derived from it by applying switching.
In view of relation (\ref{sdpYF}) it suffices to show the result 
for the operators $\nu=N$, $N'$.
The proof is by induction on $k\ge 0$
and   uses Lemma \ref{lemmabasic1} together with the following observation:
For $f\in F$, the $\hat f$-th 
 column of $Y$ is the $1$-extension of the corresponding $f$-th column of $Y^{F,1}$ 
while the remaining columns of $Y$ are duplicates of some of those.
We first consider the case $k=0$.
The statement for the case $\nu=N$ follows as a direct application
of the above observation.
Suppose now that $Y\in M'(\MET(G))$; we show that $Y^{F,1}\in M'(\MET(H))$.
For this let $C$ be a circuit in $H$ and let $D\subseteq C$ with an odd cardinality;
we show that $x:=Y^{F,1}\xi^{C,D}\in \widetilde{\MET(H)}$.
Set $\hat D:=\{\hat f\mid f\in D\}$ and let $C'$ be the circuit in $G$ obtained from $C$
as indicated in (\ref{circuiti}).
By assumption,
$y:=Y\xi^{C',\hat D}\in \widetilde{\MET(G)}$ and
$y_0=y_{uv}$. Thus, by Lemma \ref{lemmabasic1}, its
1-restriction $y^{F,1}$ belongs to $\widetilde{\MET(H)}$.
It suffices now to observe that $Y^{F,1}\xi^{C,D}$ coincides with $y^{F,1}$
(using the fact that $Ye_0=Ye_{uv}$ in the case when $C'=\hat C\cup\{uv\}$).
The proof for the implication $Y^{F,1}\in M(\MET(H))\Longrightarrow 
Y\in M(\MET(G))$ is analogue and thus omitted.


Let $k\ge 1$ and suppose that the result from Proposition \ref{propYF}
holds for $k-1$; we show that it holds for $k$.
We treat only the case when $\nu=N$ as  the proof is  analogue for $N'$.
Suppose first that $Y\in  M(N^k(\MET(G)))$; we show that $Y^{F,1}\in 
M(N^k(\MET(H)))$. For this, let
$f\in F$, $\epsilon'=\pm 1$, and $x:=Y^{F,1}(e_0+\epsilon' e_f)$; we show that
$x\in \widetilde {N^k(\MET(H))}$. By assumption, the vector
$y:=Y(e_0+\epsilon'e_{\hat f})$ belongs to $\widetilde{ N^k(\MET(G))}$ and satisfies
$y_0= y_{uv}$. Hence there exists a matrix $A\in M(N^{k-1}(\MET(G)))$
such that $y=Ae_0$. As $A_{0,0}= A_{0,uv}$, $A$ satisfies 
(\ref{relYF}) by Proposition \ref{prop3} and 
we deduce from the induction assumption
 that $A^{F,1}\in M(N^{k-1}(\MET(H)))$.
Thus $y^{F,1}=A^{F,1}e_0$ belongs to $\widetilde {N^k(\MET(H))}$.
The result now follows since $x=y^{F,1}$.
We omit the details of the proof for the converse implication:
$Y^{F,1}\in  M(N^k(\MET(H))) \Longrightarrow Y\in  M(N^k(\MET(G)))$.
 \qquad\end{proof}

%\vspace*{-5mm}
\begin{corollary}\label{corYF}
Let $k\ge 0$ be an integer, let
$y\in \oR^{\{0\}\cup E}$ satisfying $y_{uv}=\epsilon y_0$  and
{\rm (\ref{propmet})} for some $\epsilon=\pm 1$ and $uv\in E$ and let $y^{F,\epsilon}\in \oR^{\{0\}\cup F}$
be its $\epsilon$-restriction defined by {\rm (\ref{relyF})}. 
Let $\nu$ be one of the operators $N,\ldots,N'_+$.
Then,
$$y\in \widetilde{\nu^k(\MET(G))}
\Longleftrightarrow y^{F,\epsilon}\in \widetilde {\nu^k(\MET(G\slash uv))}.$$
\end{corollary}

%\vspace*{-7mm}
\begin{proof}
For $k=0$ the result holds by Lemma \ref{lemmabasic1} and for $k\ge 1$ it
follows from Proposition \ref{propYF}.
 \qquad\end{proof}


\noindent
Relation (\ref{relaxF})  together with Corollary \ref{corYF} imply:

\begin{proposition}\label{propvalid}
Let $k\ge 0$ be an integer, $\epsilon=\pm 1$, $uv\in E$, $a\in \oR^E$, $\beta\in \oR$
and $\nu$ one of  $N,\ldots,N'_+$.
The inequality $a^Tx\ge \beta$ is valid for $\nu^k(\MET(G))\cap\{x\mid x_{uv}=\epsilon\}$ if and only if
the inequality $a_\epsilon ^Tx\ge \beta -\epsilon a_{uv}$ is valid for
$\nu^k(\MET(G\slash uv))$.  \qquad
 \end{proposition}


%\vspace*{-5mm}
Let us say  that the inequality $a_\epsilon ^Tx\ge \beta -\epsilon a_{uv}$
is obtained from the inequality $a^Tx\ge \beta$ by {\em collapsing}
($\epsilon=1$) or 
{\em anti-collapsing}  ($\epsilon =-1$) nodes $u$ and $v$. 
Recall that anti-collapsing amounts to first switching signs of entries of
$a$ indexed by the cut $\delta(v)$ and then collapsing $u$ and $v$.
The following reformulations of Lemmas \ref{lemvalid1} and 
\ref{lemvalid2} will be used later in the paper.


\begin{proposition}\label{propvalid1}
Let $\nu=N,\ldots,N'_+$.
The inequality $a^Tx\ge \beta$ is valid for $\nu^{k+1}(\MET(G))$ 
if there is an edge $uv\in E$ for which both inequalities obtained from it  by
collapsing and anti-collapsing nodes $u$ and $v$ are 
valid for $\nu^k(\MET(G\slash uv))$.
\qquad 
 \end{proposition}


\begin{proposition}\label{propvalid2}
Suppose that $a_f\ge 0$ for all $f\in E$ and $\beta\le 0$.
The inequality $a^Tx\ge \beta$ is valid for $N_+^{k+1}(\MET(G))$ if, 
for every edge $uv\in E$ for which $a_{uv}>0$, the
inequality obtained from $a^Tx\ge \beta$ by anti-collapsing
nodes $u$ and $v$ is valid for 
\\ $N_+^k(\MET(G\slash uv)$. \qquad
\end{proposition}



%\vspace*{-5mm}
It is obvious that $\CUT(K_n)$ is equal to  the projection of $\CUT(K_{n+1})$
on the subspace $\oR^{E_n}$ indexed by the edge set of $K_n$; similarly for 
$\MET(K_n)$. The same can be verified  for $F_n$ and for any iterate 
$\nu^k(\MET(K_n))$ (in the latter case, use Corollaries \ref{corYF}
and \ref{corsubgraph}). 



\begin{proposition}\label{propsubgraph}
Let $G=(V_n,E)$ be a graph, $F\subseteq E$, and 
$H:=(V_n,F)$ the corresponding subgraph of $G$.
Let $\nu$ be one of the operators $N,\ldots,N'_+$, 
$\mu$ the associated operator from $M,\ldots,M'_+$ and let  $k\ge 0$ be an integer.
If $Y\in \mu(\nu^k(\MET(G)))$, then its principal submatrix $X$ indexed by
the set $\{0\}\cup F$ belongs to
$\mu(\nu^k(\MET(H)))$.
 \end{proposition}


\begin{proof}
It suffices to consider the case when $\nu=N,N'$ as $Y\succeq 0$ implies $X\succeq 0$.
We use the following facts in the proof:
$\MET(H)$ is the projection on $\oR^F$ of $\MET(G)$;
if  $\xi$ belongs to the dual cone of $\MET(H)$, then its extension 
$\xi':=(\xi,0,\ldots,0)\in \oR^E$ belongs to the dual of $\MET(G)$
and $X\xi $ is the projection 
on $\oR^{\{0\}\cup F}$ of $Y\xi'$.

The proof is by induction on $k\ge 0$.
The case $k=0$ is obvious in view of the above observations.
Let $k\ge 1$ and suppose that the result holds for $k-1$.
Assume that $Y\in \mu(\nu^k(\MET(G)))$; we show that
$X\in \mu(\nu^k(\MET(H)))$. For this consider $\xi\in \MET(H)^*$ and
its extension $\xi'\in \MET(G)^*$. We show that
$x:=X\xi\in {\widetilde {\nu^k(\MET(H))}}$. By assumption,
$y:=Y\xi'\in {\widetilde {\nu^k(\MET(G))}}$.
Therefore, $y=Ae_0$ for some $A\in \mu(\nu^{k-1}(\MET(G)))$.
Using the induction assumption, the principal submatrix
$B$ of $A$ indexed by $\{0\}\cup F$ belongs to
$\mu(\nu^{k-1}(\MET(H)))$ and, thus,
$Be_0\in {\widetilde {\nu^k(\MET(H))}}$. Note now that 
$x$ being the projection on $\oR^{\{0\}\cup F}$ of
$y$ is equal to $Be_0$.
This shows the result; indeed for $\nu=N$, restrict the above argument to
$\xi $ of the form $e_0\pm e_f$ ($f\in F$). 
 \qquad\end{proof}

%\vspace*{-5mm}
\begin{corollary}\label{corsubgraph}
Let $G=(V_n,E)$ be a graph, $H=(V_n,F)$ a subgraph of $G$, 
$\pi_F$ the projection from $\oR^E$ onto $\oR^F$, $k\ge 0$  an integer and $\nu=N,\ldots,N'_+$.
Then, $\pi_F(\nu^k(\MET(G)))\subseteq \nu^k(\MET(H))$. In particular, 
$\CUT(G)\subseteq \nu^k(G)\subseteq \nu^k(\MET(G))$. \qquad
\end{corollary}



%\vspace*{-1cm}
\subsection{Upper bound for the $N'$-index of a graph}\label{secboundN'}

We showed in Section \ref{secbound} the upper bound $n-4$ for the $N$-index of a graph on $n\ge 4$ nodes.
 We will see in Section \ref{secvalidity} that
 $$\eta_N(K_6)=\eta_{N_+}(K_6)=2,\ \eta_{N'}(K_6)=1,\ 
 \eta_{N'_+}(K_n)\ge 2 \ \mbox{ for } n\ge 7.$$
Thus, $\eta_{N'}(G)\le 1$ for a graph on $n\le 6$ nodes.
Based on this fact, one can 
show the slightly better upper bound $n-5$ for the $N'$-index of a graph
on $n\ge 6$ nodes.

\begin{theorem}
\label{theoindex}
Let $\nu$ be one of  $N,\ldots,N'_+$
and let $h,k\ge 0$ be integers.
If there exist $k$ edges $e_1,\ldots,e_k$ in $G$ 
for which $\CUT(G\slash \{e_1,\ldots,e_k\})=\nu^h(\MET(G\slash \{e_1,\ldots,e_k\}))$, 
then $\CUT(G)=\nu^{h+k}(\MET(G))$.  
\end{theorem}

\begin{proof}
The proof is by induction on $k\ge 0$. The result holds trivially for $k=0$.
Let $k\ge 1$ and suppose that the result holds for $k-1$.
Let $a^Tx\ge \beta$ be an inequality valid for $\CUT(G)$. 
By Lemma \ref{lemmabasic2}, the inequalities 
obtained from it by collapsing and anti-collapsing the end nodes 
of $e_k$ are valid for $\CUT(G\slash e_k)$ which is equal to 
$\nu^{h+k-1}(\MET(G\slash e_k))$ by 
the induction assumption. 
By  Proposition \ref{propvalid1}, this implies that
$a^Tx\ge \beta$ is valid for $\nu^{h+k}(\MET(G))$.
 \qquad\end{proof}




%\vspace*{-5mm}
\begin{corollary}\label{corN'}
The $N'$-index of a graph on $n\ge 6$ nodes is at 
most $n-5$.\end{corollary}

\begin{proof}
If $G$ is connected, one can find a set $F$ of  $n-6$ edges whose contraction produces
a graph on six nodes; as $\CUT(G\slash F)=N'(\MET(G\slash F))$,
we deduce from Theorem \ref{theoindex} that
$\CUT(G)=(N')^{|F|+1}(\MET(G))=(N')^{n-5}(\MET(G))$.
If $G$ is not connected, then by the above
$\CUT(G_i)=(N')^{n-5}(\MET(G_i))$ for each connected component $G_i$ of $G$;
using Proposition \ref{propcliquesum} this implies that
$\CUT(G)=(N')^{n-5}(\MET(G))$.
 \qquad\end{proof}



%\vspace*{-1cm}
\subsection{Behaviour of the index under taking  graph minors and clique sums}
\label{secminor}

An important motivation for the study of the LS relaxations is that one can 
solve the max-cut problem in polynomial time over the class of graphs 
having bounded $\nu$-index ($\nu=N,N_+$) or bounded projected 
$\nu$-index ($\nu=N,\ldots,N'_+$). It is therefore of great interest 
to understand which are the graphs having small index, e.g., $\le 1$.
This is however a difficult question.
As a first step, we study here 
whether  these graph classes are closed under taking minors and clique sums.


Let $G=(V_n,E)$ be a graph with edge set  $E\subseteq E_n$.
Given an edge $e=uv\in E$, recall that $G\backslash e$ is the graph obtained from $G$ by {\em deleting} edge $e$ and 
$G\slash e$ is the graph obtained from $G$ by  contracting $e$;
a {\em minor} of $G$ is then a graph obtained from $G$ by a sequence of deletions and/or contractions.
Let $G_i(V_i,E_i)$ ($i=1,2$) 
be two graphs such that the set $V_1\cap V_2$ induces a clique in both $G_1$ and $G_2$.
Then, the graph $G:=(V_1\cup V_2,E_1\cup E_2)$ is called the {\em clique $t$-sum}
of $G_1$ and $G_2$, where $t:=|V_1\cap V_2|$.

\begin{proposition}\label{propminor}
For $\nu=N,\ldots,N'_+$, 
$\eta^\pi_\nu(H)\le \eta^\pi_\nu(G)$ if $H$ is a minor of $G$ and
$\eta_\nu(H)\le \eta_\nu(G)$ if $H$ is a contraction minor of $G$.
 \end{proposition}


\begin{proof}
Monotonicity of the projected index under taking deletion minors 
follows directly from the definitions.
Suppose now that $H$ is a contraction minor of $G$; say, 
 $G=(V_n,E)$, $e:=uv\in E$, 
and  $H=G\slash uv =(V_n\setminus \{u,v\}\cup\{w\},F)$.
We show that $\eta_\nu(H)\le \eta_\nu(G)$. For this, suppose that 
$\CUT(G)=\nu^k(\MET(G))$; we show that $\CUT(H)= \nu^k(\MET(H))$.
Let $x\in \widetilde {\nu^k(\MET(H))}$; 
then $x=Xe_0$ for some  $X\in \mu(\nu^{k-1}(\MET(H)))$. By Proposition \ref{propYF}, the 1-extension $Y$ of $X$ belongs to 
$\mu(\nu^{k-1}(\MET(G)))$ and $Y_{0,0}=Y_{0,uv}$. Thus, $y:=Ye_0\in
\widetilde{\nu^k(\MET(G))}=\widetilde{\CUT(G)}$.
By Lemma \ref{lemmabasic1} (ii), this implies that $x=y^{F,1}\in \widetilde{\CUT(H)}$.

We now show that $\eta_\nu^\pi(H)\le \eta_N^\pi(G)$. 
Suppose that $\CUT(G)=\nu^k(G)$; we show that $\CUT(H)=\nu^k(H)$.
For this, let $x\in \nu^k(H)$. Thus, $x=\pi_F(Xe_0)$
for some $X\in \mu(\nu^{k-1}(\MET(K_{n-1})))$ with $X_{0,0}=1$. Viewing
$K_{n-1}$ as $K_n\slash uv$, we have from Proposition \ref{propYF}
that the 1-extension $Y$ of $X$ belongs to $\mu(\nu^{k-1}(\MET(K_n)))$ and
$Y_{0,0}=Y_{0,uv}=1$.
Thus, $y:=\pi_E(Ye_0)\in \nu^k(G)=\CUT(G)$, implying 
$x=y^{F,1}\in \CUT(H)$.
 \qquad\end{proof}

%\vspace*{-5mm}
\begin{proposition}\label{propcliquesum}
Let $G$ be the clique $t$-sum of two graphs $G_1$ and $G_2$ where $t=0,1,2,3$.
Then, 
$\eta^\pi_\nu(G)\le \max(\eta^\pi_\nu(G_1),\eta^\pi_\nu(G_2))$ and
$\eta_\nu(G)\le \max(\eta_\nu(G_1),\eta_\nu(G_2))$.
 \end{proposition}


\begin{proof}
Let $G=(V_n,E)$ be the clique $t$-sum of two graphs $G_i=(V_i,E_i)$
for $i=1,2$ with $t\le 3$; thus $V_n=V_1\cup V_2$ and $E=E_1\cup E_2$.
We  use 
the following fact shown in \cite{Ba83}:
Given $y\in \oR^{E_1\cup E_2}$ and its projections $y_i:=(y(e))_{e\in E_i}$ for $i=1,2$, 
then $y\in \CUT(G)\Longleftrightarrow y_i\in \CUT(G_i)$ for $i=1,2$.
Let $k\ge 0$ be an integer.
Suppose first that $\CUT(G_i)=\nu^k(G_i)$ for $i=1,2$ and let $y\in 
\nu^k(G)$; we show that $y\in \CUT(G)$. For this it suffices to show 
that $y_i\in \nu^k(G_i)$ for $i=1,2$.
There exists $Y\in \mu(\nu^{k-1}(\MET(K_n)))$ such that $y=\pi_E(Ye_0)$.
By Proposition \ref{propsubgraph} the principal submatrix $Y_i$ of $Y$ indexed
by $\{0\}\cup F_i$ where $F_i$ is the edge set of the complete graph 
on $V_i$, belongs to $\mu(\nu^{k-1}(\MET(K_{V_i})))$.
Thus, $y_i=\pi_{E_i}(Y_ie_0)\in \nu^k(G_i)$ for $i=1,2$.

Suppose now that $\CUT(G_i)=\nu^k(\MET(G_i))$ for $i=1,2$ and let $y\in 
{\widetilde {\nu^k(\MET(G))}}$;
we show that $y_i\in {\widetilde {\nu^k(\MET(G_i))}}$.
There exists $Y\in \mu(\nu^{k-1}(\MET(G)))$ such that $y=Ye_0$. By
Proposition \ref{propsubgraph} the principal
submatrix $Y_i$ of $Y$ indexed by $\{0\}\cup E_i$ belongs to
$\mu(\nu^{k-1}(\MET(G_i)))$ and, thus, $y_i=Y_ie_0\in 
{\widetilde{\nu^k(\MET(G_i))}}$.
 \qquad\end{proof}


As the  class of graphs $G$ with $\eta^\pi_\nu(G)\le 1$ 
is closed under taking minors, we know from
the theory of Robertson and Seymour \cite{RS} that there exists a finite list 
 of 
{\em minimal forbidden minors} characterizing membership in it;
that is, $\eta^\pi_\nu(G)\le 1$ if and only if $G$ does not contain any member
of the list as a minor.
For $\nu=N,N_+$, $\eta^\pi_\nu(K_6\backslash e)=1$ while $\eta^\pi_\nu(K_6)=2$;
hence the graph  $K_6$ is a minimal forbidden minor for both properties $\eta^\pi_N(G)\le 1$ and $\eta^\pi_{N_+}(G)\le 1$.
There are necessarily other minimal forbidden minors.
Indeed, the max-cut problem  is known to be NP-hard for the class of graphs having 
no $K_6$-minor (in fact, also for the class of  apex graphs;
that is, the graphs having a node whose deletion results in a planar
graph) (cf. \cite{Ba82}).

Let $G_0$ denote the graph obtained from $K_7$ by removing a matching of size 3. We
have verified that, for a graph $G$ on 7 nodes distinct from
$G_0$, $\eta^\pi_N(G)\le 1$ 
if and only if it does not contain $K_6$ as a minor. 
It would be interesting to compute $\eta^\pi_N(G_0)$; if its value
is $\ge 2$ then $G_0$ is 
 another minimal forbidden minor.

\medskip
In view of Propositions \ref{propminor} and \ref{propcliquesum},
the property $\nu^\pi_\nu(G)\le 1$ 
is preserved under the $\Delta Y$ operation 
(which consists of replacing a triangle by a claw $K_{1,3}$). However
it is not preserved under the converse $Y\Delta$ operation.
Indeed, if $G$ is the graph obtained from $K_6$ by applying
one $\Delta Y$ transformation, then
$\eta_N(G)=\eta_N^\pi(G) =1$ (by (\ref{alpha})) 
while $\eta_N(K_6)=2$.
We have verified that all the graphs in the Petersen family 
(consisting of the graphs that can be obtained from $K_6$ by $Y\Delta$ and $\Delta Y$ transformations) except $K_6$
have projected $N$-index equal to 1.






\section{Valid Inequalities for  the New   Relaxations}\label{secvalidity}

We saw above that the $N$-index of $K_n$ is at most $n-4$, with equality 
for $n=4,5$.
We conjecture that equality holds for any $n$.
In order to show this conjecture, 
one has to find an inequality valid for $\CUT(K_n)$ which is not valid
for $N^{n-5}(K_n)$. A possible candidate is the inequality
\begin{equation}\label{ine1}
\displaystyle\sum_{1\le i<j\le n}x_{ij}\ge -\left\lfloor {n\over 2}\right\rfloor.
\end{equation}
Note that (\ref{ine1}) is not valid for $N^{n-5}(K_n)$
if and only if there exists 
$a<-{1\over n}$ ($n$ odd) or $a<-{1\over n-1}$ ($n$ even)
for which $(a,\ldots,a)\in N^{n-5}(K_n)$.
 We show in Proposition \ref{prophyp7} that 
the inequality (\ref{ine1}) is not valid for $N^{n-5}(K_n)$ if $n=7$; we conjecture that this remains true for any odd $n$.
However, for $n$ even, the inequality (\ref{ine1}) {\em is}
valid for $N^{n-5}(K_n)$.
(Indeed, for $n$ even,  the inequality (\ref{ine1}) follows by summation from the 
inequalities (\ref{ine1}) for $n-1$; as the latter inequalities  are valid
for $N^{n-5}(K_{n-1})$, we deduce that (\ref{ine1}) too is valid
for $N^{n-5}(K_n)$.)
Therefore,
for $n$ even, one should use some more complicated inequality. We show in Proposition \ref{prophyp6}  that the inequality
\begin{equation}\label{ine2}
(n-4)\displaystyle\sum_{i=2}^n x_{1i}+\displaystyle\sum_{2\le i<j\le n}x_{ij}\ge
-{1\over 2}(n^2-7n+14)
\end{equation}
is not valid for $N^{n-5}(K_n)$ if $n=6$ and we conjecture that this holds for any even $n\ge 6$.
The inequalities (\ref{ine1}) and (\ref{ine2}) are special instances of gap inequalities that we now introduce.










\subsection{Gap inequalities}

Given an integer vector $b=(b_1,\ldots,b_n)\in \oZ^n$, its {\em gap}
$\gamma(b)$ is defined as
$$\gamma(b):=\min_{S\subseteq V_n} |\sum_{i\in S}b_i - \sum_{i\in V_n\setminus S}b_i|$$
and the inequality
\begin{equation}\label{gapineqx}
\sum_{1\le i<j\le n}b_ib_j x_{ij} \ge {1\over 2}\left(\gamma(b)^2 -\sum_{i=1}^n b_i^2\right ).
\end{equation}
\noindent
in the variable $x\in \oR^{E_n}$ is called the {\em gap inequality}
associated to $b$.
The  analogue of (\ref{gapineqx}) in the  matrix variable
$X\in \Symm_n$ takes the simpler form:
\begin{equation}\label{gapineqX}
b^TXb\ge \gamma(b)^2.
\end{equation}
\noindent
The inequality (\ref{gapineqX}) is obviously  valid for any
cut matrix $xx^T$ ($x\in \{\pm 1\}^n$); that is,
 the inequality  (\ref{gapineqx})
is valid  for the cut polytope $\CUT(K_n)$.
The gap inequalities are introduced in \cite{LP96} as a generalization 
of negative type inequalities (case $\gamma(b)=0$, \cite{Sc37}) 
and hypermetric inequalities (case $\gamma(b)=1$, \cite{De60});
cf. \cite{DL97} for a detailed survey.

The class of gap inequalities is closed under switching;
indeed, switching the gap inequality for $b\in \oZ^n$
along the cut $\delta(S)$ amounts to flipping the
signs of the components of $b$ on $S$.
%and zero-lifting of the gap inequality for $b\in \oZ^n$ produces the gap inequality for $(b,0)$.
(Anti)-collapsing specializes to gap inequalities in the following manner.
Given $b=(b_1,b_2,\ldots,b_n)\in \oZ^n$, set
$b':=(b_1+b_2,b_3,\ldots,b_n)\in \oZ^{n-1}$ and $b'':=(b_1-b_2,b_3,\ldots,b_n)\in \oZ^{n-1}$.
As $\gamma(b'),\gamma(b'')\ge \gamma(b)$, we have that 
${1\over 2}(\gamma(b')^2-\sum_{i=2}^nb_i'^2)\ge {1\over 2}(\gamma(b)^2-\sum_{i=1}^nb_i^2) -b_1b_2$ and
${1\over 2}(\gamma(b'')^2-\sum_{i=2}^nb_i''^2)\ge {1\over 2}(\gamma(b)^2-\sum_{i=1}^nb_i^2) +b_1b_2$.
Therefore, if the gap inequality for $b'$ (resp. $b''$)
is valid for $\nu^k(K_{n-1})$, then the inequality obtained from the gap inequality for $b$ by 
collapsing (resp. anti-collapsing) nodes 1 and 2 is valid
for
$\nu^k(K_{n-1})$. This fact will be useful when applying 
Propositions \ref{propvalid1} and \ref{propvalid2} to gap inequalities.


The negative type inequalities  do not induce
facets of $\CUT(K_n)$ (since they are implied by the
hypermetric inequalities); moreover, they 
are implied by the condition: $X\succeq 0$.
In fact, no gap inequality for $b\in \oZ^n$ with gap $\gamma(b)\ge 2$ 
and inducing a facet of the cut polytope is known (cf. \cite{LP96}).
On the other hand, hypermetric inequalities include large classes of facets for the cut polytope.
This is the case, for instance, for 
 the following   vectors $b$:
$$b=(1,\ldots,1)\in \oZ^n \mbox{  for }   n \mbox{ odd},\
b=(n-4, 1,\ldots,1)\in \oZ^n \mbox{ for }  n\ge 4.$$
The hypermetric inequality for $b=(1,1,1)$ is a triangle inequality 
(occurring in case (\ref{ine1}) for $n=3$ and in case (\ref{ine2})
for $n=4$); the hypermetric inequality for $b=(1,1,1,1,1)$
is called the {\em pentagonal inequality}
(occurring in cases (\ref{ine1}) and  (\ref{ine2})
for $n=5$). Moreover, for $n\le 6$, all facets of $\CUT(K_n)$ are
induced by hypermetric inequalities.
More precisely, $\CUT(K_n)=\MET(K_n)$ for $n\le 4$;  up to switching, 
all facets of $\CUT(K_5)$ arise from the triangle inequality 
and the pentagonal inequality;
up to switching and permutation, 
all facets of $\CUT(K_6)$ arise from 
the triangle inequality, the pentagonal inequality,  and the hypermetric inequality for 
$b=(2,1,1,1,1,1)$ (case $n=6$ of (\ref{ine2})).


\subsection{Valid hypermetric inequalities for the new relaxations}\label{secvalid2}

By construction, the triangle inequalities 
are   valid for $N(K_n)$. As $\CUT(K_5)=N(K_5)$ (by Corollary \ref{corindex0}),
the pentagonal inequality (that is, the gap inequality
for $b=(1,1,1,1,1,0,\ldots,0)$) is also valid for $N(K_n)$. 
We now examine validity of the gap inequalities for $(1,\ldots,1)\in \oZ^n$ 
($n\ge 7$, odd) and 
$(n-4,1,\ldots,1)$ ($n\ge 6$).

\begin{proposition}\label{prophyp}
Let $k\ge 1$ be an integer and $n:=2k+3$.
The gap inequality for $(1,\ldots,1)\in \oZ^{n}$ is valid
for $N_+^k(K_n)$.
 \end{proposition}


\begin{proof}
We proceed by induction on $k\ge 1$.
The result holds for $k=1$.
Let $k\ge 2$ and assume that the result holds for $k-1$.
By the induction assumption,  the gap inequality for $b'':=(0,1,\ldots,1)\in \oZ^{n-1}$
is valid for $N_+^{k-1}(K_{n-1})$. Therefore, using Proposition \ref{propvalid2}, we deduce that 
the gap inequality for $b$ is valid for $N_+^k(K_n)$.
 \qquad\end{proof}

One cannot hope to improve the above result and show validity for $N^k(K_n)$ with the help of
Proposition \ref{propvalid1}; indeed, collapsing of the gap inequality for $(1,1,1,1,1,1,1)\in \oZ^7$
gives the gap inequality for $(2,1,1,1,1,1)\in \oZ^6$ which, as we see
below, 
is {\em not} valid for $N(K_6)$.
In fact, 
the gap inequality for $(1,1,1,1,1,1,1)$ is {\em not} valid 
for  $N^2(K_7)$ (cf. Proposition \ref{prophyp7}).
The proofs of Propositions \ref{prophyp6}-\ref{propcut} below being quite
technical are delayed till Section \ref{secproof}.



\begin{proposition}\label{prophyp6}
The gap inequality for $(n-4,1,\ldots,1)\in \oZ^n$
% $$(n-4) \displaystyle\sum_{j=2}^n x_{1j} +\displaystyle\sum_{2\le i<j \le  n} x_{ij}\ge -{1\over 2}(n^2-7n+14)$$
is valid for $N'(K_n)$ if $n=6,7$; it is not valid for
$N'(K_n)$ if $n\ge 8$; it is not valid for $N_+(K_n)$ if $n\ge 6$ and
it is valid for $N^{n-5}(K_n)$ for $n\ge 7$.
 \end{proposition}



%\vspace*{-5mm}
\begin{proposition}\label{prophyp7}
The hypermetric inequality 
for $(1,\ldots,1)\in \oZ^n$ ($n\ge 7$, odd) is not valid for $N'_+(K_n)$ nor for
$N^2(K_n)$.
 \end{proposition}



%\vspace*{-5mm}
\begin{proposition}\label{propcut}
$\CUT(K_n)=N(K_n)$ if $n\le 5$, 
\ $\CUT(K_6)=N'(K_6)\subset N_+(K_6)$, $N'_+(K_n)\subset N_+(K_n)\subset N(K_n)$ for
$n\ge 6$, and $\CUT(K_n) \subset N_+'(K_n)$ for $n\ge 7$.
 \end{proposition}




Let $a^Tx\ge \beta$ be an inequality valid for $\CUT(K_n)$ and let
$G$ denote its {\em support graph}, whose edges are the pairs $ij$
for which $a_{ij}\ne 0$.
Obviously, the inequality $a^Tx\ge \beta$ 
is valid for $N(\MET(G))$ if $\eta_N(G)\le 1$.
This is the case, for instance, 
for parachute inequalities
(cf. section 30.4 in \cite{DL97}) and for bicycle odd wheel 
inequalities, that is, the inequalities
$$x_{uv}+\sum_{ij\in E(C)}x_{ij} +\sum_{i\in V(C)}(x_{ui}+x_{vi})\ge 1-|C|$$
where $C$ is an odd circuit and $u,v$ two adjacent nodes that are adjacent to all nodes of $C$.


%We have examined the list of inequalities defining the facets 
%of $\CUT(K_7)$ (it can be found, e.g., in section 30.6 of
%\cite{DL97}).
%Up to switching and permutation, it consists of 11 inequalities
%containing six hypermetric inequalities for 
%$b_1:=(1,1,1,0,0,0,0),$ $b_2:=(1,1,1,1,1,0,0)$,
%$b_3:=(2,1,1,1,1,1,0)$, $b_4:=(1,1,1,1,1,1,1)$,
%$b_5:=(2,2,1,1,1,1,1)$, $b_6:=(3,1,1,1,1,1,1)$.
%The hypermetric inequalities for $b_1,b_2$ are valid for $N(K_7)$;
%those  for $b_3$ and $b_6$ are  not valid for $N(K_7)$ (by
%Proposition \ref{prophyp6}),
%those for $b_4,b_5$ are not valid for $N(K_7)$ 
%(as they are violated by $(-{1\over 5},\ldots,-{1\over 5})\in 
%N(K_7)$ as will be seen in Corollary \ref{corxabcd}).
%The inequalities numbered 7 (bicycle odd wheel), 10 and 11
%are valid for $N(K_7)$ as their support graph belongs to $\GG$,
%the inequality 9 is not valid for $N(K_7)$ (as it is violated by 
%$(-{1\over 5},\ldots,-{1\over 5})$), and we do not know 
%about the inequality numbered 8.

\section{Application to the Stable Set Polytope}\label{secstable}

We explain here how the LS relaxations $\nu(\MET(G))$ 
for the cut polytope permit to tighten the corresponding LS relaxations for the stable set polytope.
Given a graph $G=(V_n,E)$, 
its {\em fractional stable set polytope} is
$$\FRAC(G):=\{d\in \oR^{n}\mid d\ge 0,\ d_i+d_j\le 1 \ \forall ij\in E\}$$
and
its {\em stable set polytope} 
is
$$\STAB(G):=\conv(x\in \{0,1\}^n\mid x\in \FRAC(G)).$$
Lov\'asz and Schrijver \cite{LS91}  studied in detail the relaxations
$N(\FRAC(G))$ and $N_+(\FRAC(G))$. (As $\FRAC(G)$ lives in the unit cube 
$Q=[0,1]^d$, the operators $N,N_+$ are now defined 
in the context of $0,1$ variables, which means that condition (\ref{reli})
is replaced by $y_{i,i}=y_{0,i}$ for $i=1,\ldots,d$, while
condition (\ref{reliiN}) is replaced 
by $Y(e_i),Y(e_0-e_i)\in \tilde K$ ($i=1,\ldots,d$).)
In particular, they have shown the following results. The relaxation 
 $N(\FRAC(G))$ is equal to the polytope
$\ODD(G)$ defined by nonnegativity, the edge inequalities
$d_i+d_j\le 1$ ($ij\in E$) and the odd hole inequalities
$\sum_{i\in V(C)}d_i\le {|C|-1\over 2}$ ($C$ odd circuit in $G$).
Any clique inequality $\sum_{i\in V(K)}d_i\le 1$ ($K$ clique in $G$)
is valid for $N_+(\FRAC(G))$ and $N^{|K|-2}(\FRAC(G))$ but not for
$N^{|K|-3}(\FRAC(G))$; odd wheel inequalities, odd antihole inequalities, 
orthogonality constraints are valid for $N_+(\FRAC(G))$.

\medskip
Let $G^\nabla$ denote the graph obtained from $G$ by adding a new node $a$ 
(the {\em apex} node) adjacent to all nodes of $G$ and set
$$\LL_G:=\{x\in \oR^{E(G^\nabla)}\mid x_{ij}-x_{ai}-x_{aj}=-1 \ \forall ij\in E\}.$$
For $d\in \oR^{V_n}$ define $x:=\varphi(d)\in  \oR^{E(G^\nabla)}$ by
\begin{equation}\label{reldx}
x_{ai}:=1-2d_i \ (i\in V_n),\ x_{ij}:=1-2d_i-2d_j \ (ij\in E).
\end{equation}
Then $\varphi$ is a bijection between $\oR^{V_n}$ and $\oR^{E(G^\nabla)}$.
For $S\subseteq V_n$, the $(\pm 1)$-incidence vector of the cut $\delta(S)$ 
(in $G^\nabla$) lies in $\LL_G$ if and only if $S$ is a stable set in $G$.
This shows the following well-known fact (cf. e.g. \cite{Pa89}):
\begin{equation}\label{stabcut}
\varphi\left(\STAB(G)\right) = \CUT(G^\nabla) \cap \LL_G.
\end{equation}
As $\varphi(\STAB(G))$ is a face of $\CUT(G^\nabla)$,
every valid inequality for $\CUT(G^\nabla)$ gives rise to a valid inequality 
for $\STAB(G)$. For instance, if $C$ is an odd circuit in $G$, the circuit
inequality $\sum_{ij\in E(C)}x_{ij}\ge 2-|C|$ for $\CUT(G^\nabla)$ gives
rise to the odd hole inequality
$\sum_{i\in V(C)}d_i\le {|C|-1\over 2}$ for $\STAB(G)$
(as $\sum_{ij\in E(C)}x_{ij}=|C|-4\sum_{i\in V(C)}d_i$);
one can verify that the (switching of the) bicycle odd wheel inequality
$$-x_{au}+\sum_{i\in V(C)}(-x_{ai}+x_{ui})+\sum_{ij\in E(C)}x_{ij}\ge 1-|C|$$ 
for $\CUT(G^\nabla)$ gives rise to the odd wheel inequality
$\sum_{i\in V(C)}d_i+{|C|-1\over 2}d_u\le {|C|-1\over 2}$ for
$\STAB(G)$ and that 
the gap inequality for $(b_a,b_1,\ldots,b_n)=(-(n-3),1,\ldots,1)\in \oZ^{n+1}$ for $\CUT(G^\nabla)$ 
gives rise to the clique inequality $\sum_{i=1}^n d_i\le 1$. 
It is shown in \cite{LPR97} that the correspondance (\ref{stabcut}) extends at
the level of the basic linear and semidefinite relaxations; namely,
\begin{equation}\label{stabmet}
\varphi\left(\ODD(G)\right)=\MET(G^\nabla)\cap \LL_G \mbox{ and } 
\varphi\left(\TTH(G)\right)={\cal E}(G^\nabla)\cap \LL_G,
\end{equation}
where ${\cal E}(G^\nabla)$ is the projection of ${\cal E}_{n+1}$ on
$\oR^{E(G^\nabla)}$ and $\TTH(G)$ is the {\em theta body} 
defined as the set of vectors 
$x\in \oR^{V_n}$ for which $(1,x)=Xe_0$ for some 
positive semidefinite 
matrix $X=(x_{ij})_{i,j=0}^n$  satisfying
$x_{0i}=x_{ii}$ ($i=1,\ldots,n$) and $x_{ij}=0$ ($ij\in E$). 
It follows from the above that
$$\varphi\left(\STAB(G)\right)\subseteq \MET(G^\nabla)\cap \LL_G =  \varphi\left(N(\FRAC(G))\right).$$
We now examine how the correspondance between
the relaxations 
$\nu(\MET(G^\nabla))$ and $\nu(\FRAC(G))$ carries out  for $\nu=N,N_+,N',N'_+$ and their iterates.

\begin{proposition}\label{propstabmet}
Let  $k\ge 0$ be an integer. Then,
$$\varphi\left(\STAB(G)\right)\subseteq 
N^k(\MET(G^\nabla))\cap \LL_G\subseteq \varphi\left(N^{k+1}(\FRAC(G))\right)$$ and,
for $\nu=N_+,N',N'_+$,
$$\varphi\left(\STAB(G)\right)\subseteq  \nu^k(\MET(G^\nabla))\cap \LL_G\subseteq 
\varphi\left(\nu^{k}(\FRAC(G))\right).$$
 \end{proposition}


%\vspace*{-5mm}
\begin{proof}
The left inclusions follow from (\ref{stabcut}).
We show that 
$ N^k(\MET(G^\nabla))\cap \LL_G$ is contained in $ \varphi(N^{k+1}(\FRAC(G)))$
by induction on $k\ge 0$. The inclusion  holds for $k=0$.
Let $k\ge 1$ and suppose that the inclusion holds for $k-1$.
Let $x\in  N^k(\MET(G^\nabla))\cap \LL_G$; then
$(1,x)=Ye_0$ for some
$Y\in M(N^{k-1}(\MET(G^\nabla)))$. Let $Z$ denote the matrix indexed by 
$\{0\}\cup V_n$ defined by
\begin{equation}\label{relZ}
\begin{array}{l}
Z_{0,0}:=1, \ Z_{0,i}=Z_{i,i}:= {1\over 2}(1-Y_{0,ai}) \  (i\in V_n),\\
Z_{i,j}:={1\over 4}(1+Y_{ai,aj}-Y_{0,ai}-Y_{0,aj}) \ (i,j\in V_n).
\end{array}
\end{equation}
Then $\varphi^{-1}(x)=(Z_{0,i})_{i\in V_n}$. Therefore,
the result will follow
if we can show that the matrix $Z$ belongs to $M(N^k(\FRAC(G)))$, i.e., that  $Z(e_k),$
$Z(e_0-e_k)$ belong to ${\widetilde {N^k(\FRAC(G))}}$. 
By assumption, $Y(e_0\pm e_{f})\in {\widetilde {N^{k-1}(\MET(G^\nabla))}}$ 
for all $f\in E(G^\nabla)$. As
$Ye_0 \in {\widetilde {\LL_G}}$ and
$Ye_0={1\over 2}(Y(e_0+e_f)+Y(e_0-e_f))$, we deduce that 
$Y(e_0\pm e_f)\in {\widetilde {\LL_G}}$ and, thus, $Ye_f \in {\widetilde {\LL_G}}$ for all $f\in E(G^\nabla)$, which  can be rewritten as
\begin{equation}\label{LG}
1+Y_{0,ij}-Y_{0,ai}-Y_{0,aj}=0,\ Y_{0,f}+Y_{ij,f}-Y_{ai,f}-Y_{aj,f}=0 \ \mbox{ for } f\in E(G^\nabla).
\end{equation}
Using the induction assumption, we obtain that 
$\varphi^{-1}(Y(e_0\pm e_{ak}))$ ($k\in V_n)$ belongs to
$\widetilde {N^k(\FRAC(G))}$. 
(We have extended the bijection $\varphi $ as a bijection between the
homogenized spaces
$\oR^{V_n\cup\{0\}}$ and $\oR^{E(G^\nabla)\cup\{0\}}$ in the obvious way;
namely, $(x_0,x)=\varphi(d_0,d)$ if $x_0=d_0$,
$x_{ai}=d_0-2d_i$ and $x_{ij}=d_0-2d_i-2d_j$.)
In order to conclude, it suffices now to 
observe 
that $Ze_k=\varphi^{-1}({1\over 2}Y(e_0-e_{ak}))$ and
$Z(e_0-e_k)=\varphi^{-1}({1\over 2}Y(e_0+e_{ak}))$ for $k\in V_n$;
this is an easy verification using the relation (\ref{LG}).

We now show the result for the $N'$ operator.
In view of the above, it suffices to show the following result: 
If $Y\in M'((N')^{k-1}(\MET(G^\nabla)))$ satisfies $Ye_0\in 
\widetilde {\LL_G}$ and if $Z$ is the associated matrix defined by (\ref{LG}),
then $Z\in M'((N')^{k-1}(\FRAC(G)))$; that is, 
$Ze_k,$ $Z(e_0-e_h-e_k)$ belong to 
$\widetilde {(N')^{k-1}(\FRAC(G))}$ for all $k\in V_n$, all $hk\in E(G)$,
respectively.
By assumption,  the vectors $Y(e_0\pm e_f)$ ($f\in E(G^\nabla)$)
and $Y(e_0\pm e_{ai}\pm e_{aj}\pm e_{ij})$  (with an even number of minus signs)
($ij\in E(G)$) belong to $(N')^{k-1}(\MET(G^\nabla))$; as $Ye_0\in 
\widetilde {\LL_G}$, 
their images under $\varphi^{-1}$ belong to 
$(N')^{k-1}(\FRAC(G))$ (by the induction assumption) and (\ref{LG}) holds.
To conclude the proof it suffices to verify (using (\ref{LG}))
that $Z(e_0-e_h-e_k)=\varphi^{-1}\left({1\over 4}Y(e_0+e_{ah}+e_{ak}+e_{hk})\right)$ 
for $hk\in E(G)$.



The result for the $N_+$ and $N'_+$ operators follows,
using the fact that $Y\succeq 0\Longrightarrow Z\succeq 0$, which 
holds because $b^TZb=c^TYc$,
where $b\in \oR^{n+1}$ and $c:=(-(b_0+\sum_{i=0}^nb_i),b_1,\ldots,b_n)$.
 \qquad\end{proof}


It is shown in \cite{LS91} that the 
smallest integer  $k$ for which
$N^k(\FRAC(G))=\STAB(G)$ is less than or equal to $ n-\alpha(G)-1$
if $G$ has at least one edge.
On the other hand, by (\ref{alpha}), 
$\eta_N(G^\nabla) 
\le n+1-\alpha(G^\nabla)-3=n-\alpha(G)-2$ if $\alpha(G)\le n-2$.
The similitude between the two bounds reflects the fact that 
$\STAB(G)$ arises as a face of $\CUT(G^\nabla)$.
In fact the two upper bounds match,
as the discrepancy of 1 can be explained by the fact that in the case of the cut polytope we start 
with a stronger relaxation than in the case of the stable set polytope; indeed, in view of
(\ref{stabmet}), we `win' one iteration at the beginning step.

\medskip
The inclusion $N^k(\MET(G^\nabla))\cap \LL_G\subseteq \varphi\left(N^{k+1}(\FRAC(G))\right)$
holds at equality for $k=0$ for all graphs and is strict for $k\ge 1$ 
for certain graphs. Indeed, for $k\ge 1$,
$$\STAB(K_{k+4})=\varphi^{-1}\left( N^k(\MET(K_{k+4}^\nabla))\cap \LL_{K_{k+4}} \right)
\subset N^{k+1}(\FRAC(K_{k+4})).$$
To see it, note that 
the clique inequality $\sum_{i=1}^{k+4}d_i\le 1$
is not valid for $N^{k+1}(\FRAC(K_{k+4}))$ while it is
valid for $\varphi^{-1}\left(N^k(\MET(K^\nabla_{k+4}))\cap \LL_{K_{k+4}}\right)$.
The latter holds because the clique inequality $\sum_{i=1}^{k+4}d_i\le 1$ 
arises from the gap inequality for
$(-(k+1),1,\ldots,1)\in \oZ^{k+5}$ (assigning $-(k+1)$ to the apex node)
which is valid for $N^k(\MET(K_{k+5}))$
when $k\ge 2$ by Proposition \ref{prophyp6};
in the case $k=1$, while not valid for $N(\MET(K_6))$, 
the gap inequality for $(-2,1,1,1,1,1)$
is valid for $N(\MET(K_5^\nabla))\cap \LL_{K_5}$ (cf. Lemma \ref{remhyp6}).

We know that clique and odd antihole inequalities are valid for
$N_+(\MET(G^\nabla))\cap \LL_G$ (as they are valid for $N_+(\FRAC(G))$).
It would be interesting to find for them some `parent' inequality 
for $\CUT(G^\nabla)$ which would be valid for $N_+(\MET(G^\nabla))$. 



\section{Proofs of Proposition \ref{prophyp6}-\ref{propcut}}\label{secproof}

We study here in detail validity of the gap inequalities 
for $c_n:=(1,\ldots,1)\in \oZ^n$ ($n\ge 7$ odd) and
for $b_n:=(n-4,1,\ldots,1)\in \oZ^n$ ($n\ge 6$) for some relaxations
$\nu^k(K_n)$.
Set 
\begin{equation}\label{Cn}
C_n:=\min(\displaystyle\sum_{1\le i<j\le n}x_{ij}\mid x\in \nu^k(K_n)),
\end{equation}
\begin{equation}\label{Bn}
B_n:=\min((n-4)\displaystyle\sum_{i=2}^nx_{1i}+\displaystyle\sum_{2\le i<j\le n}x_{ij}\mid x\in \nu^k(K_n)).
\end{equation}
Given some scalars $a,c\in \oR$, the vector $x(a,c)\in \oR^{E_n}$ is defined by
\begin{equation}\label{xab}
x(a,c)_{1i}:=a \ \mbox{ for } i=2,\ldots,n,\ x(a,c)_{ij}:=c \mbox{ for }
2\le i<j\le n;
\end{equation}
it is said to have {\em pattern} $(a,c)$.

A first basic observation is that the minimum in the program (\ref{Cn}) 
(resp.  (\ref{Bn}))
is attained 
at a point of $\nu^k(K_n)$ having some pattern $(a,a)$
(resp. $(a,c)$). 
Indeed, let $x\in \nu^k(K_n)$ be an optimum solution to the program (\ref{Cn}) and set 
$x^*:={1\over n!}\sum_\sigma x^\sigma$ where the sum is taken over all
permutations $\sigma$ of $[1,n]$; then $x^*\in \nu^k(K_n)$ is still optimum for (\ref{Cn}) and has
pattern $(a,a)$ for some $a\in \oR$. The reasoning is similar in
the case of the program (\ref{Bn}), except 
$x^*:={1\over (n-1)!}\sum_\sigma x^\sigma$, where the sum is now 
taken over all permutations of $[1,n]$ fixing $1$; then $x^*$ has pattern $(a,c)$ for some $a,c\in \oR$.


For the proofs of Propositions \ref{prophyp6} and \ref{prophyp7} 
we need to determine the conditions  on $a,c$ permitting to express membership
of the vector $x(a,c)$ in $N(K_n)$ and $N'(K_n)$. The study of validity for $N^2(K_n)$ 
will involve checking membership in $N(K_n)$ of a 
more complicated vector
 $x(a,b,c,d):=x$ defined as follows:
\begin{equation}\label{xabcd}
\begin{array}{c}
x_{12}:=a,\ x_{1i}:= b,\ x_{2i}:=c \ \mbox{ for } i=3,\ldots,n,\
x_{ij}:=d \ \mbox{ for } 3\le i<j\le n;
\end{array}
\end{equation}
$(a,b,c,d)$ is again called the {\em pattern} of the vector $x(a,b,c,d)$.
Note that $x(a,b,c,d)=x(a,c)$ if $a=b$ and $c=d$.

The rest of the section is organized as follows.
In Section \ref{secproof1} we determine the conditions on
$a,b,c,d$  expressing membership 
in $N(K_n)$ for the vector
$x(a,b,c,d)$ or membership in $N'(K_n)$ for the vector 
$x(a,c)$.
These results are then applied in Sections \ref{secproof2}-\ref{secproof3}
for proving Propositions \ref{prophyp7}-\ref{propcut}.

\subsection{Vectors with pattern $(a,b,c,d)$}\label{secproof1}



We begin with  determining the conditions on $a,b,c,d$ expressing membership 
in $N(K_n)$ for a vector with pattern $(a,b,c,d)$.
By definition, $x:=x(a,b,c,d)\in N(K_n)$ if and only if 
$(1,x)=Ye_0$ for some matrix 
$Y\in M(\MET(K_n))$. In fact, such matrix $Y$ can be assumed to satisfy certain symmetries.
Indeed, set $Y^*:={1\over (n-2)!}\sum_\sigma Y^\sigma$, where the 
sum is taken over all permutations $\sigma$ of $[1,n]$ 
fixing $1$ and 2 (recall the definition of $Y^\sigma$ from
(\ref{perm})). Then $Y^*\in M(\MET(K_n))$ and $Y^*e_0=(1,x)$.
Moreover, the matrix $Y^*$ has the property that
the value of its $(ij,hk)$-th entry
depends only  whether the pairs $ij$ and $hk$ meet 
and whether they contain any of the points 1 and 2.
Namely, if the pairs $ij$ and $hk$ meet, then the value of $Y_{ij,hk}$ is
determined by relation (\ref{relY}) and is thus
one of $a,b,c,d$;
otherwise,
\begin{equation}\label{Yabcd}
\begin{array}{l}
Y_{12,ij}=x \mbox{ for } 3\le i<j\le n,\ Y_{1i,2j}=z \mbox{ for } 
3\le i\ne j\le n,\\
Y_{1i,hk}=y,\ Y_{2i,hk}=u\ \mbox{ for } 3\le i\le n,\ 3\le i<j\le k,\  h,k\ne i,\\
Y_{ij,hk}=v\ \mbox{ for } 3\le i<j\le n, \  3\le h<k\le n,\  \{i,j\}\cap \{h,k\}=\emptyset
\end{array}\end{equation}
for some scalars $x,y,z,u,v$; $(a,b,c,d,x,y,z,u,v)$ is then called the
{\em pattern} of $Y$.


\begin{figure}\label{figY6}
$$\bordermatrix{&0  & 12 & 13 & 14 & 15 & 16 & 23 & 24 & 25 & 26 & 34 & 35 & 36 & 45 & 46 & 56 \cr
0 & 1 & a & b & b & b & b & c & c & c & c & d & d & d & d & d & d\cr
12& a & 1 & c & c & c & c & b & b & b & b & x & x & x & x & x & x\cr
13& b & c & 1 & d & d & d & a & z & z & z & b & b & b & y & y & y \cr
14& b & c & d & 1 & d & d & z & a & z & z & b & y & y & b & b & y\cr
15& b & c & d & d & 1 & d & z & z & a & z & y & b & y & b & y & b \cr
16& b & c & d & d & d & 1 & z & z & z & a & y & y & b & y & b & b\cr
23& c & b & a & z & z & z & 1 & d & d & d & c & c & c & u & u & u \cr
24& c & b & z & a & z & z & d & 1 & d & d & c & u & u & c & c & u\cr
25& c & b & z & z & a & z & d & d & 1 & d & u & c & u & c & u & c \cr
26& c & b & z & z & z & a & d & d & d & 1 & u & u & c & u & c & c \cr
34& d & x & b & b & y & y & c & c & u & u & 1 & d & d & d & d & v\cr
35& d & x & b & b & b & y & c & u & c & u & d & 1 & d & d & v & d\cr
36& d & x & b & y & y & b & c & u & u & c & d & d & 1 & v & d & d \cr
45& d & x & y & b & b & y & u & c & c & u & d & d & v & 1 & d & d\cr
46& d & x & y & b & y & b & u & c & u & c & d & v & d & d & 1 & d\cr
56& d & x & y & y & b & b & u & u & c & c & v & d & d & d & d & 1\cr}
$$
\caption{A matrix $Y\in {\cal Y}_6$ with pattern $(a,b,c,d,x,y,z,u,v)$}
\end{figure}


Let ${\cal Y}_n$  denote the set of matrices $Y\in \Symm_{1+d_n}$
having some pattern $(a,b,c,d,x,y,z,u,v)$ as defined above.
A matrix $Y\in {\cal Y}_6$ is shown in Figure \ref{figY6}.
When $a=b$ and $c=d$ (i.e., when $x=x(a,c)$), the matrix $Y$ can be assumed to satisfy the following
additionnal
symmetry:  $x=y=z$ and $u=v$ and $(a,c,x,u)$ is then called the {\em simplified pattern} of $Y$.
 (Such a matrix is pictured in Figure \ref{figpattern}.)




We first work out  the conditions on $a,\ldots,v$ 
for  membership of $Y\in {\cal Y}_n$ in $M(\MET(K_n))$
and then deduce the conditions on $a,b,c,d$ for membership
of $x(a,b,c,d)$ in $N(K_n)$.


\begin{lemma}
\label{lemY1}
{Let $Y\in {\cal Y}_n$ with pattern $(a,b,c,d,x,y,z,u,v)$ and $n\ge 6$.
Then, $Y$ belongs to 
$ M(\MET(K_n))$ if and only if $a,\ldots,v$  satisfy 
the linear inequalities:
{\small 
\begin{equation}\label{relYT}
\begin{array}{c}
a+2b+2c+d+x \ge -1,\ a-2b-2c+d+x\ge -1,\\
-a +2b-2c+d-x\ge -1,\ -a-2b+2c+d-x\ge -1,\\
a-d-x\ge -1,\ -a-d+x\ge -1,\ a+3d+3x \ge-1,\ -a+3d-3x\ge -1,\\
a+2b+2c+d+z\ge -1,\ -a+2b-2c+d-z\ge -1,\ a-d-z\ge -1,\\
-a-d+z\ge -1,\
a-2b-2c+d+z\ge -1,\ -a-2b+2c+d-z\ge -1,\\
3b+3d+y\ge -1,\ -3b +3d-y\ge -1,\  -b-d+y\ge -1,\ b-d-y\ge -1,\\
b+2c+d+y+2z\ge -1,\ b-2c +d+y -2z\ge -1,\ b-d-y\ge -1,\\
-b+2c+d-y-2z\ge -1,\ -b-2c+d-y+2z\ge -1,\ -b-d+y\ge -1,\\
b+3d+3y\ge -1,\ -b+3d-3y\ge -1,\ 3c+3d+u\ge -1,\ -3c+3d-u\ge -1,\\
2b+c+d+2z+u\ge -1,\ -2b+c+d -2z+u \ge -1,\ c-d-u\ge -1,\\
2b-c+d-2z-u\ge -1,\ -2b-c+d+2z-u\ge -1,\ -c-d+u\ge -1,\\
c+3d+3u\ge -1,\ -c+3d-3u\ge -1,\ 6d+v\ge -1,\  -2d+v\ge -1,\ v\le 1.
\end{array}\end{equation}}
}
\end{lemma}

\begin{proof}
By definition, $Y\in M(\MET(K_n))$ if and only if, for all $ij\in E_6$, 
$y:=Y(e_0\pm e_{ij})$ satisfies all triangle inequalities.
By symmetry, it suffices to consider the 
cases when $ij=12$, $13$, $23$ or $34$.
Let $ij=12$.
Due to symmetry and to the fact that $y_{12}=\pm y_0$,  it suffices to
consider the triangle inequalities based on  the triples 
 $134$ and $345$.
The triangle inequalities based on triple 134 can be reformulated as
$$\begin{array}{c}
a+2b+2c+d+x \ge -1,\ a-2b-2c+d+x\ge -1,\ a-d-x\ge -1,\\
$$-a +2b-2c+d-x\ge -1,\  -a-2b+2c+d-x\ge -1,\  -a-d-x\ge -1
\end{array}$$
and those based on  triple 345 give
$$ a+3d+3x \ge-1,\ -a+3d-3x\ge -1.$$
Let now $ij$ be one of $13, 23,34$. Due to symmetry and to the fact that $y_{ij}=\pm y_0$, 
it suffices to consider the triangle inequalities 
based on the triples  124,  145, 245 and 456.
When $ij=13$, we find the relations from (\ref{relYT}) 
$a+2b+2c+d+z\ge -1$ until  $-b+3d-3y\ge -1$. When $ij=23$
we find the relations $3c+3d+u\ge -1$ until  $ -c+3d-3u\ge -1$.
When $ij=34$ we find the relations $6d+v\ge -1, -2d+v\ge -1,\ v\le 1.$
 \qquad\end{proof}

%\vspace*{-5mm}
\begin{corollary}\label{corxabcd}
The vector $x(a,b,c,d)$ belongs to
$N(K_n)$ ($n\ge 6$) if and only if
\begin{equation}\label{xabcdN}
\begin{array}{c}
d\le 1,\ \pm 2b +d\ge -1, \ \pm 2c+d\ge -1, \ \pm 2b+3d\ge -1,\ \pm 2c+3d\ge -1,\\
\pm a \pm b\pm c\ge -1,\ \pm  a \pm 3b \pm 3c + 3d \ge -2,\\
\pm 3 a\pm 5b \pm 9c +6d \ge -5,\ \pm 3 a \pm 9b \pm 5c +6d \ge -5,\\
\end{array}\end{equation}
where in lines 2 and 3 of the above system there is an even number of
minus signs (e.g., $a+b+c\ge -1,\ -a-b+c\ge -1,$ etc.).
The vector $x(a,c)$ belongs to $N(K_n)$ ($n\ge 6$)
if and only if $a,c$ satisfy
 \begin{equation}\label{metN}
 \begin{array}{l}
\pm 2a+c\ge -1,\  \pm 2a+3c\ge -1,\ 
\pm 12a+11c\ge -5,\  -{1\over 5}\le c\le 1.
\end{array}\end{equation}
\end{corollary}

\begin{proof}
We saw above that $x=x(a,b,c,d)\in N(K_n)$ if and only if
$(1,x)=Ye_0$ for some matrix $Y\in M(\MET(K_n))$ having
pattern $(a,b,c,d,x,y,z,u,v)$ for some $x,y,z,u,v$. Using the 
computer code {\bf cdd+} of Fukuda \cite{Fu97} for polyhedral 
computations, we have verified that the projection
on the subspace indexed by the variables $a,b,c,d$
of the polytope defined by the linear system (\ref{relYT})
is described by the linear system (\ref{xabcdN}).
One can then verify that for $a=b$ and $c=d$, the system 
(\ref{xabcdN}) is equivalent to 
(\ref{metN}).
 \qquad\end{proof}


We now characterize membership in $N'(K_n)$ for a vector with pattern
$(a,c)$.


\begin{lemma}\label{lemY2}
Let $Y\in {\cal Y}_n$ with pattern $(a,c,x,u)$ and $n\ge 6$.
Then, $Y\in M'(\MET(K_n))$ if and only if 
$a$, $c$, $x$,  $u$  satisfy   the linear inequalities:
\begin{equation}\label{relYT'}
\begin{array}{c}
 -2c+u\ge -1,   \  2c-3u\ge -1,\ 10c+5u\ge -1, \
2a-2x-u\ge -1, \\  -2a+2x-u\ge -1,\
 4a + 6c +4x+u\ge -1,\ -4a+6c-4x+u\ge -1,\\
 2a + 4c +6x +3u \ge -1,\ -2 a + 4c -6 x +3 u \ge -1
\end{array}
\end{equation}
 \noindent
as well as $6c+9u\ge -1$ when $n\ge 7$.
\end{lemma}

\begin{proof}
By definition, $Y\in M'(\MET(K_n))$ if and only if, for all $1\le i<j<k\le n$,
the vector $Y(e_0\pm  e_{ij}\pm e_{ik}\pm e_{jk})$
(with 0 or 2 minus signs)  satisfies all triangle inequalities.
By symmetry, it suffices to consider the two
cases when $ijk=123$ or $234$.
Consider first the case when $ijk=123$. Due to symmetry,
it suffices to consider the
triangle inequalities for the vectors 
$x:=Y(e_0+e_{12}+e_{13}+e_{23})$,
$y:=Y(e_0+e_{12}-e_{13}-e_{23})$ and
$z:=Y(e_0-e_{12}-e_{13}+e_{23})$
and based on the triples
 $145$ and $456$ (we also use the fact that 
 $x_{12}=x_{13}=x_{23}=x_0$, $y_{13}=y_{23}=-y_{12}=-y_0$ and
 $z_{12}=z_{13}=-z_{23}=-z_0$).
 The triangle inequalities for $x$  based on triple 
 145  are equivalent to
$$4a+6c+4x+u\ge -1,\ 2a-2x-u\ge -1,\ -2c+u \ge -1\leqno(a)$$
and those  based on triple 456 give the new relation
$$2a+4c+6x+3u\ge -1.\leqno(b)$$
The triangle inequalities for $y$ based on triples  145 and 456  yield,
respectively,
$$ -2a+2x-u\ge -1,\ 2c-3u \ge -1. \leqno(c)$$
The triangle inequalities for $z$ based on triples  145 and  456 give, respectively,
the relations:
$$ -4a+6c-4x+u\ge -1,\ -2a+4c-6x+3u\ge -1.\leqno(d)$$
Consider now the case when $ijk=234$.
Due to symmetry,  it suffices to look at the triangle inequalities 
for the vectors 
$x:=Y(e_0+e_{23}+e_{24}+e_{34})$
and $y:=Y(e_0-e_{23}-e_{24}+e_{34})$ and based on the triples
 125, 156, 256, and 567
(the latter occurring only for $n\ge 7$).
The triangle inequalities for $x$ 
based on  triples 125 and 156 give no new condition;
those for triple 256  give the condition
$$10c+5u\ge -1\leqno(e)$$
and, when $n\ge 7$, those for triple 567 yield
$$6c+9u\ge -1.\leqno(f)$$
No new condition is obtained when looking at the triangle inequalities for $y$.
The inequalities from (a)-(f) are those from (\ref{relYT'}).
 \qquad\end{proof}

\begin{corollary}\label{corxab}
For $n=6$, $x(a,c)\in N'(K_n)$ if and only if
\begin{equation}\label{metN'6}
\pm 2a+c\ge -1,\ \pm 5a + 5c \ge -2,\ 
 -{1\over 5}\le c\le 1
 \end{equation}
 and, for $n\ge 7$, $x(a,c)\in N'(K_n)$ if and only if $a,c$ satisfy 
 {\rm (\ref{metN'6})} together with  the inequalities
 $\pm 18 a+15 c\ge -7$.
 \end{corollary}

\begin{proof}
We have verified (using the computer program {\bf cdd+}  \cite{Fu97})
that the projection on the subspace indexed by the variables $a$ and $c$ 
of the polytope defined by the linear system 
(\ref{relYT'}) (resp. (\ref{relYT'}) together with $6c+5u \ge -1$)
is described by the linear system 
(\ref{metN'6}) (resp. (\ref{metN'6}) together with 
$\pm 18a +15 c \ge -7$). 
 \qquad\end{proof}

We will also need to check whether a matrix $Y\in {\cal Y}_n$ 
is positive semidefinite.
For concrete examples this can be checked using computer. However,
for a matrix $Y$ with simplified  pattern $(a,c,x,u)$ one can describe
explicitely the conditions on $a,c,x,u$ ensuring $Y\succeq 0$
(as positive semidefiniteness of $Y$ can be reformulated as
positive semidefiniteness of some smaller matrix $Z$ 
whose eigenvalues can be computed because $Z$ belongs 
to an association scheme); details will be given in the Appendix.








\subsection{Proof of Proposition \ref{prophyp6}}\label{secproof2}

We show here (non) validity of the gap inequality 
for $b_n=(n-4,1,\ldots,1)\in \oZ^n$ for the relaxations 
$\nu(K_n)$ ($\nu=N,\ldots,N'_+$).
Validity over $\nu(K_n)$ means that 
$B_n\ge  \rho_n:= -{1\over 2}(n^2-7n+14),$ where $B_n$ is defined in
(\ref{Bn}) (with $k=1$); note
 that $\rho_6=-4$, $\rho_7=-7$, $\rho_8=-11$.
As the program  (\ref{Bn}) admits an optimum solution
$x$ having some pattern $(a,c)$
we can, using the results from the preceding subsection, 
reformulate (\ref{Bn})  as a program in the variables 
$a$ and $c$. In particular, 
for $\nu=N'$ and $n=6$, (\ref{Bn}) can be reformulated as
$$\min( 10 a + 10 c\mid \ a,c \mbox{ satisfy (\ref{metN'6})})$$
and, for $\nu=N'$ and $n=7$, (\ref{Bn}) is reformulated as
$$\min (18a+15 c\mid \ a,c \mbox{ satisfy (\ref{metN'6}) and } 
\pm 18a +15 c\ge -7).$$
Hence, we deduce that the gap inequality for $b_n$ is valid for $N'(K_n)$ 
when $n=6,7$.

\medskip
We now show non validity for $N'(K_n)$ ($n\ge 8$) and $N_+(K_n)$
($n\ge 6$).
We first observe that it suffices to consider the two bottom 
cases: $n=8$ for $N'$ and $n=6$ for $N_+$. 
Indeed, the gap inequality for $b_n=(n-4, 1,\ldots,1)\in \oZ^n$  coincides with the inequality obtained from 
the gap inequality for $b_{n+1}=(n-3,1,\ldots,1)\in \oZ^{n+1}$ by anti-collapsing the nodes 1 and $n+1$. Therefore,
if $x\in \nu(K_n)$ violates the gap inequality for $b_n$, 
then by taking successive $(-1)$-extensions of $x$ 
we construct a point $y\in \nu(K_m)$ violating the gap inequality
for $b_m$ for any $m\ge n+1$. 

Let $a:=-{2\over 3}$ and $c:={1\over 3}$. Then $x(a,c) \in N'(K_n)$
for any $n\ge 7$ and $(n-4)(n-1)a+{n-1\choose 2}c<\rho_n$
for any $n\ge 8$. This shows that the gap inequality for $b_n$ is not valid for $N'(K_n)$ for  $n\ge 8$.

Let $a:=-{5\over 12}$, $c:={1\over 120}$, $x:={11\over 45},$
$u:=-{29\over 90}$. Then $x(a,c)\in N_+(K_6)$. Indeed, the matrix $Y\in {\cal Y}_6$ with simplified pattern $(a,c,x,u)$
belongs to $M_+(\MET(K_6))$; that is, $a,c, x,u$ satisfy 
(\ref{relYT})  and (\ref{releigX6}). 
(Note that $\lambda_0(X)=0$ in (\ref{releigX6}).)
As $10a+10c =-{49\over 12}<-4$, 
$x(a,c)$ violates the gap inequality for $b_6$.
We have found those values of $a,c,x,u$ with the help of
the software package SDPPACK \cite{SDP}. Using 
SDPPACK, we have solved the semidefinite programming problem
$$\min (10a+10c\mid Y\in M_+(\MET(K_6))  \mbox{ having some pattern } 
(a,c,x,u))$$
and found that the optimum is attained at the above values of $a,c,x,u$. 
(This is a problem in dimension $1+{6\choose 2}=16$ with 
${16\choose 2}-4+14+16=146$ linear (in)equalities; indeed, 
one can replace  the $2{6\choose 2} \times 4{6\choose 3}=2400$
triangle inequalities expressing $Y\in M(\MET(K_6))$ by the 14 linear inequalities 
from (\ref{relYT}).)

Note that 
$\min(10a+10 c \mid x(a,c)\in N(K_6))=-{30\over 7},$
attained at $a=-{2\over 7}$, $c=-{1\over 7}$.
This shows again  that the gap inequality  for $b_6$ is not valid
for $N(K_6)$ and, moreover, the strict inclusion
$N_+(K_6)\subset N(K_6)$.
The following result has been refered to  earlier in the paper.

\begin{lemma}\label{remhyp6}
While not valid for  $N(\MET(K_6))$,
the gap inequality for $(-2,1,1,1,1,1)$ 
{\em is} valid for $N(\MET(K_5^\nabla))\cap \LL_{K_5}$ (assigning 
$-2$ to the apex node).
\end{lemma}

\begin{proof}
Indeed, $x(a,c)$ belongs to $\LL_{K_5}$ if and only if
$c=2a-1$. Then, $x(a,c)\in N(\MET(K_6))$ implies that 
$-12a+11c\ge -5$ and, thus, $10a\ge 6$; that is, 
$-10a+10 c \ge -4$.
 \qquad\end{proof}

We now show that the gap inequality for $b_n$ is valid for $N^{n-5}(K_n)$
for $n\ge 7$. Again it suffices to show the result for the bottom case $n=7$ as the general result follows using induction.
(Indeed, 
consider $b_{n+1}=(n-3,1,\ldots,1)\in \oZ^{n+1}$.
Anti-collapsing of nodes 1 and $n+1$ yields the gap inequality
for $b_n$ which is valid for $N^{n-5}(K_n)$ by
the induction assumption, while collapsing of these two nodes yields
the gap inequality for $(n-2,1,\ldots,1)\in \oZ^n$ which is valid for
$\MET(K_n)$ (as it is a sum of triangle inequalities). Therefore, 
we deduce using Proposition \ref{propvalid1} that the gap inequality for
$b_{n+1}$  is valid for $N^{n-4}(K_{n+1})$.)
Our task is now to show that 
$$\min(18a+15 c\mid x(a,c)\in N^2(K_7))\ge -7.$$
For this we need to characterize when $x(a,c)\in N^2(K_7)$.
By definition, $x(a,c)\in N^2(K_7)$ if and only if
$(1,x(a,c))=Ye_0$ for some matrix $Y\in M(N(K_7))$ with simplified pattern
$(a,c,x,u)$ for some $x,u$. Due to symmetry,
$Y\in M(N(K_7))$ if and only if
$Y(e_0\pm e_{12})$, $Y(e_0\pm e_{23})\in N(K_7)$.
Note that the vector $Y(e_0+e_{12})$ is the 1-extension of 
a vector in $\oR^{E_6}$ with pattern $({a+c\over 1+a},{c+x\over 1+a})$;
the vector $Y(e_0-e_{12})$ is the $(-1)$-extension of $x({a-c\over 1-a},{c-x\over 1-a})\in \oR^{E_6}$;
the vector $Y(e_0+e_{23})$ is the 1-extension of 
$x({2a\over 1+c},{a+x\over 1+c},{2c\over 1+c},{c+u\over 1+c})\in \oR^{E_6}$;
the vector $Y(e_0-e_{23})$ is the $(-1)$-extension of
$x(0,0,{a-x\over 1-c},{c-u\over 1-c})\in \oR^{E_6}$.
Using Corollary \ref{corxabcd}, we find that 
$x({a+c\over 1+a},{c+x\over 1+a}), \ x({a-c\over 1-a},{c-x\over 1-a})$
belong to $  N(K_6)$ 
if and only if
\begin{equation}\label{N21}
{\small 
\begin{array}{c}
a-c-x\ge -1,\ -a-c+x\ge -1,\ 3a+3c+x\ge -1,\ -3a+3c-x\ge -1,\\
17a+23 c + 11x \ge -5,\ -17 a +23 c -11 x \ge -5,\ 7a -c-11x \ge -5,\\
-7 a -c + 11 x \ge -5,\
3a + 5c + 3x\ge -1,\ -3a + 5c -3 x \ge -1,\\
a+c-3x\ge -1, \ -a + c +3x\ge -1,\ a +5 c +5 x\ge -1, \ 
-a + 5c -5x \ge -1.
\end{array}}\end{equation}
Moreover, 
$x({2a\over 1+c},{a+x\over 1+c},{2c\over 1+c},{c+u\over 1+c})\in N(K_6)$
if and only if
\begin{equation}\label{N22}
{\small\begin{array}{c}
-{1\over 3}\le u\le 1,\ 2a + 2c + 2x +u \ge -1,\ -2a+2c -2x+u\ge -1,\\
2a+4c+2x+3u \ge -1,\ -2a+4c-2x+3u \ge -1,\ 6c+u\ge -1,\\
-2c+u\ge -1,\
8c+3u\ge -1,\ 3a+3c+x\ge -1,\ -3a +3c-x\ge -1,\\
a-c-x\ge -1,\ -a-c+x\ge -1,\
5a+11c +3x+3u\ge -2,\\
-5a +11c -3x+3u\ge -2,\ 
-a-c-3x+3u\ge -2, \ a -c +3x+3u\ge -2,\\
11 a + 29 c +5x+6u\ge -5,\
-11 a +29 c -5 x+6 u\ge -5,\
a-7c -5x+6u\ge -5,\\
-a -7c +5x+6u\ge -5,\
15a+21c+9x+6u\ge -5,\
-15a+21c -9x+6u\ge -5,\\
-3a+c-9x+6u\ge -1,\
3a+c +9x+6u\ge -5.
\end{array}
}\end{equation}
Finally, after noting that $x(0,0,x,u)\in N(K_6)$ if and only if
$-{1\over 3}\le u\le 1$, $-1\le x\le 1$, $\pm 2x+u\ge -1$, $\pm 2x+3u\ge -1$,
we find that $x(0,0,{a-x\over 1-c},{c-u\over 1-c})\in N(K_6)$
if and only if
\begin{equation}\label{N23}
{\small\begin{array}{c}
-a-c+x\ge -1,\ a-c-x\ge -1, \ -2c+u\ge -1,\ 2c-3u\ge -1,\\
2a-2x-u\ge -1,\ -2a+2x-u\ge -1,\ 2a+2c-2x-3u\ge -1, \\
-2a +2c +2x -3u \ge -1.\end{array}}
\end{equation}
Using computer we verified that the minimum value of $18a+15c$ 
subject to $a,c,x,u$ satisfying the linear system 
(\ref{N21}), (\ref{N22}) and (\ref{N23}) 
is equal to -7 (attained at $a=-{1\over 3}$, $c=-{1\over 15}$, $x={1\over 5}$, $u=-{1\over 15}$).
This shows that the gap inequality for $b_7$ is valid for $N^2(K_7)$.






\subsection{Proof of Propositions \ref{prophyp7} and \ref{propcut}}\label{secproof3}



We begin with  showing that  the gap inequality for $c_n=(1,\ldots,1)\in \oZ^n$ 
is not valid for $N_+'(K_n)$ for $n\ge 7$ odd.
Let first $n=7$ and set $a=c:=-{11\over 70}$ and $x=u:={4\over 35}$. Then the matrix
$Y\in {\cal Y}_7$ with pattern $(a,c,x,u)$ belongs to
$M'_+(K_7)$, because $a,c,x,u$ satisfy 
(\ref{relYT'}) and (\ref{releigX}) (for $n=7$).
Hence  $x(a,a)$ belongs to $N'_+(K_7)$ and violates the gap inequality for $c_7$ as 
$21 a<-3$. 
We extend the result for any odd $n\ge 7$ by induction.
Suppose $x\in N'_+(K_n)$
violates the gap inequality for $c_n$ for some odd $n\ge 7$. 
For $\epsilon=\pm 1$, the $\epsilon$-extension 
$x^\epsilon$ of $x$ belongs to
$N'_+(K_{n+1})$ and thus $\hat x:={1\over 2}(x^1+x^{-1})\in N'_+(K_{n+1})$ with 
$\hat x_{i,n+1}=0$ ($1\le i\le n$) and $\hat x_{ij}=x_{ij}$
($ij\in E_n$). Consider now the $(-1)$-extension
$y$ of $\hat x$ defined by $y_{n+1,n+2}=-1$. Then $y\in N'_+(K_{n+2})$ and
violates the gap inequality for $c_{n+2}$.
This proves the first part of  Proposition \ref{prophyp7} 
and the strict inclusion $\CUT(K_n)\subset N'_+(K_n)$ ($n\ge 7$).

\medskip
We now show that the gap inequality for $c_n$ is not valid for $N^2(K_n)$
for odd $n\ge 7$. As observed above, it suffices to consider the case $n=7$.
We show that $$\min(21 a\mid x(a,a)\in N^2(K_7))<-3.$$
Using the results from the preceding subsection, we find that
$x(a,a)\in N^2(K_7)$ if and only if there exists $x\in \oR$ satisfying
$x({2a\over 1+a},{a+x\over 1+a}),\ x(0,{a-x\over 1-a})\in N(K_6)$, 
which in turn is equivalent to the following linear system 
\begin{equation}\label{N27}\begin{array}{c}
-{1\over 3}\le x\le 1,\ -2a+x\ge -1,\ 6a+x\ge -1,\\ 40a+11x\ge -5,\
-8a+11x\ge -5,\\ 8a+3x\ge -1,\ 2a-3x\ge -1,\\ 6a+5x\ge -1,\ 4a-5x\ge -1.
\end{array} \end{equation}
One can verify that the minimum value of $a$ for which 
(\ref{N27}) holds  is $-{9\over 61}$ (attained at 
$a=-{9\over 61}$, $x={5\over 61}$) and thus
$$x(a,a)\in N^2(K_7)\Longleftrightarrow 
-{9\over 61}\cdot 21\le a\le 1.$$
As $-{9\over 61}\cdot 21<-3$, we deduce that the gap inequality for $c_7$ is not valid for 
$N^2(K_7)$.





\medskip
We finally prove Proposition \ref{propcut}.
The equality $\CUT(K_n)=N(K_n)$ ($n\le 5$) follows from
Corollary \ref{corindex0} and $\CUT(K_6)=N'(K_6)\subset N_+(K_6)$ from
Proposition \ref{prophyp6}. 
We now verify the strict inclusions
$N'_+(K_n)\subset N_+(K_n)\subset N(K_n)$ for $n\ge 6$.
It suffices to check it for $n=6$; the first one follows from the above.
For the second one note that $x(-{2\over 7},-{1\over 7})\in N(K_6)\setminus N_+(K_6)$. 
Indeed if $x\in N_+(K_6)$ then there exist $x,u$ for which the matrix $Y$ with pattern
$(-{2\over 7},-{1\over 7},x,u)$ belongs to
$M_+(K_6)$. 
The inequalities $a+2b +2c+d+x \ge -1$ and $-a+3d-3x\ge -1$ from (\ref{relYT})
imply that $x={2\over 7}$
and the inequalities $3c+3d+u\ge  -1$ and  $2b-c+d-2z-u \ge -1$ imply that
$u=-{1\over 7}$ 
(we have here $a=b,c=d,x=y=z,u=v$).
 However the matrix $Y$ is not positive semidefinite since
the eigenvalue $\lambda_0$ (from (\ref{releigX6})) is negative.





\Appendix
\section{Positive Semidefinite Matrices with a Simplified Pattern}
We will use the following standard  result about Schur complements
(see, e.g., 
\cite{HJ91}).

\begin{lemma}\label{lemschur}
Let $X=\left(\matrix{A & B\cr B^T & C}\right)$ be a symmetric  matrix. 
If $A$ is nonsingular, then 
$$X\succeq 0 \Longleftrightarrow
A\succeq 0 \mbox{ and }  C-B^TA^{-1}B\succeq 0.$$
The matrix 
 $C-B^TA^{-1}B\succeq 0$ is known as the {\em Schur complement} of 
 $A$ in $X$. \qquad
 \end{lemma}

\begin{figure}
\label{figpattern}
$$\bordermatrix{&0 & 12 & 13 & 14 & 15 & 16 & 23 & 24 & 25 & 26 & 34 & 35 & 36 & 45 & 46 & 56 \cr
0 & 1 & a & a & a & a & a & c & c & c & c & c & c & c & c & c & c\cr
12& a & 1 & c & c & c & c & a & a & a & a & x & x & x & x & x & x\cr
13& a & c & 1 & c & c & c & a & x & x & x & a & a & a & x & x & x \cr
14& a & c & c & 1 & c & c & x & a & x & x & a & x & x & a & a & x\cr
15& a & c & c & c & 1 & c & x & x & a & x & x & a & x & a & x & a \cr
16& a & c & c & c & c & 1 & x & x & x & a & x & x & a & x & a & a\cr
23& c & a & a & x & x & x & 1 & c & c & c & c & c & c & u & u & u \cr
24& c & a & x & a & x & x & c & 1 & c & c & c & u & u & c & c & u\cr
25& c & a & x & x & a & x & c & c & 1 & c & u & c & u & c & u & c \cr
26& c & a & x & x & x & a & c & c & c & 1 & u & u & c & u & c & c \cr
34& c & x & a & a & x & x & c & c & u & u & 1 & c & c & c & c & u\cr
35& c & x & a & x & a & x & c & u & c & u & c & 1 & c & c & u & c\cr
36& c & x & a & x & x & a & c & u & u & c & c & c & 1 & u & c & c \cr
45& c & x & x & a & a & x & u & c & c & u & c & c & u & 1 & c & c\cr
46& c & x & x & a & x & a & u & c & u & c & c & u & c & c & 1 & c\cr
56& c & x & x & x & a & a & u & u & c & c & u & c & c & c & c & 1\cr}
$$
\caption{A matrix $Y\in {\cal Y}_6$ with simplified  pattern $(a,c,x,u)$}
\end{figure}


Let $Y\in {\cal Y}_n$ with simplified  pattern $(a,c,x,u)$ (i.e., $a=b$, $c=d$, $x=y=z$, $u=v$)
and let $Z$ denote the Schur complement in $Y$ of its $(0,0)$-entry.
Suppose first that $a=c$ and $x=u$. then $Z$ has the property that 
the value of its $(ij,hk)$-th entry  depends only whether the pairs $ij$ and $hk$ meet.
Let $A_n$ (resp. $B_n$)  denote the symmetric matrix indexed by $E_n$ 
whose entries are all equal to 0 except entry
$(ij,hk)$  equal to 1 if $|\{i,j\}\cap \{h,k\}|=1$ (resp. $=0$).
Then,
$$Z=(1-a^2)I_{d_n}+(a-a^2)A_n +(x-a^2)B_n$$
(where $I_{d_n}$ is the identity matrix of order $d_n$).
The matrices $A_n$ and $B_n$ commute (they are the adjacency
matrices of the Johnson scheme $J(n,2)$) and thus have a common basis of eigenvectors.
From this follows that a matrix $X=\alpha A_n+\beta B_n +\gamma I_{d_n}$
has three distinct eigenvalues
$$\begin{array}{c}
\lambda_0(X)=2(n-2)\alpha +{n-2\choose 2}\beta +\gamma,\ \lambda_1(X)=-2\alpha +\beta+\gamma,\\
\lambda_3(X)=(n-4)\alpha -(n-3)\beta +\gamma.\end{array}$$
Therefore, we deduce that $Y\succeq 0$ if and only if
\begin{equation}\label{releigX}
\begin{array}{c}
\lambda_0(Z)=2(n-2)(a-a^2)+{n-2\choose 2}(x-a^2)+1-a^2\ge 0,\\
\lambda_1(Z)=-2a+x+1\ge 0,\ \lambda_2(Z)=(n-4)a-(n-3)x+1\ge 0.
\end{array}\end{equation}
In the general case, the matrix $Z$ is not of the form
$\alpha A_n+\beta B_n+\gamma_{d_n}$. Let $Z_1$ be its principal submatrix indexed by
$\{12,\ldots,1n\}$; its eigenvalues are $1-c$ and $1+(n-2)c-(n-1)a^2$.
If $1-c\ne 0$ and $1+(n-2)c-(n-1)a^2\ne 0$, we can define the Schur complement
$X$ of $Z_1$ in $Z$ which turns out to be of the form
$\alpha A_{n-1}+\beta B_{n-1} +\gamma I_{d_{n-1}}$ and whose eigenvalues are 
therefore computable.
We mention the result only in the case $n=6$: Assuming that
$c,\ 1+4c-5a^2\ne 0$, $Y\succeq 0$ if and only if 
\begin{equation}\label{releigX6}
\begin{array}{c}
c\le 1,\ 1+4c-5a^2 \ge 0, \\
\lambda_0(X)=1+6c-10 c^2 +3u-2{(2a+3x-5ac)^2\over 1+4c-5a^2}\ge 0,\\
 \lambda_1(X)=1-2c+u\ge 0,\ 
 \lambda_2(X)=1+c-2u-3{(a-x)^2\over 1-c}\ge 0.
\end{array}
\end{equation}







 \begin{thebibliography}{}

\bibitem{SDP}
{\sc F. Alizadeh, J.-P. Haeberly, M.V.
Nayakkankuppam, M.L. Overton, and S. Shmieta.}
{\em SDPpack user's guide - version 0.9 Beta.}
Technical Report TR1997-737, Courant Institute of Mathematical
Sciences, NYU, New York, June 1997.

\bibitem{AW00}
{\sc M.F. Anjos and H. Wolkowicz.}
{\em Strenghtened semidefinite relaxations via a second lifting for the max-cut problem.}
Research Report CORR 2000-19, University of Waterloo, 2000. 
(To appear in  Discrete Applied Mathematics.)


\bibitem{BCC93}
{\sc E. Balas, S. Ceria, and G. Cornu\'ejols.}
{\em A lift-and-project cutting plane algorithm for
mixed 0-1 programs.}
Mathematical Programming, 58:295--324, 1993.



\bibitem{Ba83}
{\sc F. Barahona.}
{\em The max-cut problem on graphs not contractible to $K_5$.}
Operations Research Letters, 2:107--111, 1983.

\bibitem{Ba82}
{\sc F. Barahona.}
{\em On the computational complexity of Ising spin glass models.}
Journal of Physics A, Mathematical and General, 15:3241--3253, 1982.


\bibitem{Ba93}
{\sc  F. Barahona.}
{\em On cuts and matchings in planar graphs.}
Mathematical Programming, 60:53--68, 1993.


\bibitem{BM86}
{\sc F. Barahona and A.R. Mahjoub.}
{\em On the cut polytope.}
 Mathematical Programming, 36:157--173, 1986.


\bibitem{CD00}
{\sc W. Cook and S. Dash.}
{\em On the matrix-cut rank of polyhedra.}
Mathematics of Operations Research, 26:19--30, 2001.


\bibitem{De60}
{\sc M.E. Tylkin (=M. Deza). }
{\em On Hamming geometry of unitary cubes} (in Russian).
Doklady Akademii Nauk SSSR, 134:1037--1040, 1960. 
(English translation in Cybernetics and Control Theory, 134(5):940--943, 1961.)

\bibitem{DL97}
{\sc M. Deza and M. Laurent.}
{\em Geometry of Cuts and Metrics.}
Vol. 15 of  Algorithms and Combinatorics, Springer
Verlag, 1997.

\bibitem{Fu97}
{\sc K. Fukuda.}
 cdd/cdd+ computer codes for polyhedral computations available 
from { http://www.ifor.math.ethz.ch/staff/fukuda/fukuda.html}.

\bibitem{GT00}
{\sc M.X. Goemans and L. Tun\c{c}el.}
{\em When does the positive semidefiniteness constraint help 
in lifting procedures ?}
To appear in  Mathematics of Operations Research..

\bibitem{GW95}
{\sc M.X. Goemans and D.P. Williamson.}
{\em Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite
programming.}
Journal of ACM, 42:1115--1145, 1995.

\bibitem{GLS88}
{\sc M. Gr\"otschel, L. Lov\'asz and A. Schrijver.}
{\em Geometric Algorithms and Combinatorial Optimization}.
Vol. 2 of  Algorithms and Combinatorics, 
Springer Verlag, 1988.

\bibitem{HJ91}
{\sc R.A. Horn and C.R. Johnson.}
{\em Topics in Matrix Analysis.}
Cambridge University Press, Cambridge, 1991.

\bibitem{Las00}
{\sc J.B. Lasserre.}
{\em Optimality conditions and LMI relaxations for $0-1$ programs.}
 Technical Report N. 00099, 2000.


 \bibitem{Las01b}
{\sc  J.B. Lasserre.}
{\em  An explicit exact SDP relaxation for nonlinear $0-1$ programs.}
 In  Proceedings of the 8th conference on Integer Programming
  and Combinatorial Optimization, Utrecht, The Netherlands, 2001.

\bibitem{La01}
{\sc M. Laurent.}
{\em A comparison of the Sherali-Adams, 
Lov\'asz-Schrijver and Lasserre relaxations for $0-1$ programming.}
Preprint, 2001.

\bibitem{LP96}
{\sc M. Laurent and S. Poljak.}
{\em Gap inequalities for the cut polytope.}
 European Journal of Combinatorics, 17:233--254, 1996.

\bibitem{LPR97}
{\sc M. Laurent, S. Poljak, and F. Rendl.}
{\em Connections between semidefinite relaxations of the max-cut and stable set 
problems.}
 Mathematical Programming, 77:225--246, 1997.

\bibitem{LO99}
{\sc C. Lemar\'echal and F. Oustry.}
{\em Semidefinite relaxations and Lagrangian duality with application to combinatorial optimization.}
INRIA Rh\^one-Alpes, Montbonnot St Martin, France.
Rapport de Recherche n. 3710, June 1999, 40 pages.

\bibitem{LS91}
{\sc L. Lov\'asz and A. Schrijver.}
{\em Cones of matrices and set-functions and 
$0-1$ optimization.}
 SIAM Journal on Optimization, 1:166--190, 1991.

\bibitem{PR95}
{\sc S. Poljak and F. Rendl.}
{\em Nonpolyhedral relaxation of graph-bisection problems.}
SIAM Journal on Optimization, 5:467--487, 1995.

\bibitem{PRW95}
{\sc S. Poljak, F. Rendl and H. Wolkowicz.}
{\em A recipe for semidefinite relaxation for $(0,1)$-quadratic 
programming.}
Journal of Global Optimization, 7:51--73, 1995.


\bibitem{Pa89}
{\sc M. Padberg.}
{\em The boolean quadric polytope: Some characteristics, facets and relatives.}
Mathematical Programming, 45:139--172, 1989.

\bibitem{RS}
{\sc N. Robertson and P.D.  Seymour. }
{\em Graphs minors XX. Wagner's conjecture.}
1988.

\bibitem{Sc37}
{\sc I.J. Schoenberg.}
{\em On certain metric spaces arising from Euclidean spaces
by a change of metric and their imbedding in Hilbert spaces.}
 Annals of Mathematics, 38:787--793, 1937.

\bibitem{SA90}
{\sc H.D.  Sherali and W.P. Adams.}
{\em A hierarchy of relaxations between the continuous and convex hull representations for 
zero-one programming problems.}
 SIAM Journal on Discrete Mathematics, 3:411--430, 1990.

\bibitem{ST99}
{\sc T. Stephen and L. Tun\c{c}el.}
{\em On a representation of the matching polytope via semidefinite 
liftings.}
 Mathematics of Operations Research, 24:1--7, 1999.


 \end{thebibliography}





\end{document}