\documentstyle[11pt]{article} \setlength{\oddsidemargin}{0in} \setlength{\topmargin}{-.35in} \addtolength{\textwidth}{1.2in} \addtolength{\textheight}{1.5in} \def\R{\hbox{\sf I\kern-.12em R}} \def\Z{\hbox{\sf Z\kern-.34em Z}} \newtheorem{theorem}{Theorem}[section] \newtheorem{prob}[theorem]{Problem} \newtheorem{example}[theorem]{Example} \newtheorem{prop}[theorem]{Proposition} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{remark}[theorem]{Remark} \def\one{{\bf 1}} \def\T{^{\sf T}} \def\tr{{\rm tr}} \def\STAB{{\rm STAB}} \def\QSTAB{{\rm QSTAB}} \def\FRAC{{\rm FRAC}} \def\THETA{{\rm TH}} \def\rk{{\rm rk}} \def\mod{{\rm mod~}} \tolerance=2000 \begin{document} \begin{center} {\LARGE\bf Semidefinite programs and combinatorial optimization}\\ \medskip Lecture notes by L.~Lov\'asz\\ December 1995 \end{center} \noindent{\large\bf Outline} \medskip \ref{INTRO}.~Introductory examples: Shannon capacity and maximum cuts. \ref{PRELIM}.~Preliminaries: linear programming, semidefinite matrices. \ref{GENERAL}.~General properties of semidefinite programs: equivalent forms, Farkas Lemma, Duality Theorem, Ellipsoid method, Interior point method. \ref{EIGEN}.~Getting semidefinite programs I: eigenvalues of graphs and the method of variables. \ref{GEOM}.~Getting semidefinite programs II: geometric representations of graphs. Unit distance representations; orthogonal representations, properties of $\vartheta$. \ref{STABLE}.~The stable set polytope: facets, linear and non-linear relaxations. \ref{QUAD}.~Getting semidefinite programs III: quadratic constraints and inference rules. More on the stable set polytope. \ref{OPEN}.~Extensions and open problems: other eigenvalue results, inference rules and higher degree constraints, bounds on approximation. \section{Introductory examples}\label{INTRO} \subsection{Shannon capacity} The {\it strong product} $G\cdot H$ of two graphs $G=(V,E)$ and $H=(W,F)$ is defined as the graph with $V(G\cdot H)=V\times W$, with $(i,u)(j,v)\in E(G\cdot H)$ iff $ij\in E$ and $uv\in F$, or $ij\in E$ and $u=v$, or $i=j$ and $uv\in E$. The product of $k$ copies of $G$ is denoted by $G^k$. We denote by $\alpha(G)$ the maximum number of independent points (the maximum size of a stable set) in graph $G=(V,E)$. Thus $\alpha(G^k)$ is the maximum number of words of length $n$, composed of elements of $V$, so that for every two words there is at least one $i$ ($1\le i\le k$) such that the $i$-th letters are different and non-adjacent in $G$. The {\it Stable Set Problem} is the problem of finding $\alpha(G)$. \begin{prop} The Stable Set Problem is NP-hard. In fact, it is NP-hard to determine $\alpha(G)$ with a relative error less than $n^{1/10}$, where $n=|V|$. \end{prop} The {\it Shannon capacity} of a graph $G$ is the value $\Theta(G)=\lim_{k\to\infty} \alpha(G^k)^{1/k}$. It is not known whether $\Theta(G)$ can be computed by any algorithm (polynomial or not). The smallest graph for which $\Theta(G)$ cannot be computed by elementary means is the pentagon $C_5$. If we set $V(C_5)=\{0,1,2,3,4\}$ with $E(C_5)=\{01,12,23,34,40\}$, then $C_5^2$ contains the stable set $\{(0,0),(1,2),(2,4),(3,0),(4,1)\}$. Hence $\Theta(C_5)\ge \sqrt{5}$. We show that equality holds here (Lov\'asz \cite{LL2}). Consider an ``umbrella'' with handle $e_1$ and 5 ribs in $\R^3$ and open it up to the point when non-consecutive ribs are orthogonal. This way we get $5$ unit vectors $u_0,u_1,u_2,u_3,u_4$, assigned to the nodes of $C_5$ so that each $u_i$ forms the same angle with $e_1$ and any two non-adjacent nodes are labelled with orthogonal vectors. Elementary geometry gives $e_1\T u_i=5^{-1/4}$. Taking tensor products, we get a similar labelling of the nodes of $C_5^k$ by unit vectors $v_i\in\R^{3k}$, so that any two non-adjacent nodes are labelled with orthogonal vectors. Moreover, $e_1\T v_i=5^{-k/4}$ for every $i\in V(C_5^k)$. If $S$ is any stable set in $C_5^k$, then $\{v_i:~i\in S\}$ is a set of mutually orthogonal unit vectors, and hence $$ \sum_i (e_1\T v_i)^2 \le |e_1|^2 = 1. $$ The left hand side is $|S|5^{-k/2}$, whence $|S|\le 5^{k/2}$. Hence $\Theta(C_5)= \sqrt{5}$. For a general graph $G=(V,E)$, the best bound that can be achieved by this method is $$ \vartheta(G) = \min \max_{i\in V} {1\over (e_1\T v_i)^2}, $$ where the minimum is over all ``orthonormal representations'' of $G$, i.e., labellings of $V$ by unit vectors in some $\R^d$ so that non-adjacent nodes are labelled by orthogonal vectors. This value can be computed in polynomial time, and various properties of it and formulas for it can be derived, using semidefinite optimization, as we shall see \cite{LL2}. \subsection{Maximum cuts} A {\it cut} in a graph $G=(V,E)$ is the set of edges connecting a set $S\subseteq V$ to $V\setminus S$, where $\emptyset\subset S\subset V$. Assume that we are given a weighting $w:~V\to\R_+$. The weight of a subset $A\subseteq E$ is defined as the sum of weights in $A$. The {\it Max Cut Problem} is to find a cut with maximum weight. \begin{prop}{\rm \cite{Ar,Bell}} The Max Cut Problem is NP-hard. In fact, it is NP-hard to determine the maximum weight of a cut with a relative error less than $1$ percent. \end{prop} \begin{prop} For any fixed ordering $(v_1,\dots,v_n)$ of the nodes, color $v_1,v_2,\dots,v_n$ successively red or blue so that for each $i$, $v_i$ is colored blue iff the total weight of edges connecting $v_i$ to blue nodes among $v_1,\dots,v_{i-1}$ is less than the total weight of edges connecting $v_i$ to red nodes in this set. Then the weight of the cut formed by the edges between red and blue nodes is at least $w(E)/2$. \end{prop} \begin{corollary} The maximum weight of cut can be approximated from below in polynomial time with a multiplicative error of at most $1/2$. \end{corollary} There is an even easier randomized algorithm to achieve this approximation, at least in expected value: \begin{prop} Let us 2-color the nodes of $G$ randomly, so that each node is colored red or blue independently, with probability $1/2$. Then the expected weight of the cut formed by the edges between red and blue nodes is $w(E)/2$. \end{prop} \begin{theorem}{\rm [Goemans and Williamson]}\label{GOEMANS} The maximum weight of cut can be approximated from below in polynomial time with a multiplicative error of at most $.878$. \end{theorem} The algorithm of Goemans and Williamson depends on the following lemmas. \begin{lemma}\label{ANGLE} Let $u,v\in\R^n$, $|u|=|v|=1$. The probability that a random hyperplane $H$ through $0$ separates $u$ and $v$ is $\alpha /\pi$, where $\alpha = \arccos u\T v$ is the angle between $u$ and $v$. \end{lemma} \begin{lemma} If $-1\le t\le 1$ then $\arccos t \ge (1-\sin\theta) (1-t)$, where $\pi/2< \theta<\pi $ is the solution of $\theta \sin\theta +\cos\theta = 1$. \end{lemma} \begin{theorem} A labelling $u:~V\to\R^n$ such that $|u_i|=1$ for all $i\in V$ and $\sum_{ij\in E} w_{ij} u_i\T u_j$ is minimized can be computed in polynomial time. \end{theorem} \section{Preliminaries}\label{PRELIM} \subsection{Linear programming} All matrices and vectors are real. \begin{lemma}[Farkas Lemma] \label{FARKAS1} A system of linear inequalities $a_1^T x \le b_1$, $\ldots$, $a_m^T x \le b_m$ has no solution iff there exist $\lambda_1,\ldots,\lambda_m\ge 0$ such that that $\sum_i \lambda_ia_i=0$ and $\sum_i\lambda_ib_i =-1$. \end{lemma} \begin{lemma}[Farkas Lemma, inference version] \label{FARKAS2} Let $a_1,\ldots,a_m,c\in\R^n$, $b_1,\ldots,b_m,d\in\R$. Assume that the system $a_1^T x\le b_1,\ \ldots,\ a_m^T x\le b_m$ has a solution. Then $c^Tx\le d$ for all solutions of $a_1^T x\le b_1,\ \ldots,\ a_m^T x\le b_m$ iff there exist $\lambda_1,\ldots,\lambda_m\ge 0$ such that $c=\sum_i\lambda_ia_i$ and $d\ge \sum_i\lambda_i b_i$. \end{lemma} A typical linear program has the following form. \begin{eqnarray}\label{LINEAR} \hbox{maximize~} &&c\T x\nonumber \\ \hbox{subject to~}&&\cases{a_1\T x\le b_1 & \cr \vdots & \cr a_m\T x\le b_m & \cr} \end{eqnarray} These inequalities can be summed up in matrix form as $Ax\le b$, where $A$ is a matrix with $m$ rows and $m$ columns and $b\in\R^m$. There are many alternative ways to describe a linear program. We may want to maximize instead of minimize; we may have equations, and/or inequalities of the form $\ge$. Sometimes we consider only non-negative variables; the inequalities $x_i\ge 0$ may be included in (**), but it may be adventageous to separate them. All these versions are easily reduced to each other. The {\em dual} of (\ref{LINEAR}) is the linear program \begin{eqnarray}\label{LINEAR2} \hbox{minimize } && b\T y \nonumber \\ \hbox{subject to } &&\cases{ A\T y=c, &\cr y\ge 0.&\cr} \end{eqnarray} \begin{theorem}[Duality Theorem] If either one of the primal and dual programs has an optimum solution, then so does the other and the two optimum values are equal. The primal program is infeasible iff the dual is unbounded. The dual program is infeasible iff the primal is unbounded. \end{theorem} \begin{theorem}[Complementary slackness] Let $x$ be a solution of the primal program and $y$, a solution of the dual program. The both $x$ and $y$ are optimal if and only if for every $j$ with $y_j>0$, the $j$th constraint of the primal problem is satisfied with equality. \end{theorem} \subsection{Linear algebra} We denote by $\tr(A)$ the trace of the (square) matrix $A$. On the space $\R^{n\times m}$ of $n\times m$ matrixes, the operation $$ A\cdot B = \sum_{i=1}^n\sum_{j=1}^m a_{ij}b_{ij} = tr(A\T B) $$ defines an inner product. Let $A$ be a symmetric matrix. A {\it symmetric minor} of $A$ is a submatrix $B$ obtained by deleting some rows and the corresponding columns. All eigenvalues of a symmetric matrix are real. Every symmetric matrix can be written az $U\T DU$, where $U$ is an orthogonal matrix and $D$ is a diagonal matrix. The eigenvalues of $A$ are just the diagonal entries of $D$. \begin{theorem}[Interlacing eigenvalues] Let $A$ be an $n\times n$ symmetric matrix with eigenvalues $\lambda _1\ge \dots\lambda_n$. Let $B$ be an $(n-k)\times(n-k)$ symmetric minor of $A$ with eigenvalues $\mu _1\ge\dots\ge\mu_{n-k}$. Then $$\lambda _i\le \mu _i\le \lambda _{i+k}.$$ \end{theorem} A symmetric $n\times n$ matrix $A$ is called {\it positive semidefinite}, if all of its eigenvalues are non-negative. This property is denoted by $A\succeq 0$. We write $A\succeq B$ if $A-B\succeq 0$. This defines a partial order on matrices. \begin{prop} The following are equivalent: \smallskip {\rm (i)} $A$ is positive semidefinite; \smallskip {\rm (ii)} the quadratic form $x^TAx$ is non-negative for every $x\in\R^n$; \smallskip {\rm (iii)} $A$ can be written as the Gram matrix of $n$ vectors $u_1,...,u_n\in\R^m$ for some $m$; this means that $a_{ij}=u_i\T u_j$. Equivalently, $A=U\T U$ for some matrix $U$. \smallskip {\rm (iv)} The determinant of every symmetric minor is non-negative. \end{prop} The least $m$ for which a representation as in (iii) is possible is the rank of $A$. The diagonal entries of any positive semidefinite matrix are non-negative, and all entries in a row or column with a $0$ diagonal entry are $0$. In particular, the trace of a positive semidefinite matrix $A$ is non-negative, and $\tr(A)=0$ if and only if $A=0$. The sum of two positive semidefinite matrices is again positive semidefinite. The product of two positive semidefinite matrices is not necessarily positive semidefinite. \begin{lemma}\label{PRODUCT} {\rm (a)} If $A$ and $B$ are positive semidefinite matrices that $A\cdot B=\tr(AB)\ge 0$, and equality holds iff $AB=0$. \smallskip {\rm (b)} A matrix $A$ is positive semidefinite iff $A\cdot B \ge 0$ for every positive semidefinite matrix $B$. \end{lemma} \begin{prop}\label{CONE} The set of all positive semidefinite matrices forms a convex closed cone ${\cal P}$ in $\R^{n\times n}$. The cone ${\cal P}$ is non-polyhedral for $n\ge 2$. The polar cone of ${\cal P}$ is itself. \end{prop} \begin{theorem}[Perron-Frobenius] If an $n\times n$ matrix has non-negative entries then it has a non-negative real eigenvalue $\lambda$ which has maximum absolute value among all eigenvalues. This eigenvalue $\lambda$ has a non-negative real eigenvector. If, in addition, the matrix has no block-diagonal decomposition, i.e., it does not contain a $k\times(n-k)$ block of $0$-s disjoint from the diagonal, then $\lambda$ has multiplicity $1$ and the corresponding eigenvector is positive. \end{theorem} \section{Semidefinite programs}\label{GENERAL} A semidefinite program is an optimization problem of the following form: \begin{eqnarray}\label{SEMIDEF} \hbox{minimize~} &&c\T x \nonumber \\ \hbox{subject to~}&& x_1A_1 + \dots x_nA_n - B\succeq 0 \end{eqnarray} Here $A_1,\dots,A_n,B$ are given symmetric $m\times m$ matrices, and $c\in\R^n$ is a given vector. The special case when $A_1,\dots,A_n,B$ are a diagonal matrices is just a ``generic'' linear program. We denote by $v_{\rm primal}$ the supremum of the objective function. \medskip \begin{example}\label{GAP}\rm Consider the semidefinite program \begin{eqnarray*} \hbox{maximize} &&-x_1 \\ \hbox{subject to} && \left(\matrix{x_1 & 1 & 0 \cr 1 & x_2 & 0 \cr 0 & 0 & x_1 \cr}\right) \succeq 0 \end{eqnarray*} Clearly the possible values of the objective function are all $x_1 > 0$. Thus $v_{\rm primal}=0$, but the supremum is not assumed. \end{example} \subsection{Fundamental properties of semidefinite programs} We could consider minimization instead of maximization. We could allow additional linear contraints on the variables $x_i$ (inequalities and/or equations). These could be incorporated into the form above by extending the $A_i$ and $B$ with new diagonal entries. There is a natural version of the Farkas Lemma: \begin{lemma}\label{SEMIFARKAS}{\rm [Homogeneous version]} Let $A_1,\dots,A_n$ be symmetric $m\times m$ matrices. The system $$ x_1A_1 + \dots x_nA_n\succ 0 $$ has no solution in $x_1,\dots,x_n$ if and only if there exists a symmetric matrix $Y\not= 0$ such that \begin{eqnarray*} A_1\cdot Y &=& 0 \\ A_2\cdot Y &=& 0 \\ &\vdots& \\ A_n\cdot Y &=& 0 \\ Y &\succeq& 0~. \end{eqnarray*} \end{lemma} \begin{lemma}\label{SEMIFARKAS2}{\rm [Inhomogeneous version]} Let $A_1,\dots,A_n,B$ be symmetric $m\times m$ matrices. The system $$ x_1A_1 + \dots x_nA_n - B \succ 0 $$ has a solution in $x_1,\dots,x_n$ if and only if there exists a symmetric matrix $Y\not= 0$ such that \begin{eqnarray*} A_1\cdot Y &=& 0 \\ A_2\cdot Y &=& 0 \\ &\vdots& \\ A_n\cdot Y &=& 0 \\ B\cdot Y &\ge& 0 \\ Y &\succeq& 0~. \end{eqnarray*} \end{lemma} Given a semidefinite program (\ref{SEMIDEF}), one can formulate the {\it dual program}: \begin{eqnarray}\label{SEMIDEF2} \hbox{maximize~} &&B\cdot Y \nonumber\\ \hbox{subject to~}&&\cases{ A_1\cdot Y = c_1 &\cr A_2\cdot Y = c_2 &\cr \vdots &\cr A_n\cdot Y = c_m &\cr Y \succeq 0. &\cr} \end{eqnarray} Note that this too is a semidefinite program in the general sense. We denote by $v_{\rm dual}$ the infimum of the objective function. With this notion of duality, the Duality theorem holds in the following sense (see e.g. \cite{Wol,Vande}): \begin{theorem} Assume that both the primal and the dual semidefinite pograms have feasible solutions. Then $v_{\rm primal}\le v_{\rm dual}$. If, in addition, the primal program (say) has a strictly feasible solution (i.e., the matrix constrained to be positive semidefinite is positive definite for this solution), then the dual optimum is attained and $v_{\rm primal}= v_{\rm dual}$. In particular, if both programs have strictly feasible solutions, then the supremum resp.~infimum of the objective functions are attained. \end{theorem} Furthermore, we have the following {\it complementary slackness conditions}: \begin{prop} Let $x$ be a feasible solution of the primal program and $Y$, a feasible solution of the dual program. Then $v_{\rm primal}= v_{\rm dual}$ and both $x$ and $Y$ are optimal solutions if and only if $Y(\sum_ix_iA_i-B)=0$. \end{prop} \begin{example}\rm Consider the semidefinite program \begin{eqnarray*} \hbox{minimize} && x_1 \\ \hbox{subject to} && \left(\matrix{0 & x_1 & 0 \cr x_1 & x_2 & 0 \cr 0 & 0 & x_1+1 \cr}\right) \succeq 0 \end{eqnarray*} The feasible solutions are $x_1=0$, $x_2\ge 0$. Hence $v_{\rm primal}$ is assumed and is equal to $0$. The dual program is \begin{eqnarray*} \hbox{maximize} &&-Y_{33} \\ \hbox{subject to} && Y_{12}+Y_{21}+Y_{33} = 1 \\ && Y_{22}=0 \\ && Y\succeq 0~. \end{eqnarray*} The feasible solutions are all matrices of the form $$ \left(\matrix{a & 0 & b \cr 0 & 0 & 0 \cr b & 0 & 1 \cr}\right) $$ where $a\ge b^2$. Hence $v_{\rm dual}=-1$. \end{example} \subsection{Algorithms for semidefinite programs I: the ellipsoid method} One can test if a symmetric matrix $A$ is positive semidefinite using the following algorithm: \smallskip \noindent {\bf Algorithm.} Carry out Gaussian elimination on $A$, pivoting always on diagonal entries. If you ever find a negative diagonal entry, stop: the matrix is not positive semidefinite. Else, the matrix is positive semidefinite. \smallskip \noindent {\bf Supplement.} Assume that the $i$-th diagonal entry of the matrix $A^{(k)}$ after $k$ steps is is negative. Write $A^{(k)}=E_k\T\dots E_1\T A E_1\dots E_k$, where $E_i$ are elementary matrices. Then the vector $v=E_1\dots E_ke_i$ satisfies $v\T Av <0$. \smallskip Let $K$ be a convex body (closed, compact, convex set) in $\R^N$. We set $S(K,t)=\{x\in\R^N:~d(x,K)\le t\}$, where $d$ denotes euclidean distance. Thus $S(0,t)$ is the ball woth radius $t$ about $0$. A {\it (strong) separation oracle} for a convex body $K\subseteq\R^N$ is an oracle whose input is a rational vector $x\in\R^N$, and which either asserts that $x\in K$ or returns a vector $y\in\R^N$ such that $y\T x >y\T z$ for all $z\in K$. \begin{theorem}{\rm \cite{GLS4}} Let $K$ be a convex body in $\R^n$ and assume that we know two real numbers $R>r>0$ such that $S(0,r)\subseteq K\subseteq S(0,R)$. Assume that we have a separation oracle for $K$. Let a (rational) vector $c\in \R^N$ and an error bound $0<\varepsilon<1$ be also given. Then we can compute a (rational) vector $x\in\R^N$ such that $x\in K$ and $c\T x \ge c^T z - \varepsilon $ for every $y\in K$. The number of calls on the oracle and the number of arithmetic operations in the algorithm is polynomial in $\log(R/r)+\log(1/\varepsilon )+N$. \end{theorem} Applying this to semidefinite programs, we get \begin{corollary} {\rm \cite{GLS1} } Assume that we are given a semidefinite program (\ref{SEMIDEF}) with rational coefficients and an $\varepsilon >0$. Also assume that we know a rational strictly feasible solution $x_0$. Then one can compute, in time polynomial in $\log(1/\varepsilon )$ and in the number of digits in the coefficients and in $x_0$, a feasible solution $x$ such that the value of the objective function is at most $v_{\rm primal}+\varepsilon $. \end{corollary} \subsection{Algorithms for semidefinite programs II: interior point methods} Semidefinite programs can be solved in polynomial time and also {\it practically efficiently} by interior point methods \cite{Ov,Ali1,Ali2,NN1}. The key is the following fact: \begin{prop} The function $$ F(x)=-\log{\rm det~}(\sum_i x_iA_i -B) $$ is convex and analytic in the interior of the feasible domain of (\ref{SEMIDEF}), and tends to $\infty$ at the boundary. \end{prop} This lemma guarantees that $F(x)$ can serve as a ``barrier function''. The algorithm can be described very informally as follows: Minimize the convex function $F(x)+K c\T x$ using Newton's method, while gradually increasing $K$. See \cite{Vande} for details. \section{Getting semidefinite programs I: spectra of graphs}\label{EIGEN} \subsection{Eigenvalue bounds and the method of variables} Let $G=(V,E)$ be a graph. We denote by $\overline{G}=(V,\overline{E})$ its complement and set $\Delta=\{ii:~i\in V\}$. The adjacency matrix $A_G$ of $G$ is defined by $$ (A_G)_{ij} = \cases{1,& if $ij\in E$,\cr 0,& if $ij\in\overline{E}\cup\Delta$.\cr} $$ Let $\lambda_1\ge \dots\ge \lambda_n$ be the eigenvalues of $A_G$. If $G$ is $d$-regular that trivially $\lambda_1=d$. Since the trace of $A_G$ is $0$, we have $\lambda_1+\dots+\lambda_n=0$, and hence if $e\not=\emptyset$ then $\lambda_1>0$ but $\lambda_n<0$. There are many useful connections between the eigenvalues of a graph and its combinatorial properties. \begin{prop}\label{CLIQUESPEC} The maximum size $\omega(G)$ of a clique in $G$ is at most $\lambda_1-1$. This bound remains valid even if we replace the non-diagonal $0$'s in the adjacency matrix by arbitrary real numbers. \end{prop} \begin{prop}\label{CHROMATIC} {\rm (Hoffman)} The chromatic number $\chi(G)$ of $G$ is at least $1-(\lambda_1/\lambda_n)$. This bound remains valid even if we replace the $1$'s in the adjacency matrix by arbitrary real numbers. \end{prop} \begin{prop}\label{MAXCUT} {\rm \cite{DP1,DP2,MP,PR}} The maximum size $\gamma(G)$ of a cut in $G$ is at most $|E|/2-(n/4)\lambda_n$. This bound remains valid even if we replace the diagonal $0$'s in the adjacency matrix by arbitrary real numbers. \end{prop} Observation: to determine the best choice of real numbers in \ref{CLIQUESPEC}, \ref{CHROMATIC} and \ref{MAXCUT} takes a semidefinite program. The programs for \ref{CLIQUESPEC} and \ref{CHROMATIC} are dual to each other. Their common optimum value is denoted by $\vartheta(G)$ (see later). The program for \ref{MAXCUT} gives the approximation used by Goemans and Williamson (for the case when all weights are $1$). See \cite{Kah} for a similar method to obtain an improved bound on the mixing rate of random walks. \subsection{Rank maximization} Let $G$ be a bipartite graph and let $B_G$ denote its (non-symmetric) adjacency matrix in the bipartite sense. Let $\mu (G)$ denote the maximum size of a matching in $G$. Then \begin{prop}\label{MATCHING}{\rm [Frobenius, K\"onig, Mirsky and Perfect]} We have $\mu (G)\ge \rk(B_G)$. This bound remains valid if we replace the $1$'s in $B_G$ by arbitrary real numbers. For almost all choices of these numbers equality holds. \end{prop} Many other problems in graph theory, matroid theory, electrical engineering, static etc. can be formulated as maximizing the rank of a matrix in which every entry is a linear function of certain variables (see \cite{Recs,LL4}). Such problems can be solved by an obvious polynomial time randomized algorithm. It is not known whether they can be solved in deterministic polynomial time. \section{Getting semidefinite programs II: geometric representations} \label{GEOM} \subsection{Unit distance graphs} A {\it unit distance representation} of a graph $G=(V,E)$ is a mapping $u:~V\to\R^d$ for some $d\ge 1$ such that $|u_i-u_j|=1$ for every $ij\in E$ (we allow that $|u_i-u_j|=1$ for some $ij\in\overline{E}$). Question: what is the smallest radius of a ball containing a unit distance representation of $G$ (in any dimension)? \begin{prop} A graph $G$ has a unit distance representation in a ball of radius $R$ (in some dimension $d$) if and only if if there exists a positive semidefinite matrix $A$ such that \begin{eqnarray*} A_{ii}&\le& R^2 \quad (i\in V)\\ A_{ii}-2A{ij}+A_{jj} &=& 1 \quad (ij\in E). \end{eqnarray*} In other words, the least $R$ is the square root of the optimum value of the semidefinite program \begin{eqnarray*} \hbox{\rm minimize }&& t \\ \hbox{\rm subject to }&& A_{ii}\le t \quad (i\in V) \\ && A_{ii}-2A{ij}+A_{jj} = 1 \quad (ij\in E). \end{eqnarray*} \end{prop} \subsection{Orthogonal representations} An {\it orthogonal representation} of a graph $G=(V,E)$ is a mapping (labelling) $u:~V\to\R^d$ for some $d$ such that $u_i\T u_j=0$ for all $ij\in \overline{E}$. An {\it orthonormal representation} is an orthogonal representation with $|u_i|=1$ for all $i$. The {\it angle} of an orthonormal representation is the smallest half-angle of a rotational cone containing the representing vectors. \begin{prop}\label{THETAANGLE} The minimum angle $\phi$ of any orthogonal representation of $G$ is given by $\cos^2\phi= 1/\vartheta(G)$. \end{prop} Let the {\it leaning} of an orthonormal representation of $G$ be definied as $\sum_{i\in V} (e_1\T u_i)^2$. \begin{prop}\label{THETALEANING} The maximum leaning of an orthonormal representation of $G$ is $\vartheta(\overline{G})$. \end{prop} The ``umbrella'' construction given in the introduction shows, by Proposition \ref{THETAANGLE}, that $\vartheta(C_5) \le \sqrt{5}$, and by Proposition \ref{THETALEANING}, that $\vartheta(\overline{C_5}) \ge \sqrt{5}$. Hence $\vartheta(C_5) = \sqrt{5}$. \subsection{Properties of $\vartheta$} We collect some properties of $\vartheta$, mostly from \cite{LL2}. See also \cite{Kn} for a survey. \begin{prop}{\rm [Sandwich Theorem]} For every graph $G$, $$ \omega(G)\le\vartheta(\overline{G})\le \chi(G). $$ \end{prop} For an application of this result to complexity theory, see \cite{Tar}. The {\it fractional chromatic number} $\chi^*(G)$ is defined as the least $t$ for which there exists a family $\{A_j:~j=1,\dots,p\}$ of stable sets in $G$, and non-negative weights $\{\tau_j:~j=1,\dots,p\}$ such that $\sum\{\tau_j:~A_j\ni i\}\ge 1$ for all $i\in V$ and $\sum_j\tau_j= t$. By linear programming duality, $\chi^*(G)$ is equal to the largest $s$ for which there exist weights $\{\sigma_i:~i\in V\}$ such that $\sum_{i\in A} \sigma_i \le 1$ for every stable set $A$ and $\sum_i\sigma_i=s$. Clearly $\omega(G)\le\chi^*(G)\le\chi(G)$. \begin{prop} $$\vartheta(G)\le\chi^*(\overline{G}).$$ \end{prop} \begin{prop}\label{DIMTHETA} Suppose that $G$ has an orthonormal representation in dimension $d$. Then $\vartheta(G)\le d$. \end{prop} \begin{prop} For any two graphs, $$ \vartheta(G\cdot H)=\vartheta(G)\vartheta(H) $$ and $$ \vartheta(\overline{G\cdot H}) = \vartheta(\overline{G})\vartheta(\overline{H}) . $$ \end{prop} \begin{corollary}\label{THETABOUND} For every graph, $$\Theta(G)\le \vartheta(G).$$ \end{corollary} \begin{prop} For every graph $G$, $$ \vartheta(G)\vartheta(\overline{G}) \ge n. $$ If $G$ has a vertex-transitive automorphism group, then equality holds. \end{prop} \begin{corollary} If $G$ is a self-complementary graph on $n$ nodes with a node-transitive automorphism group, then $$ \Theta(G)=\vartheta(G)=\sqrt{n}. $$ \end{corollary} \begin{theorem}{\rm (Juh\'asz \cite{Juh})} If $G$ is a random graph on $n$ nodes then $\vartheta(G)/\sqrt{n}\to 1$ with probability $1$ as $n\to\infty$. \end{theorem} \subsection{Applications of $\vartheta$ in approximation algorithms} Negative results: Koniagin \cite{Kon} showed that a graph can have $\alpha(G)=2$ and $\vartheta(G)=\Omega(n^{1/3})$. Feige \cite{Fe} showed that $\vartheta/\alpha$ can be larger than $n^{1-\varepsilon}$ for every $\varepsilon>0$. By results of Szegedy \cite{Sze}, this also implies that $\vartheta(\overline{G})$ does not approximate the chromatic number within a factor of $n^{1-\varepsilon}$. Karger, Motwani and Sudan \cite{KMS} gave a polynomial time algorithm that, given a 3-colorable graph, computes a coloring with $n^{1/4}$ colors. The method is based on $\vartheta(G)$ and is similar to the method of Goemans and Williamson. \subsection{Minimum dimension representations} From a geometric point of view, it is more natural to consider unit distance (orthogonal, etc.) representations in a fixed small dimension. Little is known. A vector labelling $V\to \R^d$ is {\it generic} if any $d$ labels are linearly independent. \begin{theorem}{\rm \cite{LSS}}\label{ORTHOGENERIC} The minimum dimension in which a graph $G$ has a generic orthogonal labelling is $n-k$, where $k$ is the node-connectivity of $G$. \end{theorem} \subsection{Other representations} Several other geometric representations of graphs are connected to interesting graph-theoretic properties, and several of these are related to semidefinite optimization. This connection is largely unexplored. Just some pointers: Tutte \cite{Tu} proved that a straight-line embedding in the plane of any 3-connected planar graph can be obtained by fixing the vertices of a face to the vertices of a convex polygon, replacing the edges by "rubber bands", and let the other nodes find their equilibrium (this translates into minimizing an appropriate convex quadratic objective function). Tutte's construction is used in many graph drawing programs. A similar construction was used by Linial, Lov\'asz and Wigderson \cite{LLW} to characterize $k$-connectivity of a graph, and to design an efficient randomized $k$-connectivity test. Colin de Verdi\`ere \cite{CV1,CV2,CV3} introduced an interesting spectral invariant of graphs that is related to topological properties. Kotlov, Lov\'asz and Vempala (unpublished) showed that this invariant can be defined in terms of the minimum dimension in which the graph admits a vector labelling such that the inner product of vectors assigned to adjacent nodes is $1$, the inner product of vectors assigned to non-adjacent nodes is less than $1$, and a certain ``genericity'' condition similar to that in theorem \ref{ORTHOGENERIC} (but more complicated) is satisfied. Such labellings, in turn, are related to a classical result of Koebe \cite{Ko} (see also \cite{And,Thu,Sch}, asserting that every planar graph can be represented in the plane by touching circular disks. \section{The stable set polytope}\label{STABLE} We recall some results on the stable set polytope. A detailed account can be found e.g. in Gr\"otschel, Lov\'asz and Schrijver (1988). Let $G=(V,E)$ be a graph without isolated nodes. For every subset $S\subseteq V$, let $\chi ^S\in \R^V$ denote its incidence vector, i.e., the vector defined by $$\chi ^S_i=\cases{1, & if $i\in S$, \cr 0, & otherwise, \cr}$$ The {\it stable set polytope} $\STAB(G)$ of $G$ is the convex hull of incidence vectors of all stable sets. \subsection{Facets} Linear inequalities valid for the stable set polytope: \medskip \noindent {\sc Non-negativity constraints}: \begin{equation}\label{NON-NEG} x_i\ge 0\quad (i\in V). \end{equation} \noindent {\sc Edge constraints}: \begin{equation}\label{EDGE} x_i+x_j \le 1\quad (ij \in E). \end{equation} These inequalities define a polytope $\FRAC(G)$, which is in general larger than $\STAB(G)$. \begin{prop}\label{FRAC} {\rm (a)} $\STAB(G)=\FRAC(G)$ iff $G$ is bipartite. {\rm (b)} The vertices of $\FRAC(G)$ are half-integral. \end{prop} \noindent {\sc Clique constraints}: \begin{equation}\label{CLIQUE} \sum_{i\in B} x_i \le 1, \quad \hbox{where $B$ is a clique.} \end{equation} Inequalities (\ref{NON-NEG}) and (\ref{CLIQUE}) define a polytope $\QSTAB(G)$, which is in general larger than $\STAB(G)$. A {\it convex corner} in $\R^V$ is a full-dimensional, compact, convex set $P$ such that $x\in P$, $0\le y\le x$ implies $y\in P$. The {\it antiblocker} of a convex corner $P$ is defined as $P^*=\{x\in\R_+^V:~x\T y \le 1 \hbox{ for all }y\in P\}$. $P^*$ is a convex corner and $P^{**}=P$. \begin{prop}\label{STABDUAL} For every graph $G$, $$ \QSTAB(G)=\STAB(\overline{G})^*. $$ \end{prop} A graph $G$ is called {\it perfect} if $\chi(G')=\omega(G')$ for every induced subgraph $G'$ of $G$. If $G$ is perfect then so is $\overline{G}$ \cite{LL0}. See \cite{Gol,GLS4,LL3} for the theory of perfect graphs. \begin{theorem}\label{PERFECT}{\rm [Fulkerson--Chvatal]} Inequalities {\rm (\ref{NON-NEG})} and {\rm (\ref{CLIQUE})} suffice to describe $\STAB(G)$ iff $G$ is perfect. \end{theorem} \noindent {\sc Odd hole constraints:} \begin{equation}\label{ODD-HOLE} \sum_{i\in B} x_i \le {|C|-1\over 2}, \quad \hbox{where $B$ induces a cordless odd cycle.} \end{equation} A graph is called {\it t-perfect} if (\ref{NON-NEG}), (\ref{EDGE}) and (\ref{ODD-HOLE}) suffice to describe $\STAB(G)$, and {\it h-perfect} if (\ref{NON-NEG}), (\ref{CLIQUE}) and (\ref{ODD-HOLE}) suffice to describe $\STAB(G)$. \noindent {\sc Odd antihole constraints:} \begin{equation}\label{ANTIHOLE} \sum_{i\in B} x_i \le 2, \quad \hbox{where $B$ induces the complement of a cordless odd cycle.} \end{equation} All these inequalities are facets if $B=V$, and in many other cases. If there are nodes not occurring in the inequality then they may sometimes be added to the constraint with non-zero coefficient; this is called {\it lifting}. \begin{theorem}\label{CRITICAL}{\rm [Chv\`atal]} Let $G=(V,E)$ be an $\alpha $-critical graph. Then the inequality $\sum_{i\in V} x_i \le \alpha (G)$ defines a facet of $\STAB(G)$. \end{theorem} Let $\sum_i a_ix_i\le b$ be an inequality defining a facet of $\STAB(G)$. We define its {\it Gallai class number} as $\sum_i a_i -2b$. The Gallai class number of an odd hole contraint is $1$; the Gallai class number of a clique constraint (\ref{CLIQUE}) is $|B|-2$. In the case of a facet defined by an $\alpha $-critical graph $G$, this value is $\delta(G)=|V(G)|-2\alpha (G)$, introduced by Gallai. \begin{lemma}\label{GALLAI}{\rm [Lov\'asz--Schrijver]} Let $\sum_i a_ix_i \le b$ be a facet of $\STAB(G)$. Then $$ \max\left\{\sum_ia_ix_i:\ x\in \FRAC(G)\right\} = {1\over 2}\sum_i a_i. $$ \end{lemma} \begin{corollary} The Gallai class number of a facet $\sum_i a_ix_i \le b$ is twice the ``integrality gap'' between optimizing the left hand side over $\FRAC(G)$ and $\STAB(G)$. More exactly, \begin{eqnarray*} \sum_i a_i - 2b &=& 2\max\left\{\sum_i a_ix_i:\ x\in \FRAC(G)\right\} \\ &-& 2 \max\left\{\sum_ia_ix_i:\ x\in\STAB(G)\right\}. \end{eqnarray*} \end{corollary} \subsection{Orthogonality constraints} For every orthonormal representation $(u_i:~i\in V)$, consider the vector $x[u]=(e_1\T u_i)^2:~i\in V)\in\R^V$. Let $\THETA(B)$ denote the set of all vectors $x[u]$. \begin{theorem}{\rm \cite{GLS3}} {\rm (a)} $\THETA(G)$ is a convex corner in $\R^V$. \smallskip {\rm (b)} $\STAB(G)\subseteq \THETA(G) \subseteq \QSTAB(G)$. \smallskip {\rm (c)} Every vector in $\THETA(G)$ satisfies all the clique constraints. \smallskip {\rm (d)} $\THETA(G)$ is defined by the (infinitely many) linear constraints \begin{equation}\label{ORTHOGONAL} \sum_{i\in V} (e_1\T v_i)^2x_i \le 1, \end{equation} where $(v_i:~i\in V)$ ranges over all orthonormal representations of $\overline{G}$. \smallskip {\rm (e)} $\THETA(\overline{G})$ is the antiblocker of $\THETA(G)$. \smallskip {\rm (f)} $\THETA(G)$ is polyhedral if and only if the graph is perfect. \smallskip {\rm (g)} Every linear objective function can be maximized over $\THETA(G)$ (with arbitrary small error) in polynomial time. \end{theorem} By (b) and (d), the inequalities (\ref{ORTHOGONAL}) are linear constraints valid for $\STAB(G)$, called {\it orthogonality constraints}. Every clique constraint is an orthogonality constraint. No other orthogonality constraint defines a facet of $\STAB(G)$ (not even of $\THETA(G)$. \section{Getting semidefinite programs III: Quadratic inequalities.} \label{QUAD} Consider a typical 0-1 optimization problem: \begin{eqnarray}\label{01PROG} \hbox{maximize~} &&c^tx\\ \hbox{subject to~}&&\cases{Ax\le b &\cr x \in \{0,1\}^n.&\cr} \end{eqnarray} We get an equivalent problem if we replace the last constraint by \begin{equation}\label{ZERO-ONE} x_i^2=x_i \qquad(i=1,\dots,n). \end{equation} Let $G=(V,E)$ be a graph with $V=\{1,\dots,n\}$ and consider the following system of equations: \begin{equation}\label{EDGEQUAD} x_ix_j=0\qquad (ij\in E) \end{equation} Trivially, the solutions of (\ref{ZERO-ONE}) and (\ref{EDGEQUAD}) are precisely the incidence vectors of stable sets. Unfortunately, this shows is that even the solvability of such a simple system of quadratic equations (together with a linear equation $\sum_ix_i=\alpha $) is NP-hard. However, we can use this system to derive some other constraints (\cite{LS1,LS2}; see also \cite{LL5}). (\ref{ZERO-ONE}) implies that for every node $i$, $$ x_i=x_i^2\ge 0,\quad 1-x_i=(1-x_i)^2\ge 0 $$ and using this (\ref{EDGEQUAD}) implies the edge constraints for every edge $ij$: \begin{equation}\label{EDGELIN2} 1-x_i-x_j=1-x_i-x_j+x_ix_j=(1-x_i)(1-x_j)\ge 0. \end{equation} Consider e.g. a pentagon $(1,2,3,4,5)$. Then we have $$ 1-x_1-x_2-x_3+x_1x_3= 1-x_1-x_2-x_3+x_1x_2+x_1x_3= (1-x_1)(1-x_2-x_3)\ge 0, $$ and similarly $$ 1-x_1-x_4-x_5+x_1x_4\ge 0. $$ Furthermore, $$ x_1-x_1x_3-x_1x_4=x_1(1-x_3-x_4)\ge 0 $$ Summing these inequalities, we get the odd hole constraint \begin{equation}\label{ODDHOLE2} 2-x_1-x_2-x_3-x_4-x_5\ge 0. \end{equation} We can also derive the clique constraints. Assume that nodes 1,2,3,4,5 induce a complete 5-graph. Then \begin{eqnarray*} 0 &\le& (1-x_1-x_2-x_3-x_4-x_5)^2 = 1+\sum_{i=1}^5 x_i^2 -2 \sum_{i=1}^5 x_i+2 \sum_{i\not=j} x_ix_j \\ &=& 1-x_1-x_2-x_3-x_4-x_5, \end{eqnarray*} by (\ref{ZERO-ONE}) and (\ref{EDGEQUAD}). \subsection{Strong insolvability of quadratic equations} \begin{lemma}\label{SINGLEQUAD} We can decide whether a single quadratic inequality is solvable in polynomial time. \end{lemma} A system of quadratic inequalities is {\it strongly unsolvable} if there is an unsolvable quadratic inequality that can be obtained as a linear combination of the given inequalities. By the Farkas Lemma, the analogous condition for the solvability of a system of linear inequalities is necessary and sufficient. In the quadratic case, there are unsolvable but not strongly unsolvable systems. \begin{theorem}\label{STRONG-UNSOLVE} It is decidable in polynomial time whether a system of quadratic inequalities is strongly unsolvable. \end{theorem} An {\it inference rule} for algebraic inequalities is a procedure that, given a system $\alpha_1\ge 0,\dots, \alpha_m\ge 0$ of algebraic inequalities in $n$ variables, determines a new algebraic inequality $\alpha\ge 0$, which is a {\it logical consequence} of the given system in the sense that every vector $x\in\R^n$ satisfying $\alpha_1(x)\ge 0,\dots,\alpha_m(x)\ge 0$ also satisfies $\alpha(x)\ge 0$. \smallskip \noindent {\sc Linear combination rule}: $$ ({\bf R}_0):~ \alpha_1\ge 0,\dots,\alpha_m\ge 0 \Longrightarrow c_0+c_1\alpha_1+\dots c_m\alpha_m\ge 0 \quad (c_0,c_1,\dots,c_m\ge 0). $$ The Farkas Lemma asserts that among {\it linear} inequalities, this single rule generates {\it all} logical consequences. \noindent {\sc Multiplication rule}: $$ ({\bf R}_1):~ \alpha_1\ge 0,\alpha_2\ge 0 \Longrightarrow \alpha_1\alpha_2\ge 0. $$ Assume that the linear inequalities $0\le x_i\le 1$ as well as the quadratic equations $x_i^2=x_i$ are present. Under this assumption, one can formulate the following restricted version of $({\bf R}_1)$: $$ ({\bf R}'_1):~ \alpha\ge 0 \Longrightarrow x_i\alpha\ge 0, (1-x_i)\alpha\ge 0. $$ \noindent {\sc Semidefinite rule}: $$ ({\bf R}_2):~ \alpha\ge 0\ge 0 \Longrightarrow \alpha+\beta_1^2+\dots+\beta_m^2\ge 0 $$ (where the $\beta_i$ are arbitrary polynomials). We can consider the {\it restricted version} where all the $\beta_i$ are linear. \noindent {\sc Division rule}: $$ ({\bf R}_3):~ \alpha_1\ge 0,~(1+\alpha_1)\alpha_2\ge 0 \Longrightarrow \alpha_2\ge 0. $$ \begin{theorem}{\rm (Lov\'asz and Schrijver \cite{LS1,LS2})} Starting with any system of linear inequalities, repeated application of rules $({\bf R}_0)$ and $({\bf R}'_1)$ generates all {\it linear} inequalities valid for the 0-1 solutions, in at most $n$ steps. \end{theorem} \begin{theorem}{\rm \cite{LS1,LS2}} Let $G$ any graph, and let $F$ be a facet of $\STAB(G)$ with Gallai class number $\delta$. Starting with the non-negativity constraints {\rm (\ref{NON-NEG})} and the edge constraints {\rm (\ref{EDGE})}, the facet $F$ can be derived, using rules $({\bf R}_0)$ and $({\bf R}'_1)$, in at most $\delta$ steps. \end{theorem} If we also use rule $({\bf R}_2)$, then the deriviation may be much faster. It seems that all the known ``nice'' (polynomially separable, see below) classes of facets of the stable set polytope, with the possible exception of the "Edmonds facets" in the case of the matching polytope, can be derived by one or two rounds of applications of (${\bf R_0}$), (${\bf R}'_1$), and (${\bf R}_2$). This implies the polynomial time solvability of the Maximum Weight Stable Set Problem for a rather broad class of graphs. Let $G=(V,E)$ be a graph and let $I(G)$ denote the polynomial ideal generated by the polynomials $x_i^2-x_i$ ($i\in V$) and $x_ix_j$ ($ij\in E$). Obviously, the roots of this ideal are the incidence vectors of stable sets. We write $f\ge 0$ (mod $I(G)$) iff $f(x)\ge 0$ for every root of the ideal $I(G)$. \begin{theorem}{\rm [Artin's theorem]} A polynomial $f\in\R[x_1,\dots,x_n]$ is non-negative for all $(x_1,\dots,x_n)\in\R^n$ if and only if it is a sum of squares of rational functions. \end{theorem} \begin{prop} For any polynomial $f$, we have $f\ge 0~(\mod I(G))$ iff there exist polynomials $g_1,\ldots,g_N$ such that $f\equiv g_1^2+\ldots +g_N^2 ~(\mod I(G))$. \end{prop} \begin{theorem} A graph $G$ is perfect if and only if the following holds: For any linear polynomial $f$, we have $f\ge 0~(\mod I(G))$ iff exist linear polynomials $g_1,\ldots,g_N$ such that $f\equiv g_1^2+\ldots + g_N^2~(\mod I(G))$. \end{theorem} \subsection{Algorithmic aspects of inference rules} Let ${\cal L}$ be a possibly infinite system of linear inequalities in $n$ variables, associated to a finite structure (e.g., a graph). We say that ${\cal L}$ is {\it polynomially separable}, if for every vector $x\in\R^n$, we can decide in polynomial time whether $x$ satisfies every member of ${\cal L}$, and if it does not, we can find a violated member. Let ${\bf R}$ be any inference rule, and let ${\bf R}{\cal L}$ denote the set of all linear inequalities produced by one application of ${\bf R}$ to members of ${\cal L}$. We say that the rule is {\it polynomial}, if ${\bf R}{\cal L}$ is polynomially separable whenever ${\cal L}$ is. \begin{lemma} Rules (${\bf R}_0$), (${\bf R}'_1$), and (${\bf R}_2$) are polynomial. \end{lemma} \begin{corollary} The Stable Set Problem can be solved for perfect, $t$-perfect and $h$-perfect graphs in polynomial time. \end{corollary} \begin{corollary} Consider a class of graphs for which every facet of the stable set polytope has Gallai class number at most a constant. Then the Stable Set Problem can be solved polynomially for this class. \end{corollary} \section{Extensions and problems}\label{OPEN} \subsection{Inference rules} Several other rules of inference for quadratic inequalities can be investigated, but little is known. Barvinok \cite{Bar} gives a polynomial time algorithm to decide whether a system of a bounded number of quadratic equations is solvable (over the real field). This suggests a hierarchy of extensions of strong insolvability: produce a fixed number $k$ of quadratic equations by linear combination which are collectively unsolvable. \begin{prob}\rm Can one decide in polynomial time the $k$-th version of strong insolvability? Is this a real hierarchy? Are there any natural problems in higher classes? \end{prob} \begin{prob}\rm Are the product rule $({\bf R}_1)$ and the division rule $({\bf R}_3)$ polynomial? Are they polynomial if we restrict ourselves to quadratic inequalities? Does the division rule have a natural and useful restriction that is polynomial? \end{prob} \begin{prob}\rm Are there other combinatorial optimization problems for which interesting classes of facets can be derived using the division rule? \end{prob} \begin{prob}\rm Are there other rules that are worth considering? Can any interesting discrete programming problem be attacked using polynomials of higher degree? \end{prob} \begin{prob}\rm How to implement rule $({\bf R}'_1)$ efficiently? Is there a way to use interior point methods, in a way parallel to Alizadeh's application of interior point methods to semidefinite programming? \end{prob} \begin{prob}\rm Graphs that are $\alpha$-critical with bounded Gallai class number have a finite classification (Lov\'asz \cite{LL1}). Is there a similar classification of facets of $\STAB(G)$ with bounded Gallai class number? \end{prob} \begin{prob}\rm If a graph $G$ contains no subdivision of $K_4$, then it is series-parallel, and hence $t$-perfect. This means that every facet of $\STAB(G)$ has Gallai class number at most $1$. Is there an analogous simple graph-theoretic condition that guarantees that every facet has Gallai class number at most $2$, $3$, etc.? \end{prob} \subsection{New applications through eigenvalue techniques} \begin{prob}\rm Is there a semidefinite relaxation of the discrepancy problem that provides new insight and/or new methods? \end{prob} (We refer to \cite{BC} and to \cite{BS} for an exposition of combinatorial discrepancy theory, and for the succesful application of eigenvalue techniques in discrepancy estimates going back to K.F.Roth.) \subsection{Approximation algorithms} \begin{prob}\rm Can the randomized ``rounding'' method of Goemans--William\-son and Karger--Motwani--Sudan be generalized to semidefinite relaxations of more general problems? \end{prob} \begin{prob}\rm Can the ratio $\vartheta/\alpha$ be estimated by $n^{1-\varepsilon}$ for special classes of graphs? \end{prob} \begin{prob}\rm Can the extended semidefinite optimization methods be used to obtain a polynomial time approximation algorithm for $\alpha$ with relative error $n^{1-\varepsilon}$? \end{prob} \begin{prob}\rm Is there a polynomial time algorithm that outputs an upper bound $\phi(G)$ for $\alpha(G)$ such that there is a function $f:~\Z_+\to\Z_+$ with $\phi(G)0$ there exists an algorithm that computes $\alpha(G)$ in time $(1+\varepsilon)^n$? \end{prob} \noindent{\bf Acknowledgement.} My thanks are due to Andr\'as Frank for organizing a series of talks on this subject and to my audience for their patience and active participation. I am particularly indepted to Mikl\'os \'Ujv\'ary for pointing out several errors in an earlier version of these notes. \begin{thebibliography}{99} \vskip10pt \bibitem{Ali1} F.~Alizadeh: Combinatorial optimization with semi-definite matrices, in: {\it Integer Programming and Combinatorial Optimization} (Proceedings of IPCO '92), (eds. E. Balas, G. Cornu\'ejols and R. Kannan), Carnegie Mellon University Printing (1992), 385--405. \bibitem{Ali2} F.~Alizadeh: Interior point methods in semidefinite programming with applications to combinatorial optimization, {\it SIAM J. on Optimization} (to appear) %\bibitem{ADLRY} %N.~Alon, R.~A.~Duke, H.~Lefmann, V.~R\"odl and R.~Yuster: The %algorithmic aspects of the Regularity Lemma, {\it Proc. 33rd Annual %Symp. on Found. of Computer Science}, IEEE Computer Society Press (1992), %473--481. \bibitem{Alo} N.~Alon: Explicit Ramsey graphs and orthonormal labelings, {\it The Electronic Journal of Combinatorics} {\bf 1} (1994), 8pp. \bibitem{AK} N.~Alon and N.~Kahale: Approximating the independence number via the $\theta$ function (manuscript, Nov. 1994). \bibitem{And} E.~Andre'ev, On convex polyhedra in Lobachevsky spaces, {\it Mat. Sbornik}, Nov. Ser. {\bf 81} (1970), 445--478. \bibitem{Ar} S.~Arora, C.~Lund, R.~Motwani, M.~Sudan, M.~Szegedy: Proof verification and hardness of approximation problems {\it Proc. 33rd FOCS} (1992), 14--23. \bibitem{Bell} M.~Bellare, O.~Goldreich, M.~Sudan: Free bits, PCPs and non-approximability --- towards tight results, {\it Proc. 36th FOCS} (1996), 422--431. \bibitem{BCV} R.~Bacher and Y.~Colin de Verdi\`ere, Multiplicit\'es de valeurs propres et transformations \'etoile-triangle des graphes, {\it Bull. Soc. Math. France} {\bf 123} (1995), 101-117. \bibitem{Bar} A.~I.~Barvinok: Feasibility testing for systems of real quadratic equations, {\it Discrete and Comp. Geometry} {\bf 10} (1993), 1--13. \bibitem{BC} J.~Beck and W.~Chen: {\it Irregularities of Distribution,} Cambridge Univ. Press (1987). \bibitem{BS} J.~Beck and V.T.~S\'os: Discrepancy Theory, Chapter 26 in: {\it Handbook of Combinatorics} (ed. R.L.~Graham, M.~Gr\"otschel and L.~Lov\'asz), North-Holland, Amsterdam (1995). \bibitem{CV1} Y.~Colin de Verdi\`ere, Sur la multiplicit\'e de la premi\`ere valeur propre non nulle du laplacien, {\it Comment. Math. Helv.} {\bf 61} (1986), 254--270. \bibitem{CV2} Y.~Colin de Verdi\`ere, Sur un novel invariant des graphes at un crit\`ere de planarit\'e, {\it J. Combin. Theory B} {\bf 50} (1990) 11--21. \bibitem{CV3} Y.~Colin de Verdi\`ere, On a new graph invariant and a criterion for planarity, in: {\it Graph Structure Theory} (Robertson and P. D. Seymour, eds.), Contemporary Mathematics, Amer. Math. Soc., Providence, RI (1993), 137--147. \bibitem{DP1} C.~Delorme and S.~Poljak: Combinatorial properties and the complexity of max-cut approximations, {\it Europ. J. Combin.} {\bf 14} (1993), 313--333. \bibitem{DP2} C.~Delorme and S.~Poljak: Laplacian eigenvalues and the maximum cut problem, {\it Math. Programming} {\bf 62} (1993) \bibitem{Fe} U.~Feige (1995): Randomized graph products, chromatic numbers, and the Lov\'asz $\vartheta$-function (manuscript) \bibitem{FL} U.~Feige and L.~Lov\'asz: Two-prover one-round proof systems: Their power and their problems. {\it Proc. 24th ACM Symp. on Theory of Computing} (1992), 733-744. \bibitem{GW1} M.~X.~Goemans and D.~P.~Williamson: .878-Approximation algorithms for MAX CUT and MAX 2SAT, {\it Proc. 26th ACM Symp. on Theory of Computing} (1994), 422-431. \bibitem{GW2} M.~X.~Goemans and D.~P.~Williamson: Improved approximation algorithms for maximum cut and satisfiablity problems using semidefinite programming, {\it J. ACM} (to appear) \bibitem{Gol} M.~C.~Golumbic: {\it Algorithmic Graph Theory and Perfect Graphs}, Academic Press, New York (1980). \bibitem{GLS1} M.~Gr\"otschel, L.~Lov\'asz and A.~Schrijver: The ellipsoid method and its consequences in combinatorial optimization, {\it Combinatorica} {\bf 1} (1981), 169-197. \bibitem{GLS2} M.~Gr\"otschel, L.~Lov\'asz and A.~Schrijver: Polynomial algorithms for perfect graphs, {\it Annals of Discrete Math.} {\bf 21} (1984), 325-256. \bibitem{GLS3} M.~Gr\"otschel, L.~Lov\'asz and A.~Schrijver: Relaxations of vertex packing, {\it J. Combin. Theory B} {\bf 40} (1986), 330-343. \bibitem{GLS4} M.~Gr\"otschel, L.~Lov\'asz and A.~Schrijver: {\it Geometric Algorithms and Combinatorial Optimization}, Springer, Heidelberg, 1988. \bibitem{HH} H.~van der Holst, A short proof of the planarity characterization of Colin de Verdi\`ere, Preprint, CWI Amsterdam, 1994. \bibitem{HLS} H.~van der Holst, L.~Lov\'asz and A.~Schrijver: On the invariance of Colin de Verdi\`ere's graph parameter under clique sums, {\it Linear Algebra and its Applications}, {\bf 226--228} (1995), 509--518. \bibitem{Juh} F.~Juh\'asz: The asymptotic behaviour of Lov\'asz' $\vartheta$ function for random graphs, {\it Combinatorica} {\bf 2} (1982) 153--155. \bibitem{Kah} N.~Kahale: A semidefinite bound for mixing rates of Markov chains, DIMACS Tech. Report No. 95-41. \bibitem{KMS} D.~Karger, R.~Motwani, M.~Sudan: Approximate graph coloring by semidefinite programming, {\it Proc. 35th FOCS} (1994), 2--13. \bibitem{KK} B.~S.~Kashin and S.~V.~Konyagin: On systems of vectors in Hilbert spaces, {\it Trudy Mat. Inst. V.A.Steklova} {\bf 157} (1981), 64--67; English translation: {\it Proc. of the Steklov Inst. of Math.} (AMS 1983), 67--70. \bibitem{Kon} V.~S.~Konyagin, Systems of vectors in Euclidean space and an extremal problem for polynomials, {\it Mat. Zametky} {\bf 29} (1981), 63--74. English translation: {\it math. Notes of the Academy USSR} {\bf 29} (1981), 33--39. \bibitem{Kn} D.~E.~Knuth: The sandwich theorem, {\it The Electronic Journal of Combinatorics} {\bf 1} (1994) 48 pp. \bibitem{Ko} P.~Koebe, Kontaktprobleme der konformen Abbildung, {\it Berichte uber die Verhandlungen d. S\"achs. Akad. d. Wiss.}, Math.--Phys. Klasse, {\bf 88} (1936) 141--164. \bibitem{LLW} N.~Linial, L.~Lov\'asz, A.~Wigderson: Rubber bands, convex embeddings, and graph connectivity, {\it Combinatorica} {\bf 8} (1988), 91--102. \bibitem{LL0} L.~Lov\'asz: Normal hypergraphs and the perfect graph conjecture, {\it Discrete Math.} {\bf 2} (1972), 253-267. \bibitem{LL1} L.~Lov\'asz: Some finite basis theorems in graph theory, in: {\it Combinatorics}, Coll. Math. Soc. J. Bolyai {\bf 18} (1978), 717-729. \bibitem{LL2} L.~Lov\'asz: On the Shannon capacity of graphs, {\it IEEE Trans. Inform. Theory} {\bf 25} (1979), 1--7. \bibitem{LL3} L.~Lov\'asz: Perfect graphs, in: {\it More Selected Topics in Graph Theory} (ed. L. W. Beineke, R. L. Wilson), Academic Press (1983), 55-67. \bibitem{LL4} L.~Lov\'asz: Singular spaces of matrices and their applications in combinatorics, {\it Bol. Soc. Braz. Mat.} {\bf 20} (1989), 87--99. \bibitem{LL5} L.~Lov\'asz: Stable sets and polynomials, {\it Discrete Math.} {\bf 124} (1994), 137--153. \bibitem{LSS} L.~Lov\'asz, M.~Saks, A.~Schrijver: Orthogonal representations and connectivity of graphs, {\it Linear Alg. Appl.} {\bf 114/115} (1989), 439--454. \bibitem{LS1} L.~Lov\'asz and A.~Schrijver: Cones of matrices and set-functions, and 0-1 optimization, {\it SIAM J. on Optimization} {\bf 1} (1990), 166-190. \bibitem{LS2} L.~Lov\'asz and A.~Schrijver: Matrix cones, projection representations, and stable set polyhedra, in: {\it Polyhedral Combinatorics}, DIMACS Series in Discrete Mathematics and Theoretical Computer Science I, Amer. Math. Soc., Providence (1990), 1--17. \bibitem{MP} B.~Mohar and S.~Poljak: Eigenvalues and the max-cut problem, {\it Czechoslovak Mathematical Journal} {\bf 40} (1990), 343--352. \bibitem{NN1} Yu.~E.~Nesterov and A.~Nemirovsky: {\it Interior-point polynomial methods in convex programming,} Studies in Appl. Math. {\bf 13}, SIAM, Philadelphia, 1994. \bibitem{Ov} M.~L.~Overton: On minimizing the maximum eigenvalue of a symmetric matrix, {\it SIAM J. on Matrix Analysis and Appl.} {\bf 9} (1988), 256--268. \bibitem{OW} M.~L.~Overton and R.~Womersley: On the sum of the largest eigenvalues of a symmetric matrix, {\it SIAM J. on Matrix Analysis and Appl.} {\bf 13} (1992), 41--45. \bibitem{PR} S.~Poljak and F.~Rendl: Nonpolyhedral relaxations of graph-bisection problems, DIMACS Tech. Report 92-55 (1992). \bibitem{Recs} A.~Recski: {\it Matroid Theory and its Applications in Electric Network Theory and Statics}, Akad\'emiai Kiad\'o--Springer-Verlag (1989). \bibitem{Sch} O.~Schramm: How to cage an egg, {\it Invent. Math.} {\bf 107} (1992), 543--560. \bibitem{Sze} M.~Szegedy: A note on the $\theta$ number of Lov\'asz and the generalized Delsarte bound, {\it Proc. 35th FOCS} (1994), 36--39. \bibitem{Tar} \'E.~Tardos: The gap between monotone and non-monotone circuit complexity is exponential, {\it Combinatorica} {\bf 8} (1988), 141--142. \bibitem{Thu} W.~Thurston: {\it The Geometry and Topology of Three-manifolds}, Princeton Lecture Notes, Chapter 13, Princeton, 1985. \bibitem{Tu} W.T.~Tutte: How to draw a graph, {\it Proc. London Math. Soc.} {\bf 13} (1963), 743-768. \bibitem{Vande} L.~Vandeberghe and S.~Boyd: Semidefinite programming, in: {\it Math. Programming: State of the Art} (ed. J.~R.~Birge and K.~G.~Murty), Univ. of Michigan, 1994; revised preprint, 1995. \bibitem{Wol} H.~Wolkowitz: Some applications of optimization in matrix theory, {\it Linear Algebra and its Applications} {\bf 40} (1981), 101--118. \end{thebibliography} \end{document}