A vector $r$-coloring ($r>1$) of a graph $G=([n],E)$ is an assignment of unit vectors $v_1,\ldots,v_n$ in $R^n$ to the vertices of $G$ such that $\{i,j\}\in E$ implies that the dot product $\langle v_i,v_j \rangle = -1/(r-1)$. Consider the function \[ \bar{\vartheta}(G):=\vartheta(\overline{G}) \] whose value is the Lovász capacity of the complement of $G$.
In this paper paper, Karger, Motwani and Sudan have proved the following theorem (Theorem 8.1 in the paper).
Theorem: $\bar{\vartheta}(G)$ is exactly the minimum real number $r$ for which $G$ has a vector $r$-coloring.By this theorem, the monotonicity of the function $\bar{\vartheta}(G)$ is obvious: by removing an edge, we reduce the number of constraints to be satisfied by a vector coloring; so $\bar{\vartheta}(G)\leq \bar{\vartheta}(G+e)$. The theorem also allows to easily prove that $\bar{\vartheta}(G)$ is sandwitched between the clique and the chromatic numbers. This was already proved by Lovász himself, but the new definition of the Lovász capacity function given by the theorem leads to a fairly easy proof of this fundamental result.
Lemma 1: For every graph $G$, we have $\omega(G)\leq \bar{\vartheta}(G)\leq\chi(G)$.Proof: To show $\omega(G)\leq \bar{\vartheta}(G)$, let $k=\omega(G)$, and consider a $k$-clique in $G$. Suppose that the graph $G$ is vector $k-1$-colorable, and let $v_1,\ldots,v_k$ be the corresponding unit vectors associated with the vertices of the clique. Then \[ \|v_1+\cdots+v_k \|^2=\sum_{i=1}^k\|v_i\|^2+\sum_{i\neq j}\langle v_i,v_j\rangle = k + k(k-1)\left(-\frac{1}{k-2}\right) = k - k\left(1+\frac{1}{k-2}\right) < 0 \] which is impossible.
To show $\bar{\vartheta}(G)\leq\chi(G)$, let $k=\chi(G)$ and consider $k$ vectors $\vec{v}_1,\ldots,\vec{v}_k$ of the form $\vec{v}_i=(v_{i,1},\ldots,v_{i,k},0,\ldots,0)$ where \[ v_{i,l}=\begin{cases} \sqrt{\frac{k-1}{k}} & \mbox{ for $l=i$}\\ -\sqrt{\frac{1}{k(k-1)}} & \mbox{ for all $l\neq i$} \end{cases} \] These vectors are unit vectors: \[ \|\vec{v}_i\|^2=\frac{k-1}{k}+(k-1)\cdot \frac{1}{k(k-1)}=1\,. \] For any $i\neq j$ we have \[ \langle \vec{v}_i,\vec{v}_j\rangle = (k-2)\cdot\frac{1}{k(k-1)} -2\cdot \frac{1}{k} =\frac{k-2}{k(k-1)} -\frac{2}{k}=-\frac{1}{k-1}\,. \] Now, if we have a coloring of $G$ with colors $1,\ldots,k$, then we can assign vector $\vec{v}_i$ to the $i$-th color class. Since endpoints of each edge of $G$ receive different colors, this gives us a vector $k$-coloring of $G$. $\Box$
As we mention in the book, Grötschel, Lovász and Schrijver (in this paper) gave a polynomial time approximation algorithm for $\vartheta$. That is, given a graph $G$ and a rational number $\epsilon>0$ the algorithm computes, in $\mathrm{poly}(n,1/\epsilon)$ time, a function $g(G,\epsilon)$ such that \[ \bar{\vartheta}(G)\leq g(\overline{G},\epsilon)\leq \bar{\vartheta}(G)+\epsilon\,.\qquad\qquad (*) \] Now, for any $0<\epsilon<1/2$ the function $\lfloor g(\overline{G},\epsilon)\rfloor$ is a polynomial time computable function sandwitched between $\omega(G)$ and $\chi(G)$. But this function might not be monotone. The idea of Tardos (see her amazingly short paper) was to consider a slight perturbation of this function: \[ \phi(G):=\lfloor g(\overline{G},\epsilon)+|G|\cdot \epsilon\rfloor\qquad \mbox{ with }\ \ \epsilon:=1/n^2\,, \] where $n$ is the number of vertices and $|G|$ the number of edges in $G$.
Lemma 2: $\phi(G)$ is a monotone function computable in polynomial time, and satisfies $\omega(G)\leq \phi(G)\leq\chi(G)$.Proof: Let us first show that $\phi(G)$ is monotone, i.e. that $\phi(G)\leq \phi(G+e)$ holds: \begin{align*} \phi(G) &=\lfloor g(\overline{G},\epsilon)+|G|\cdot \epsilon\rfloor \overset{(\ast)}{\leq} \lfloor \bar{\vartheta}(G)+\epsilon +|G|\cdot \epsilon\rfloor =: K\,,\\ \phi(G+e) &=\lfloor g(\overline{G+e},\epsilon)+|G|\cdot \epsilon+\epsilon\rfloor \overset{(\ast)}{\geq} \lfloor \bar{\vartheta}(G+e) +|G|\cdot \epsilon +\epsilon\rfloor \geq \lfloor \bar{\vartheta}(G) +|G|\cdot \epsilon +\epsilon\rfloor =K. \end{align*} Let us now show the inequalities $\omega(G)\leq \phi(G)\leq\chi(G)$: \begin{align*} \phi(G)&=\lfloor g(\overline{G},\epsilon)+|G|\cdot \epsilon\rfloor \overset{(\ast)}{\leq} \lfloor \bar{\vartheta}(G)+\epsilon +|G|\cdot \epsilon\rfloor \overset{\mathrm{Lemma~1}}{\leq} \lfloor \chi(G)+\overbrace{\epsilon +|G|\cdot \epsilon}^{< 1}\rfloor\leq \chi(G)\,,\\ \phi(G)&=\lfloor g(\overline{G},\epsilon)+|G|\cdot \epsilon\rfloor \overset{(\ast)}{\geq} \lfloor \bar{\vartheta}(G)+|G|\cdot \epsilon\rfloor \overset{\mathrm{Lemma~1}}{\geq} \lfloor \omega(G)+|G|\cdot \epsilon\rfloor\geq \omega(G) \end{align*} $\Box$
For every integer $3\leq k\leq n$, the Tardos function (with threshold $k$) is a monotone boolean function $T_k$ of $\tbinom{n}{2}$ boolean variables encoding the edges of a graph on $n$ vertices, whose values are defined by \[ T_k(G)=1\ \ \mbox{ iff }\ \ \phi(G)\geq k\,. \] The function is monotone because $\phi(G)$ is such. The function has non-monotone circuits of polynomial size because $\phi(G)$ is computable in polynomial time. Finally, the function accepts all $k$-cliques $G$ (because then $\phi(G)\geq \omega(G)=k$), and rejects all complete $l$-partite graphs $G$ with $l\leq k-1$ (because then $\phi(G)\leq \chi(G)\leq k-1$), just as the $k$-CLIQUE function does. Note that $T_k$ accepts all graphs accepted by $k$-CLIQUE, but can also accept some graphs rejected by $k$-CLIQUE, namely, non-perfect graphs $G$ with $\omega(G) < k$ and $\chi(G)\geq k$.