More on Tardos' function

Lovász' theta-function $\vartheta(G)$ introduced in this paper is a fundamental concept allowing to efficiently solve the clique problem on perfect graphs, i.e. those for in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph. Tardos' monotone boolean function is based on $\vartheta(G)$.

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$.

[ADDED 31.08.2017] I couldn't realize from the GLS-paper (Section 6) that the approximation error in (*) is indeed one-sided. But even if we only have \[ \bar{\vartheta}(G)-\epsilon\leq g(\overline{G},\epsilon)\leq \bar{\vartheta}(G)+\epsilon\,,\qquad\qquad (**) \] Tardos' construction works with a slight modification. Namely define \[ \phi(G):=\lfloor g(\overline{G},\epsilon)+|G|\cdot 2\epsilon\rfloor\qquad \mbox{ with }\ \ \epsilon:=1/n^2\,. \] That is, just take $|G|\cdot 2\epsilon$ instead of $|G|\cdot \epsilon$. 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 2\epsilon\rfloor \overset{(\ast\ast)}{\leq} \lfloor \bar{\vartheta}(G)+\epsilon +|G|\cdot 2\epsilon\rfloor =: K\,,\\ \phi(G+e) &=\lfloor g(\overline{G+e},\epsilon)+|G|\cdot 2\epsilon+2\epsilon\rfloor \overset{(\ast\ast)}{\geq} \lfloor \bar{\vartheta}(G+e)-\epsilon +|G|\cdot 2\epsilon +2\epsilon\rfloor \geq \lfloor \bar{\vartheta}(G) +|G|\cdot 2\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 2\epsilon\rfloor \overset{(\ast\ast)}{\leq} \lfloor \bar{\vartheta}(G)+\epsilon +|G|\cdot 2\epsilon\rfloor \overset{\mathrm{Lemma~1}}{\leq} \lfloor \chi(G)+\overbrace{\epsilon +|G|\cdot 2\epsilon}^{< 1}\rfloor\leq \chi(G)\,,\\ \phi(G)&=\lfloor g(\overline{G},\epsilon)+|G|\cdot 2\epsilon\rfloor \overset{(\ast\ast)}{\geq} \lfloor \bar{\vartheta}(G)-\epsilon+|G|\cdot 2\epsilon\rfloor \overset{\mathrm{Lemma~1}}{\geq} \lfloor \omega(G)+\overbrace{|G|\cdot 2\epsilon-\epsilon}^{\geq 0}\rfloor\geq \omega(G) \end{align*}

S. Jukna, 24.08.2017