% An AMSTeX file for a  3 page document
\documentstyle{amsppt}
\hsize=15.2cm
\vsize=22.9cm

\define \rank {\operatorname{rank}}
\def\adj{\mathrel-\joinrel\joinrel\mathrel-}   %long minus [3,D.Knuth]
\def\noadj{\hskip3pt\not\hskip-3pt\adj}  %not long minus [3,D.Knuth]
\def\pfbox
  {\hbox{\hskip 3pt\lower1pt\vbox{\hrule
  \hbox to 7pt{\vrule height 7pt\hfill\vrule}
  \hrule}}\hskip3pt}  %[3,D.Knuth]

\emergencystretch=0.5 cm

\document
\magnification\magstep1
\font\smcp=cmcsc8 
        \headline={\ifnum\pageno>1 {\smcp the electronic journal of combinatorics 4 (1997),
        \#R19\hfill\folio} \fi} 
\font\rhfont=cmcsc8
\centerline{\bf On the function ``sandwiched" between
               $\alpha(G)$ and $\overline{\chi}(G)$}
\bigskip
\centerline{V. Y. Dobrynin \footnote{e-mail address: {\tt <vdobr\@gamma.niimm.spb.su>}}}
\vskip .2in
\centerline{Submitted: July 18, 1997; Accepted: September 2, 1997}


\vskip .3in
\centerline{\bf Abstract}

A new function of a graph $G$ is presented. Say that a matrix $B$
that is indexed by vertices of $G$ is feasible for $G$ if it is real,
symmetric and $I \le B \le I  + A(G),$ where $I$ is the identity
matrix and $A(G)$ is the adjacency matrix of $G$. Let $\Cal B(G)$
be the set of all feasible matrices for $G$, and let $\overline{\chi}(G)$ be  the smallest
number of cliques that cover the vertices of $G$. We show that
$$
  \alpha(G) \le \min \{\,\rank(B)\,\vert B \in \Cal B(G)\} \le
  \overline{\chi}(G)
$$
and that $\alpha(G)= \min \{\,\rank(B)\,\vert B \in \Cal B(G)\}$
implies    $ \alpha(G)=\overline{\chi}(G).$

\vskip .6in
The well known  Lov\'asz number $\vartheta(G)$ of a graph~$G$ [1] is
``sandwiched" between the size of the largest stable set in $G$ and the smallest
number of  cliques  that cover the vertices of $G$
$$
    \alpha(G) \le  \vartheta(G) \le \overline{\chi}(G).
$$

Some alternative definitions of $\vartheta(G)$ are introduced in
[2,3]. For example,
$$\eqalignno{
\vartheta(G)=\max\{\,&\Lambda(B)\,\vert
B\hbox{ is a real positive semidefinite matrix} \cr
&\hbox{indexed by vertices of $G$,} \cr
&B_{vv}=1 \ \hbox{for all $v \in V(G)$,}\cr
&B_{uv}=0 \ \hbox{whenever $u \adj v$ in $G$}\}, }
$$
where $\Lambda(B)$ is the maximum eigenvalue of $B$, $V(G)$ --- the set of
vertices of $G$, $u \adj v$ denotes the adjacency of vertices
$u$ and $v$.

Call the matrix $B$ indexed by vertices of $G$ feasible for $G$ if
$$\eqalignno{
&B\,\hbox{ is real and symmetric,} \cr
&B_{vv}=1 \ \hbox{for all $v \in V(G)$,}\cr
&B_{uv}=0 \ \hbox{whenever $u \noadj v$ in $G$,}\cr
&0 \le B_{uv} \le 1 \ \hbox{whenever $u \adj v$ in $G$.}  }
$$

Let $\Cal B(G)$ be the set of all feasible matrices for $G$. Then [4]
$$
  \overline{\chi}(G) = \min \{\,\rank(B)\,\vert B \in \Cal B(G),
    B=C^TC, C \ge 0 \},
$$
where the inequality denotes componentwise inequality.


The aim of this paper is to study a  new function  of
graph  $G$
$$
    \min \{\,\rank(B)\,\vert B \in \Cal B(G)\}.
$$

Clearly  $\alpha(G) \le \min \{\,\rank(B)\,\vert B \in \Cal B(G)\}$,
because every stable set in $G$ with $k$ vertices corresponds
to an identity $k \times k$-submatrix  of any matrix $B \in \Cal B(G).$

\proclaim
{Theorem} For all graphs $G$
$$
  \alpha(G)= \min \{\,\rank(B)\,\vert B \in \Cal B(G)\}
$$
implies    $ \alpha(G)=\overline{\chi}(G).$
\endproclaim
\noindent
{\bf Proof.}\quad
Let $S=\{v_1,v_2,\dots,v_{\alpha(G)}\}$ be the stable set of $G$,
$\overline{S}=V(G)\setminus S$
and
$B \in \Cal  B(G)$ is a matrix such that $ \rank(B)=\alpha(G)$. We can assume that
$$
    B=\left(\matrix I_{\alpha(G)}&X\\ X^T&Y \endmatrix \right),
$$
where $I_{\alpha(G)}$ is the identity $\alpha(G)  \times \alpha(G)$-matrix.

Applying block Gauss elimination, $B$ reduces to the matrix
$$
    B^\prime=\left(\matrix I_{\alpha(G)}&X\\ 0&Y-X^TX \endmatrix \right).
$$
We have
$$
    Y-X^TX=0
$$
or
$$
  Y_{uv}-\sum_{w \in S}X_{wu}X_{wv}=0,\ \ u,v \in \overline{S} \eqno(1)
$$
since $\rank(B^\prime)=\rank(B)=\alpha(G).$

Equation (1) gives us further information about the graph $G$.
\itemitem{(i)}If $v \in \overline{S}$ then exists $u \in S$ such that
$u \adj v$. Indeed, $Y_{vv}=1$ and $X_{wv}\ge 0$ for  all $w \in S.$
Hence,\  $\sum_{w \in S}X_{wv}^2=1$ and $X_{uv}>0$ for some $u \in S.$
\itemitem{(ii)}If $v^\prime,v^{\prime\prime} \in \overline{S}$
and $X_{uv^\prime}X_{uv^{\prime\prime}}>0$ for some $u \in S$ then
$v^\prime  \adj v^{\prime\prime}.$ Indeed, if
\  $\sum_{w \in S}X_{wv^\prime}X_{wv^{\prime\prime}}>0$ then
$Y_{v^{\prime}v^{\prime\prime}}>0.$

Let $$V_u=\{u\}\cup \{v \vert v \in \overline{S},X_{uv}>0\}$$
for all $u \in S$ and $G(V_u)$ be the subgraph induced from
$G$ by leaving out all vertices except vertices from $V_u.$
We know from (i) and (ii) that $G(V_u)$ is a clique  and
$V(G)=\cup_{u \in S}V_u.$ Hence,  $\overline{\chi}(G)=\alpha(G).\pfbox $
\proclaim
{ Corollary }
If $\overline{\chi}(G)\le \alpha(G)+1$ then
$$
  \overline{\chi}(G)= \min \{\,\rank(B)\,\vert B \in \Cal B(G)\}.
$$
\endproclaim
For example, consider the Petersen graph $G$. We have
$\alpha(G)=\vartheta(G)=4,\; \overline{\chi}(G)=5.$ Hence,
$\min \{\,\rank(B)\,\vert B \in \Cal B(G)\}=5.$

There is a graph $G$ such that
$$
  \alpha(G)< \min \{\,\rank(B)\,\vert B \in \Cal B(G)\}< \overline{\chi}(G).
$$
Let $V(G)=2^{\{1,2,3,4,5,6\}}$ and $ u \adj v $ iff
$2 \le \vert (u\setminus v) \cup (v\setminus  u)\vert \le 5$
for all $u,v \in V(G).$
Then [5]
$\chi(G)=32$ and $\rank(A(G))=29$ where $A(G)$ is the adjacency matrix
of $G$. Then $\overline{\chi}(\overline{G})=32$ and
$$
 \rank(I+A(\overline{G}))=\rank(J-A(G))\le 1+\rank(A(G))=30,
$$
where $J$ is all 1's.

Notice that $I+A(\overline{G})\in \Cal B(\overline{G}).$ Therefore
$$
\min \{\,\rank(B)\,\vert B \in \Cal B(\overline{G})\}< \overline{\chi}(\overline{G})
$$
and
$$
\alpha(\overline{G})<\min \{\,\rank(B)\,\vert B \in \Cal B(\overline{G})\}
$$
by theorem.

\bigskip\noindent
{\bf Acknowledgement.}

The author is grateful to the anonymous referee for valuable remarks.

\vskip 1in
\centerline{\bf References}

\par\noindent 1. L. Lov\'asz, ``On the Shannon capacity of a graph'',
{\sl IEEE Transactions on Information Theory\/} {\bf IT--25} (1979), 1--7.

\par\noindent 2. Martin Gr\"otschel, L\'aszl\'o Lov\'asz, and Alexander Schrijver,
{\sl Geometric Algorithms and Combinatorial Optimization\/}
(Springer-Verlag, 1988).

\par\noindent 3. Donald E.Knuth, ``The Sandwich Theorem'',
{\sl Electronic J. Combinatorics\/} {\bf 1}, A1 (1994), 48 pp.

\par\noindent 4. V.Y.Dobrynin, ``The chromatic number of a graph
and rank of matrix associated with it'',
{\sl Vestnik Sankt-Peterburgskogo Universiteta\/}, Ser.1, Issue 2, Vol.15
(1995),  120--122.

\par\noindent 5. N.Alon, P.D.Seymour. ``A counterexample to the
rank-coloring conjecture'',
{\sl Journal of Graph Theory}  {\bf 13} (1989), 523--525.
\enddocument