%final version, submitted March 13
\documentclass[12pt]{article}
\usepackage{latexsym}
\usepackage{psfig}
\usepackage[latin2]{inputenc}
%\font\pici=cmssi8
\pagestyle{myheadings}
\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics \textbf{7} (2000),
\#R15\hfill}
\thispagestyle{empty}
\title{ Low Rank Co-Diagonal Matrices and Ramsey Graphs}
\author{Vince Grolmusz\\
{\small Department of Computer Science}\\ {\small E\"otv\"os University,
H-1053 Budapest}\\
{\small HUNGARY}
\\ {\small E-mail:
grolmusz@cs.elte.hu} \\ {\small Submitted: March 7, 2000. Accepted: March
12, 2000}}
\date{}
\tolerance=7500
\newcommand{\qed}{$\Box$}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{conjecture}[theorem]{Conjecture}
\newenvironment{proof}
{\pagebreak[1]{\narrower\noindent {\bf
Proof:\quad\nopagebreak}}}{\qed}
\def\L{\hbox{\rm L}}
\def\C{{\cal C}}
\def\size{\hbox{size}}
\def\sgn{\hbox{\rm sgn}}
\def\E{\hbox{\rm E}}
\def\Var{\hbox{\rm Var}}
\def\MOD{\hbox{\rm MOD}}
\def\AND{\hbox{\rm AND}}
\def\rank{\hbox{\rm rank}}
\oddsidemargin 0in
\evensidemargin 0in
\textwidth 6.5in
\textheight 8in
\begin{document}
\maketitle
\date{ }
\begin{abstract}
We examine $n\times n$ matrices over $Z_m$, with 0's in the diagonal and
nonzeros elsewhere. If $m$ is a prime, then such matrices have large rank
(i.e., $n^{1/(p-1)}-O(1)$ ). If $m$ is a non-prime-power integer, then we
show that their rank can be much smaller. For $m=6$ we construct a matrix
of rank $\exp(c\sqrt{\log n\log \log n})$. We also show, that explicit
constructions of such low rank matrices imply explicit constructions of
Ramsey graphs.
\end{abstract}
\bigskip
\noindent Keywords: composite modulus, explicit Ramsey-graph constructions,
matrices over rings, co-diagonal matrices
\bigskip
\section{Introduction}
In this work we examine matrices over a ring $R$, such that the diagonal
elements of the matrix are all 0's, but the elements off the diagonal are
not zero (we shall call these matrices co-diagonal over $R$). We define the
rank of a matrix over a ring, and show that low rank co-diagonal matrices
over $Z_6$ naturally correspond to graphs with small homogenous vertex sets
(i.e., cliques and anti-cliques). Consequently, explicitly constructible
low rank co-diagonal matrices over $Z_6$ imply explicit Ramsey graph
constructions. Our best construction reproduces the logarithmic order of
magnitude of the Ramsey-graph of {\em Frankl} and {\em Wilson} \cite{FW},
continuing the sequence of results on new explicit Ramsey graph
constructions of {\em Alon} \cite{Alon} and {\em Grolmusz} \cite{G99}. Our
present result, analogously to the constructions of \cite{G99} and
\cite{Alon}, can be generalized to more than one color.
Our results give a recipe for constructing explicit Ramsey graphs from
explicit low rank co-diagonal matrices over $Z_6$, analogously to the way
that our results gave a method for constructing explicit Ramsey graphs from
certain low degree polynomials over $Z_6$ in \cite{G99}. In this sense, our
results may lead to improved Ramsey graph constructions, if lower rank
co-diagonal matrix constructions exist.
\begin{definition}
Let $R$ be a ring and let $n$ be a positive integer. We say, that $n\times
n$ matrix $A=\{a_{ij}\}$ is a co-diagonal matrix over $R$, if $a_{ij}\in R,
\ i,j=1,2,\ldots,n$ and $a_{ii}=0, a_{ij}\ne 0$, for all
$i,j=1,2,\ldots,n$, $i\ne j$.
We say, that $A$ is an upper co-triangle matrix over $R$, if $a_{ij}\in R,
\ i,j=1,2,\ldots,n$ and $a_{ii}=0, a_{ij}\ne 0$, for all $1\leq ij.}$$
Consequently, by the triangle criterion \cite{BF}, polynomials
$$Q_i(x_1,x_2,\ldots,x_r)=1-P_i^{p-1}(x_1,x_2,\ldots,x_r), $$
for $i=1,2,\ldots,n$, form a linearly independent set in the vector space
of dimension
$${r+p-2\choose p-1}+1$$ of polynomials of form $Q+\alpha$, where $Q$ is an
$r$-variable homogeneous polynomial of degree $p-1$ and $\alpha\in$GF$_p$.
(To prove this without the triangle criterion of \cite{BF}, one should
observe that $Q_k$ is zero on column $i$ of matrix $C$ for $ii$.) Consequently,
$$n\leq {r+p-2\choose p-1}+1\leq (r+p)^{p-1}.\eqno{(3)}.$$
\end{proof}
We are interested in the following question:
\medskip
\noindent{\bf Question.} {\sl Let $R=Z_m$, what is the minimum rank of an
$n\times n$ co-triangle (or co-diagonal) matrix over $R$?}
\medskip
If $m=p$ a prime, then by Theorem \ref{largerank} we have that the rank
should be at least $n^{1/{p-1}}-p$. What can we say for non-prime $m$'s?
The main motivation of this question is the following theorem:
\begin{theorem}\label{ramsey1}
Let $A=\{a_{ij}\}$ be an $n\times n$ co-triangle matrix over $R=Z_6$, with
$r=\rank_{Z_6}(A)$. Then there exists an $n$-vertex graph $G$, containing
neither a clique of size $r+2$ nor an anti-clique of size
$${r+1\choose2}+2.$$
\end{theorem}
\begin{proof}
Suppose, that $A$ is a lower co-triangle matrix. If the $Z_6$ rank of $A$
is $r$, then both the GF$_2$ and GF$_3$ ranks of $A$ are at most $r$. Let
$V=\{v_1,v_2,\ldots,v_n\}.$ For any $i>j$, let us connect $v_i$ and $v_j$
with an edge, if $a_{ij}$ is odd. Then any clique of size $t$ will
correspond to a $t\times t$ lower co-triangle minor over GF$_2$, so from (3),
$$t\leq r+1.$$
Any anti-clique of size $t$ will correspond to a $t\times t$ lower
co-triangle minor over GF$_3$, so from (3),
$$t\leq {r+1\choose 2}+1.\eqno{(4)}$$
\end{proof}
{}From Theorem \ref{ramsey1} one can get a lower bound for the rank, using
estimations for the Ramsey numbers. Our original bound was significantly
improved by {\em Noga Alon}, who allowed us to include his proof here.
\begin{theorem}\label{lowerbound}
Let $A=\{a_{ij}\}$ be an $n\times n$ co-triangle matrix over $R=Z_6$.
Then
$$\rank_{Z_6}(A)\geq {\log n\over{2\log \log n}}-2.$$
\end{theorem}
\begin{proof}
By the result of {\em Ramsey} \cite{Ramsey} and {\em Erd\H os} and {\em
Szekeres} \cite{ErdSzek}, every $n$-vertex graph has either a clique on
$k$, or an anti-clique on $\ell$ vertices, if
$$n\geq{k+\ell-2\choose k-1}.$$ If we set $k=\lfloor{1\over2}{\log
n\over\log\log n}\rfloor$, and $\ell=\lfloor\log^2n\rfloor$, then we get
from Theorem \ref{ramsey1}, that both $r+2\leq k$ and ${r+1\choose 2}+2\leq
\ell $ cannot be satisfied, and this completes the proof.
\end{proof}
The proof of Theorem \ref{ramsey1} also proves
\begin{theorem}\label{ramsey2}
Suppose, that there exists an explicitly constructible $n\times n$
co-triangle matrix $A=\{a_{ij}\}$ over $R=Z_6$, with $r=\rank_{Z_6}(A)$.
Then one can explicitly construct an $n$-vertex Ramsey-graph, without
homogenous vertex-sets of size
$${r+1\choose2}+2.$$
\end{theorem}\qed
Our main result is that there do exist explicitly constructible low-rank
co-diagonal matrices over $Z_6$, implying explicit Ramsey-graph constructions.
\begin{theorem}\label{main}
There exists a $c>0$ such that for all positive integer $n$, there exists
an explicitly constructible $n\times n$ co-diagonal matrix $A=\{a_{ij}\}$
over $R=Z_6$, with $$\rank_{Z_6}(A)\leq 2^{c\sqrt{\log n\log \log n}}.$$
\end{theorem}
Theorem \ref{main} together with Theorem \ref{ramsey1}, gives an explicit
Ramsey-graph construction on $n$ vertices, without a homogeneous vertex-set
of size $2^{c'\sqrt{\log n\log \log n}}$, for some $c'>0$, or in other
words, an explicit Ramsey-graph construction on
$$2^{c''\log^2t\over \log\log t}$$
vertices, without homogeneous vertex-set of size $t$, for some $c''>0$.
This bound was first proven by {\em Frankl} and {\em Wilson} \cite{FW} with
a larger (better) constant than our $c''$, using the famous Frankl-Wilson
theorem \cite{FW}. We also gave a construction, using the BBR polynomial
\cite{BBR} and also the Frankl-Wilson theorem in \cite{G99}.
A generalization of our main result for ring $Z_m$, where $m$ has more than
two prime divisors:
\begin{theorem}\label{main-gen}
For any $m=p_1^{\alpha_1}p_2^{\alpha_2}...p_\ell^{\alpha_\ell}$, where the
$p_i$'s are distinct primes,
there exists a $c=c_m>0$ such that for all positive integer $n$, there
exists an explicitly constructible $n\times n$ co-diagonal matrix
$A=\{a_{ij}\}$ over $R=Z_m$,
with $$\rank_{Z_m}(A)\leq 2^{c\sqrt[\ell]{\log n(\log \log n)^{\ell-1}}}.$$
\end{theorem}
\section{Constructing Low Rank mod 6 Co-Diagonal Matrices}
In this section we prove Theorems \ref{main} and \ref{main-gen}.
Our main tool is the following theorem (choosing $m=6$ and $\ell=2$):
\begin{theorem}[Barrington, Beigel, Rudich\cite{BBR}]\label{BBR}
Given $m=p_1^{\alpha_1}p_2^{\alpha_2}...p_\ell^{\alpha_\ell}$
where the $p_i$ are distinct primes, then there exists
an explicitly constructible multi-linear polynomial $P$ with integer
coefficients, with $k$ variables, and of degree
$O(k^{1/\ell})$ which satisfies for $x\in\{0,1\}^k$, that $P(x)=0$ over
$Z_m$ iff $x=(0,0,\ldots,0)$.
\end{theorem}\qed
Let $k$ be the smallest integer such that $n\leq k^k$. Let
$B=\{0,1,2,\ldots,k-1\}$. Let us define $\delta:B\times B\to\{0,1\}$ as
follows:
$$\delta(u,v)=\cases{1, \hbox{ if } u=v,\cr
0 \hbox{ otherwise.}}$$
Then matrix $\bar{A}$ is defined as follows: both the rows and the columns
of $\bar{A}$ correspond to the elements of the set $B^k$. The entry of
matrix $\bar{A}$ in the intersection of a row, corresponding to
$u=(u_1,u_2,\ldots,u_k)\in B^k$ and of a column, corresponding to
$v=(v_1,v_2,\ldots,v_k)\in B^k$ is the number:
$$P(1-\delta(u_1,v_1),1-\delta(u_2,v_2),\ldots,1-\delta(u_k,v_k)).\eqno{(5)}$$
If $u=v$, then all of the $\delta(u_i,v_i)$'s are 1, so the value of $P$ is
0. So the diagonal of $\bar{A}$ is all-0, but no other elements of the
matrix are 0 over $Z_6$, consequently, $\bar{A}$ is co-diagonal over $Z_6$.
Multi-linear polynomial $P$ has degree $O(\sqrt{k})$, so (5) can be written
as the sum of
$${k\choose \leq
c\lfloor\sqrt{k}\rfloor}=\sum_{i=0}^{c\lfloor\sqrt{k}\rfloor}{k\choose
i}