% Revised version, accepted to the Electronic J. of Combinatorics.
% October 29, 1994.
%A LaTeX file for an 8 page article.
\title{Explicit Ramsey graphs and orthonormal labelings}
\author{Noga Alon
\thanks{ AT \& T Bell Labs, Murray Hill, NJ 07974, USA
and Department of Mathematics,
Raymond and Beverly
Sackler Faculty of Exact Sciences,
Tel Aviv University, Tel Aviv, Israel.
Research supported in part by a United
States Israel BSF Grant. }}
\date{}
\documentstyle [11pt]{article}
% SIDE MARGINS:
\oddsidemargin 0pt % Left margin on odd-numbered pages.
\evensidemargin 0pt % Left margin on even-numbered pages.
\marginparwidth 40pt % Width of marginal notes.
\marginparsep 10pt % Horizontal space between outer margin and
% marginal note
% VERTICAL SPACING:
\topmargin 0pt % Nominal distance from top of page to top of
% box containing running head.
\headsep 10pt % Space between running head and text.
% DIMENSION OF TEXT:
\textheight 8.4in %Height of text(including footnotes and figures,
% excluding running head and foot).
\textwidth 6.5in % Width of text line.
\newtheorem{theo}{Theorem}[section]
\newtheorem{prop}[theo]{Proposition}
\newtheorem{lemma}[theo]{Lemma}
\newtheorem{coro}[theo]{Corollary}
\newtheorem{conj}[theo]{Conjecture}
\renewcommand{\baselinestretch}{1.2}
\def \G {\overline G}
\begin{document}
\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics 1 (1994),\#R12\hfill}
\thispagestyle{empty}
\maketitle
\setcounter{page}{0}
\begin{center}
Submitted: August 22, 1994; Accepted October 29, 1994
\end{center}
\begin{abstract}
We describe an explicit construction of triangle-free graphs with no
independent sets of size $m$ and with $\Omega(m^{3/2})$ vertices,
improving a sequence of previous constructions by various authors.
As a byproduct we show that the maximum possible value of the Lov\'asz
$\theta$-function of a graph on $n$ vertices with no independent set
of size $3$ is $\Theta(n^{1/3})$, slightly
improving a result of Kashin
and Konyagin who showed that this maximum is at least
$\Omega(n^{1/3}/ \log n)$ and at most $O(n^{1/3})$. Our results
imply that the maximum possible Euclidean norm of a sum
of $n$ unit vectors
in $R^n$, so that among any three of them some two are orthogonal,
is $\Theta(n^{2/3})$.
\end{abstract}
%\newpage
%\vspace{2cm}
%
%\noindent
%{\bf Keywords:}\, Eigenvalues, Ramsey graphs,
%Cayley graphs.
%
%\noindent
%{\bf Address for correspondence:}\, Noga Alon, Department of
%Mathematics, Tel Aviv University, Ramat Aviv, Tel Aviv, Israel.
%Email address: noga@math.tau.ac.il.
%
%\noindent
%{\bf AMS Subject Classification:}\, 05C35, 05C38, 05C55, 05C25.
%
%\newpage
\setcounter{page}{1}
\section{Introduction}
Let $R(3,m)$ denote the maximum number of vertices of a triangle-free
graph whose independence
number is at most $m$. The problem of determining or estimating R(3,m)
is a well studied Ramsey type problem.
Ajtai, Koml\'os and
Szemer\'edi proved in \cite{AKS} that $R(3,m) \leq O(m^2 / \log
m)$, (see also \cite{Sh} for an estimate with a better constant).
Improving a result of
Erd\"{o}s , who
showed in \cite{Er1} that
$R(3,m) \geq \Omega ((m/ \log m)^2)$,
(see also \cite{Sp}, \cite{Kr} or \cite{AS} for a simpler proof), Kim
\cite{Ki} proved, very recently, that the upper bound
is tight, up to a constant
factor, that is: $R(3,m) =\Theta(m^2 /\log m)$. His proof, as well
as that of Erd\"os, is probabilistic, and does not supply any
explicit construction of such a graph.
The problem of finding an explicit construction of
triangle-free graphs of independence number $m$ and
many vertices has also received a considerable amount of attention.
Erd\"{o}s \cite{Er2}
gave an explicit
construction of such graphs with
$$
\Omega (m^{(2 \log 2)/3( \log 3 - \log 2)})=\Omega (m^{1.13})
$$
vertices. This has been improved by Cleve and Dagum \cite{CD},
and improved further by Chung, Cleve and Dagum in
\cite{CCD}, where the authors present a construction with
$$
\Omega (m^{ \log 6/ \log 4 })=\Omega (m^{1.29})
$$
vertices. The best known explicit construction is given in
\cite{Al1}, where the number of vertices is
$\Omega (m^{4/3})$.
Here we improve this bound and describe an explicit construction
of triangle free graphs with independence numbers $m$ and
$\Omega(m^{3/2})$ vertices. Our graphs
are Cayley graphs and
their construction is based on some of the properties of certain
Dual BCH error-correcting codes.
The bound on their independence numbers follows from an estimate of
their Lov\'asz $\theta$-function. This fascinating
function, introduced
by Lov\'asz in \cite{Lo0}, can be defined as follows. If $G=(V,E)$ is
a graph, an {\em orthonormal labeling} of $G$ is a family
$(b_v)_{v \in V}$ of
unit vectors in an Euclidean space so that if $u$ and $v$ are distinct
non-adjacent vertices, then $b_u^t b_v=0$, that is,
$b_u$ and $b_v$ are orthogonal.
The $\theta$-number $\theta(G)$ is the minimum, over all
orthonormal labelings $b_v$ of $G$ and over all unit vectors $c$,
of
$$
max_{v \in V} \frac{1}{(c^t b_v)^2}.
$$
It is known (and easy; see \cite{Lo0}) that the independence number
of $G$ does not exceed
$\theta(G)$. The graphs $G_n$ we construct here are
triangle free graphs on $n$ vertices satisfying $\theta(G_n)
= \Theta(n^{2/3})$,
and hence the independence number of $G_n$ is at most $O(n^{2/3})$.
The construction and the properties of the $\theta$-function
settle a geometric problem posed by Lov\'asz
and partially solved by Kashin and Konyagin \cite{Ko}, \cite{KK}.
Let $\Delta_n$ denote the maximum possible value of the Euclidean
norm $||\sum_{i=1}^n u_i||$ of the sum of $n$ unit vectors
$u_1, \ldots ,u_n$
in $R^n$, so that among any three of them some two are orthogonal.
Motivated by the study of the $\theta$-function, Lov\'asz raised
the problem of determining the order of magnitude of $\Delta_n$.
In \cite{Ko} it is shown that $\Delta_n \leq O(n^{2/3})$
and in \cite{KK} it is proved that this is nearly tight,
namely that $\Delta_n \geq \Omega(n^{2/3} /(\log n)^{1/2})$.
Here we show that the upper bound is tight up to a constant factor,
that is:
$$
\Delta_n=\Theta(n^{2/3}).
$$
The rest of this note is organized as follows. In Section 2
we construct our graphs and estimate their $\theta$-numbers
and their independence numbers. The resulting
lower bound for $\Delta_n$
is described in Section 3. Our method in these sections
combines the ideas of
\cite{KK} with those in \cite{Al1}.
The final Section 4 contains some concluding
remarks.
\section{The graphs}
For a positive integer $k$, let $F_k=GF(2^k)$ denote the finite
field with $2^k$ elements. The elements of $F_k$ are represented,
as usual, by binary vectors of length $k$. If $a,b$ and $c$ are three
such vectors, let $(a,b,c)$ denote their concatenation, i.e.,
the binary vector of length $3k$
whose coordinates are those of $a$, followed by those of $b$
and those of $c$.
Suppose $k$ is not divisible by $3$ and put $n=2^{3k}$.
Let $W_0$ be the set of all nonzero elements $\alpha \in F_k$
so that the leftmost bit in the binary representation
of $\alpha^7$ is $0$, and let $W_1$
be the set of all nonzero elements $\alpha \in F_k$ for which
the leftmost bit of $\alpha^7$ is $1$. Since $3$ does not divide $k$,
$7$ does not divide $2^k-1$ and hence $|W_0|=2^{k-1}-1$ and
$|W_1|=2^{k-1}$, as when $\alpha$ ranges over all nonzero elements
of $F_k$ so does $\alpha^7$.
Let $G_n$ be the graph whose vertices
are all $n=2^{3k}$ binary vectors of length $3k$, where two vectors
$u$ and $v$ are adjacent if and only if there exist
$w_0 \in W_0$ and $w_1 \in W_1$ so that
$u+v=(w_0,w_0^3,w_0^5)+(w_1,w_1^3,w_1^5)$, where here the
powers are computed in the field $F_k$ and the addition is addition
modulo $2$. Note that $G_n$ is the Cayley graph of the additive group
$(Z_2)^{3k}$ with respect to the generating set
$S=U_0+U_1=\{u_0+u_1: u_0 \in U_0, u_1 \in U_1\}$, where
$U_0=\{ (w_0,w_0^3,w_0^5): w_0 \in W_0\}$, and $U_1$ is defined
similarly.
The following theorem summerizes some
of the properties of the graphs $G_n$.
\begin{theo}
\label{t21}
If $k$ is not divisible by $3$ and $n=2^{3k}$ then
$G_n$ is a $d_n=2^{k-1}(2^{k-1}-1)$-regular graph on
$n=2^{3k}$ vertices with the following properties.
\begin{enumerate}
\item
$G_n$ is triangle-free.
\item
Every eigenvalue $\mu$ of $G_n$, besides the largest, satisfies
$$
-9 \cdot 2^k -3 \cdot 2^{k/2} -1/4 \leq \mu \leq
4 \cdot 2^k + 2 \cdot 2^{k/2} +1/4.
$$
\item
The $\theta$-function of $G_n$ satisfies
$$
\theta(G_n) \leq
n \frac{36 \cdot 2^k +12 \cdot 2^{k/2} +1}{2^k(2^k-2)+
36 \cdot 2^k +12 \cdot 2^{k/2} +1} \leq
(36+o(1)) n^{2/3},
$$
where here the $o(1)$ term tends to $0$ as $n$ tends to infinity.
\end{enumerate}
\end{theo}
{\bf Proof.}\,
The graph $G_n$ is the Cayley graph of $Z_2^{3k}$ with respect to
the generating set $S=S_n=U_0+U_1$, where $U_i$ are defined
as above.
Let $A_0$ be the $3k$ by $2^{k-1}-1$ binary matrix whose columns
are all vectors of $U_0$, and let $A_1$ be the $3k$ by $2^{k-1}$
matrix whose columns are all vectors of $U_1$. Let $A=[A_0,A_1]$ be
the $3k$ by $2^k-1$ matrix
whose columns are all those of $A_0$ and those of $A_1$.
This matrix is the
parity check matrix of a binary BCH-code of designed distance $7$
(see, e.g., \cite{MS}, Chapter 9), and hence every set of six columns
of $A$ is linearly independent over $GF(2)$. In particular,
all the sums $(u_0+u_1)_{u_0 \in U_0, u_1 \in U_1}$ are distinct
and hence $|S_n|=|U_0||U_1|$. It follows that
$G_n$ has $2^{3k}$ vertices and it is
$|S_n|=2^{k-1} (2^{k-1}-1)$ regular.
The fact that $G_n$ is
triangle-free is equivalent to the fact that the sum (modulo $2$)
of any set of
$3$ elements of $S_n$ is not the zero-vector. Let $u_0+u_1$,
$u'_0+u'_1$ and $u"_0+u"_1$ be three distinct elements of $S_n$,
where $u_0, u'_0,u"_0 \in U_0$ and $u_1,u'_1,u"_1 \in U_1$.
If the sum (modulo $2$) of these six vectors is zero then, since
every six columns of $A$ are linearly independent, every vector
must appear an even number of times in the sequence
$(u_0,u'_0,u"_0,u_1,u'_1,u"_1)$. However, since $U_0$ and $U_1$ are
disjoint this implies that every vector must appear an even number
of times in the sequence $(u_0,u'_0,u"_0)$ and this is clearly
impossible. This proves part $1$ of the theorem.
In order to prove part $2$ we argue
as follows. Recall that
the eigenvalues of Cayley graphs of abelian groups can be computed
easily in terms of the characters of the group. This result,
decsribed in, e.g., \cite{Lo}, implies that the eigenvalues of
the graph $G_n$ are all the numbers
$$
\sum_{s \in S_n} \chi(s),
$$
where $\chi$ is a character of $Z_2^{3k}$.
By the definition of
$S_n$, these eigenvalues are precisely all the numbers
$$
(\sum_{u_0 \in U_0} \chi(u_0))(\sum_{u_1 \in U_1} \chi(u_1)).
$$
It follows that these eigenvalues can be expressed in terms of the
Hamming weights of the linear combinations (over $GF(2)$)
of the rows of the matrices $A_0$ and $A_1$ as follows. Each linear
combination of the rows of $A$ of Hamming weight $x+y$, where
the Hamming weight of its projection on the columns of $A_0$
is $x$ and the weight of its projection on the columns of $A_1$
is $y$, corresponds to the eigenvalue
$$
(2^{k-1}-1-2x)(2^{k-1}-2y).
$$
Our objective is thus to bound these quantities.
The linear combinations of the rows of $A$ are simply all
words of the code whose generating matrix is $A$, which is the
dual of the BCH-code whose parity-check matrix is $A$. It is
known (see \cite{MS}, pages 280-281) that the
Carlitz-Uchiyama bound implies that the Hamming weight $x+y$ of
each non-zero codeword of this dual code satisfies
\begin{equation}
\label{e21}
2^{k-1}-2^{1+k/2} \leq x+y \leq 2^{k-1}+2^{1+k/2}.
\end{equation}
Let $p$ denote the characteristic vector of $W_1$, that is, the
binary vector indexed by the non-zero elements
of $F_k$ which has a $1$ in each coordinate indexed by a member
of $W_1$ and a $0$ in each coordinate indexed by a member of
$W_0$. Note that the sum (modulo $2$) of $p$ and any linear
combination of the rows of $A$ is a non-zero codeword in the dual
of the BCH-code with designed distance $9$. Therefore, by the
Carlitz-Uchiyama bound, the Hamming weight of the sum of $p$ with
the linear combination
considered above, which is $x+(2^{k-1}-y)$, satisfies
\begin{equation}
\label{e22}
2^{k-1}-3 \cdot 2^{k/2} \leq x+2^{k-1}-y \leq 2^{k-1}+3 \cdot 2^{k/2}.
\end{equation}
Since for any two reals $a$ and $b$,
$$
-(\frac{a-b}{2})^2 \leq ab \leq (\frac{a+b}{2})^2
$$
we conclude from (\ref{e21}) that
$$
(2^{k-1}-1-2x)(2^{k-1}-2y) \leq \frac{(2^k-1 -2(x+y))^2}{4}
\leq 4 \cdot 2^k + 2 \cdot 2^{k/2} +1/4.
$$
Similarly, (\ref{e22}) implies that
$$
(2^{k-1}-1-2x)(2^{k-1}-2y) \geq -\frac{(1+2(x-y))^2}{4}
\geq -9 \cdot 2^k -3 \cdot 2^{k/2} -1/4.
$$
This completes the proof of part 2 of the theorem.
Part 3 follows from part 2 together with Theorem 9 of \cite{Lo0}
which asserts that for $d$-regular graphs $G$ with eigenvalues
$d=\lambda_1 \geq \lambda_2 \geq \ldots \geq \lambda_n$,
$$
\theta(G) \leq \frac{-n \lambda_n}{\lambda_1-\lambda_n}.
$$
It is worth noting that the fact that the right hand side in the
last inequality bounds the independence number of $G$ is due to
A. J. Hoffman.
$ \Box$
Since the independence number of each graph $G$ does not exceed
$\theta(G)$ the following result follows.
\begin{coro}
\label{c22}
If $k$ is not divisible by $3$ and $n=2^{3k}$, then the graph
$G_n$ is a triangle-free graph with independence number
at most $(36+o(1)) n^{2/3}.$ $\Box$
\end{coro}
Let $G_n$ be one of the graphs above and let $\G_n$
denote its complement. Since $G_n$ is a Cayley graph, Theorem
8 in \cite{Lo0} implies that $\theta(\G_n)\theta(G_n)
=n$ and hence, by Theorem \ref{t21}, $\theta(\G_n)
\geq (1+o(1))\frac{1}{36} n^{1/3}.$
In \cite{KK} it is proved
(in a somewhat disguised form), that for any graph $H$ with
$n$ vertices and no independent set of size $3$, $\theta(H)
\leq 2^{2/3}n^{1/3}$. (See also \cite{AK} for an extension).
Since $\G_n$ has no independent set of size $3$ and since
for every graph $H$, $\theta(H) \theta(\overline{H}) \geq n$
(see Corollary 2 of \cite{Lo0}) the following
result follows.
\begin{coro}
\label{c23}
If $k$ is not divisible by $3$ and $n=2^{3k}$, then
$\theta(G_n) =\Theta(n^{2/3})$ and $\theta(\G_n)=\Theta(n^{1/3}).$
Therefore, the minimum possible value of the $\theta$-number
of a triangle-free graph on $n$ vertices is $\Theta(n^{2/3})$
and the maximum possible value of the $\theta$-number of
an $n$-vertex graph with no independent set of size $3$ is
$\Theta(n^{1/3}).$
\end{coro}
\section{Nearly orthogonal systems of vectors}
A system of $n$ unit vectors $u_1, \ldots ,u_n$ in $R^n$
is called {\em nearly orthogonal} if any set of three
vectors of the system contains an orthogonal pair.
Let $\Delta_n$ denote the maximum possible value of the Euclidean
norm $||\sum_{i=1}^n u_i||$, where the maximum is taken over all
systems $u_1, \ldots ,u_n$ of nearly orthogonal vectors.
Lov\'asz raised
the problem of determining the order of magnitude of $\Delta_n$.
Konyagin showed in \cite{Ko} that $\Delta_n \leq O(n^{2/3})$
and that
$$\Delta_n \geq \Omega(n^{4/3-\log 3 / 2 \log 2}) \geq
\Omega(n^{0.54}).$$
The lower bound was improved by Kashin and Konyagin in \cite{KK},
where it is shown that
$$\Delta_n \geq \Omega(n^{2/3} /(\log n)^{1/2})$$.
The following theorem asserts that the upper bound is tight
up to a constant factor.
\begin{theo}
\label{t31}
There exists an absolute positive constant $a$ so that for every $n$
$$
\Delta_n \geq a n^{2/3}.
$$
Thus, $\Delta_n= \Theta(n^{2/3}).$
\end{theo}
{\bf Proof.} It clearly suffices to prove the lower bound for values
of $n$ of the form $n=2^{3k}$, where $k$ is an integer and $3$ does not
divide $k$. Fix such an $n$, let $G=G_n=(V,E)$ be the graph
constructed in the previous section and define
$\theta=\theta(G)$. By Theorem \ref{t21},
$\theta \leq (36+o(1)) n^{2/3}$. By the definition of $\theta$
there exists an orthonormal
labeling $(b_v)_{v \in V}$ of $G$ and a unit vector $c$
so that $(c^t b_v)^2 \geq 1/\theta $
for every $v \in V$. Therefore, the norm of the projection
of each $b_v$ on $c$ is at least $1/\sqrt {\theta}$ and by
assigning appropriate signs to the vectors $b_v$ we
can ensure that all these projections are in the same direction.
With this choice of signs, the norm of the projection of
$\sum_{v \in V} b_v$ on $c$ is at least $n/\sqrt {\theta}$,
implying that
$$
||\sum_{v \in V} b_v|| \geq n/\sqrt {\theta} \geq
(\frac{1}{6}-o(1)) n^{2/3}.
$$
Note that since the vectors $b_v$ form an orthonormal labeling
of $G$, which is triangle-free, among any three of them there are
some two which are orthogonal. This implies that $(b_v)_{v \in V}$
is a nearly orthogonal system and shows that for every $n=2^{3k}$ as
above
$$
\Delta_n \geq
(\frac{1}{6}-o(1)) n^{2/3},
$$
completing the proof of the theorem. $\Box$
\section{Concluding remarks}
The method applied here for explicut constructions of
triangle-free graphs with small independence numbers
cannot yield asymptotically better constructions. This is because
the independence number is bounded here by bounding the
$\theta$-number which, by Corollary \ref{c23}, cannot be smaller
than $\Theta(n^{2/3})$ for any triangle-free graph on
$n$ vertices.
Some of the results of \cite{KK} can be extended.
In a forthcoming paper with N. Kahale \cite{AK} we show
that for every $k \geq 3$
and
every graph $H$ on $n$ vertices
with no independent set of size $k$,
\begin{equation}
\label{e41}
\theta(H) \leq M n^{1-2/k},
\end{equation}
for some absolute positive constant $M$.
It is not known if this is tight for $k>3$. Combining this
with some of the properties of the $\theta$-function,
this can be used to show that for every $k \geq 3$ and
any system
of $n$ unit vectors $u_1, \ldots ,u_n$ in $R^n$ so that among
any $k$ of them some two are orthogonal, the inequality
$$
||\sum_{i=1}^n u_i|| \leq O( n^{1-1/k})
$$
holds. This is also not known to be tight for $k>3$.
Lov\'asz (cf. \cite{Kn})
conjectured that there exists an absolute constant $c$ so that
for every graph $H$ on $n$ vertices and no independent set of size
$k$,
$$
\theta(H) \leq c k \sqrt n.
$$
Note that this conjecture, if true, would imply that the estimate
(\ref{e41}) above is {\em not} tight for all fixed $k>4$.
\noindent
{\bf Acknowledgment}
I would like to thank
Nabil Kahale for helpful comments and
Rob Calderbank
for fruitful suggestions that improved the presentation significantly.
\begin{thebibliography}{99}
\bibitem{AKS} M. Ajtai, J. Koml\'{o}s
and E. Szemer\'{e}di,
{\em A note on Ramsey numbers},
J. Combinatorial Theory Ser. A 29 (1980), 354-360.
\bibitem{Al1} N. Alon, {\em Tough Ramsey graphs without short cycles},
to appear.
\bibitem{AK} N. Alon and N. Kahale, in preparation.
\bibitem{AS} N. Alon and J. H. Spencer,
{\bf The Probabilistic Method}, Wiley, 1991.
\bibitem{CCD}
F. R. K. Chung, R. Cleve and P. Dagum,
{\em A note on constructive lower bounds for the Ramsey numbers
$R(3,t)$}, J. Combinatorial Theory Ser. B 57 (1993), 150-155.
\bibitem{CD} R. Cleve and P. Dagum,
{\em A constructive $\Omega (t^{1.26})$ lower bound for the Ramsey
number $R(3,t)$}, Inter. Comp. Sci. Inst. Tech. Rep. TR-89-009,
1989.
\bibitem{Er1} P. Erd\"{o}s,
{\em Graph Theory and Probability, II},
Canad. J. Math. 13 (1961), 346-352.
\bibitem{Er2} P. Erd\"{o}s,
{\em On the construction of certain graphs},
J. Combinatorial Theory 17 (1966), 149-153.
\bibitem{KK} B. S. Kashin and S. V. Konyagin,
{\em On systems of vectors in a Hilbert space},
Trudy Mat. Inst. imeni V. A. Steklova 157 (1981), 64-67.
English translation in:
Proc. of the Steklov Institute of Mathematics (AMS 1983), 67-70.
\bibitem{Ki} J. H. Kim,
{\em The Ramsey number $R(3,t)$
has order of magnitude $t^2/\log t$},
to appear.
\bibitem{Kn} D. E. Knuth,
{\em The sandwich theorem},
Electronic Journal of Combinatorics A1 (1994),
48pp.
\bibitem{Ko} S. V. Konyagin,
{\em Systems of vectors in Euclidean space and an extremal problem
for polynomials}, Mat. Zametki 29 (1981), 63-74.
English translation in: Mathematical Notes of the Academy of the USSR
29 (1981), 33-39.
\bibitem{Kr} M. Krivelevich,
{\em Bounding Ramsey numbers through large
deviation inequalities}, to appear.
\bibitem{Lo0}
L. Lov\'asz, {\em On the Shannon capacity of a graph}, IEEE
Transactions on Information Theory IT-25, (1979), 1-7.
\bibitem{Lo}
L. Lov\'asz, {\bf Combinatorial Problems and Exercises}, North Holland,
Amsterdam, 1979, Problem 11.8.
\bibitem{MS}
F. J. MacWilliams and N. J. A. Sloane,
{\bf The Theory of Error-Correcting Codes},
North Holland, Amsterdam, 1977.
\bibitem{Sh} J. B. Shearer,
{\em A note on the independence number of a triangle-free graph},
Discrete Math. 46 (1983), 83-87.
\bibitem{Sp} J. Spencer,
{\em Asymptotic lower bounds for Ramsey functions}, Discrete Math.
20 (1977), 69-76.
\end{thebibliography}
\end{document}