\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Nathan Linial, Michael Saks and David Statter}
%
%
\medskip
\noindent
%
%
{\bf The Non-Crossing Graph}
%
%
\vskip 5mm
\noindent
%
%
%
%
Two sets are non-crossing if they are disjoint or one contains the
other. The {\em non-crossing graph} ${\rm NC}_n$ is the graph whose
vertex set is the set of nonempty subsets of $[n]=\{1,\ldots,n\}$ with
an edge between any two non-crossing sets.
Various facts, some new and some already known,
concerning the chromatic number, fractional chromatic
number, independence number, clique number and clique cover number
of this graph are presented.
For the chromatic number of this graph we show:
$$
n(\log_e n -\Theta(1)) \le \chi({\rm NC}_n) \le n
(\lceil\log_2 n\rceil-1).
$$
\bye