\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb,graphicx,psfig} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{amsmath,amsthm} \usepackage{amsfonts,latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}} \newcommand{\psdraw}[3]{\begin{array}{c} \hspace{-1mm} \raisebox{-4pt}{\psfig{figure=#1.ps,width=#2,height=#3}} \hspace{-62pt}\end{array}} \newtheorem{prop}{Proposition} \newtheorem{lemma}[prop]{Lemma} \newtheorem{cor}[prop]{Corollary} \newtheorem{theorem}[prop]{Theorem} \theoremstyle{definition} \newtheorem{defin}[prop]{Definition} \newtheorem{ex}{Example} \newtheorem{remark}[prop]{Remark} %\newenvironment{proof}[1][Proof]{\paragraph*{#1}}{\hspace*{\fill}$\Box$\bigskip} \def\mn{\mbox{-}} \def\SS{{\mathcal S}} \def\aaa{$\psdraw{shape000}{25mm}{5mm}$} \def\aab{$\psdraw{shape010}{25mm}{5mm}$} \def\aba{$\psdraw{shape100}{25mm}{5mm}$} \def\abb{$\psdraw{shape110}{25mm}{5mm}$} \def\baa{$\psdraw{shape001}{25mm}{5mm}$} \def\bab{$\psdraw{shape011}{25mm}{5mm}$} \def\bba{$\psdraw{shape101}{25mm}{5mm}$} \def\bbb{$\psdraw{shape111}{25mm}{5mm}$} \def\aaaa{$\psdraw{shape0000}{25mm}{5mm}$} \def\aaab{$\psdraw{shape0001}{25mm}{5mm}$} \def\abab{$\psdraw{shape0101}{25mm}{5mm}$} \def\abba{$\psdraw{shape0110}{25mm}{5mm}$} \newcommand\ul{$\Box \Box \Box$} \def\eex{$\psdraw{kmv_i11}{10mm}{14mm}$\hspace{36pt}} \def\eexx{$\psdraw{kmv_i22}{10mm}{14mm}$\hspace{36pt}} \def\eexxx{$\psdraw{kmv_i33}{10mm}{14mm}$\hspace{36pt}} \def\eexxxx{$\psdraw{kmv_i44}{10mm}{14mm}$\hspace{36pt}} \def\x1201{$\psdraw{1201}{7mm}{5.5mm}$\hspace{26pt}} \def\xcomp{$\psdraw{comp}{3.5mm}{5mm}$\hspace{16pt}} \def\xcompp{$\psdraw{comp2}{3.5mm}{5mm}$\hspace{16pt}} \def\eempty{$\psdraw{empty}{5mm}{5mm}$\hspace{16pt}} \def\udo{$\psdraw{udo}{3.5mm}{5mm}$\hspace{16pt}} \def\hdo{$\psdraw{hdo}{5mm}{3.5mm}$\hspace{16pt}} \def\amm{$\psdraw{am1}{5mm}{5mm}$\hspace{16pt}} \def\mam{$\psdraw{am2}{5mm}{5mm}$\hspace{16pt}} \def\upleft{\hspace{-5pt}$\psdraw{upleft}{4mm}{5mm}$\hspace{20pt}} \def\upright{\hspace{-5pt}$\psdraw{upright}{4mm}{5mm}$\hspace{20pt}} \def\downleft{\hspace{-2pt}$\psdraw{downleft}{4mm}{5mm}$\hspace{20pt}} \def\downright{\hspace{-5pt}$\psdraw{downright}{4mm}{5mm}$\hspace{20pt}} \def\square{$\psdraw{square}{5mm}{4mm}$\hspace{12pt}} \def\BB{\mathcal{B}} \def\AA{\mathcal{A}} \def\fstate{\overline{\epsilon}} \def\EE{\mathcal{E}} \newcommand\mps[1]{\marginpar{\small\sf#1}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode%\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm{\LARGE\bf Pattern Avoidance in Matrices} \vskip 1cm \large Sergey Kitaev,\footnote{Department of Mathematics, University of Kentucky, Lexington, KY 40506-0027, USA}\ \ Toufik Mansour\footnote{Research financed by the EC's IHRP Programme, within the Research Training Network ``Algebraic Combinatorics in Europe'', grant HPRN-CT-2001-00272.}\ \footnote{Department of Mathematics, University of Haifa, 31905 Haifa, Israel}\ \ and\ Antoine Vella\footnote{Department of Combinatorics and Optimization, University of Waterloo, Waterloo N2L 3G1, Ontario, Canada} \\ {\small Matematik}\\ {\small Chalmers tekniska h\"ogskola och G\"oteborg universitet}\\ {\small 412 96 G\"oteborg, Sweden} \href{mailto:kitaev@math.chalmers.se}{\tt kitaev@math.chalmers.se},\ \href{mailto:toufik@math.chalmers.se}{toufik@math.chalmers.se},\ \href{mailto:mg001@math.chalmers.se}{mg001@math.chalmers.se} \\ \end{center} \vskip .2 in \begin{abstract} We generalize the concept of pattern avoidance from words to matrices, and consider specifically binary matrices avoiding the smallest non-trivial patterns. For all binary right angled patterns (0/1 subconfigurations with 3 entries, 2 in the same row and 2 in the same column) and all $2 \times 2$ binary patterns, we enumerate the $m \times n$ binary matrices avoiding the given pattern. For right angled patterns, and the all zeroes 2 $\times$ 2 pattern, we employ direct combinatorial considerations to obtain either explicit closed form formulas or generating functions; in the other cases, we use the transfer matrix method to derive an algorithm which gives, for any fixed $m$, a closed form formula in $n$. Some of these cases lead naturally to extremal problems of Ramsey type. \end{abstract} \bigskip \section{Introduction and Background} The subject of pattern avoidance originated in the context of permutations; the original idea seems to be attributable to Donald Knuth, but the paper by Simion and Schmidt \cite{simsch} was the one that spawned the large body of work in this area in the last few years. Let $\pi = a_1a_2 \cdots a_t$, $\tau = b_1 b_2 \cdots b_s$ be finite sequences of integers; then a subsequence of $\pi$ of the same length as $\tau$ is said to be an \emph{occurrence} of $\tau$ if its entries occur in the same relative order as in $\tau$. More precisely, given indices $i_1 < i_2 < \cdots < i_{s}$, the subsequence $a_{i_1}a_{i_2}\cdots a_{i_s}$ is an occurrence of $\tau$ if and only if for all $j,k$ we have $a_{i_j} < a_{i_k} \Leftrightarrow b_{j} < b_k$. Thus for example 451428 is an occurrence of 341325 in 91452174289. For integers $p,q$, let us denote by $[p,q]$ the set $S = \{x \in \mathbb{Z} \ | \ p \leq x \leq q \} $. If $p = 0$, then $S$ is a \emph{non-negative} interval, and if $p=1$, we shorten the notation to $[q]$ and refer to $S$ as a \emph{positive interval}. Note that, in the above definition of occurrence, if all the $a_i$'s (respectively $b_i$'s) are distinct elements of $[t]$ (respectively $[s]$), then $\pi$ (respectively $\tau$) can be thought of as a permutation; otherwise, one can think of words (strings) with integers as the letters. The problems considered in this context are usually enumerative: how many permutations (words) of length $n$ \emph{avoid} (do not have an occurrence of) a given permutation (word) $\tau$? Apart from the issue of whether the entries are distinct or not, the major difference between the contexts of words or permutations lies in the fact that, in the context of words (strings), while the length of the string is allowed to grow, the entries usually come from a fixed finite alphabet, whereas of course the (distinct) entries of a growing permutation must necessarily come from a growing alphabet. The avoidance problem on words in the sense just described seems to have been first considered by Burstein \cite{thes:burst}. In this paper we extend these notions to matrices with integer entries. Although the definitions are, in principle, applicable to matrices with entries from a fixed {\it or} growing alphabet, we shall only consider the enumerative problem with a fixed binary alphabet. It turns out that in some specific cases this problem leads to interesting Ramsey-type extremal questions. Henceforth, $m,n$ will denote positive integers. A matrix $A$ of dimension $m \times n$ can be thought of as a function on $[m] \times [n]$ which associates to $(i,j)$ the entry $a_{i,j}$ on row $i$ and column $j$. We say that a subset $S \subseteq \mathbb{Z}^2$ is a \emph{shape} if both projections $\{ x \ | \ \exists y : (x,y) \in S \}$ and $\{ y \ | \ \exists x : (x,y) \in S \}$ are positive intervals. Since we shall be thinking of shapes in relation to subsets of entries of a matrix, we shall denote them pictorially by a collection of tiles in the two-dimensional integer lattice, with the convention (compatible with the usual matrix notation) that the row numbering corresponds to the first coordinate and starts from the top, and the column numbering corresponds to the second coordinate and starts from the left. Thus for example the symbol \eex stands for the set $\{(1,1),(3,2),(2,3),(2,4)\}$. We define a \emph{pattern} to be a surjection from a shape onto a non-negative interval. We shall extend the pictorial notation to represent the function, by placing the image of each point in the corresponding tile. Thus for example \eexx represents the function (pattern) which associates to the points $(1,1),(3,2),(2,3),(2,4)$ the images $1,1,0,1$ respectively. Now we define an occurrence of a pattern $P$ in a matrix, by analogy with the case of sequences. Given an $m \times n$-matrix $A =(a_{i,j})$ with integer entries, we say that a subset $T$ of $[m] \times [n]$ is an \emph{occurrence} of a pattern $P:S \rightarrow [0,s]$ in $A$ if there exists a bijection $\phi: S \rightarrow T$ such that for any two points $(i, j), \ (k, l) \in S$ with $(i', j') = \phi((i,j)), \ (k',l')=\phi((k, l))$, we have:\\[2mm] $i < k \Leftrightarrow i' < k'$ ; \quad $j < l \Leftrightarrow j' < l' $; \ \mbox{ and } \ $P(i,j) < P(k,l) \Leftrightarrow a_{i', \, j'} < a_{k', \, l'} $.\\[-3mm] Thus, for example, the set $\{(1,2), (2,5), (2,7), (3,4) \}$ is an occurrence of \x1201 in the matrix $$\left( \begin{array}{cccccccc} *&3&*&*&*&*&*\\ *&*&*&*&1&*&3\\ *&*&*&6&*&*&* \end{array} \right)$$ (the $*$ entries are irrelevant, and could be arbitrary integers). If there are no occurrences of a pattern $P$ in a matrix $M$, then $M$ is said to \emph{avoid} $P$. Given a set $Z$ of patterns, $M$ avoids $Z$ if it avoids every pattern in $Z$. In this paper we wish to introduce the following generalization of the pattern avoidance problem on words: given the pattern $P$, or a set of patterns $Z$, and an integer $t$, determine the function $ (m,n) \mapsto c_{m,n}$ which counts the number of different matrices of dimension $m \times n$ with entries in $[0,t]$ avoiding $P$ (or $Z$). In Sections 2 and 3, we tackle the problem in the first case of $t=1$, for several small choices of the pattern $P$. Although $P$ (or $Z$) may change according to the context, henceforth $c_{m,n}$ will denote the number of $m\times n$ matrices avoiding $P$ (or $Z$). \subsection{The connection to Bipartite Ramsey Problems} Any $m \times n$ matrix can be viewed as an edge-colouring of the complete bipartite graph $K_{m,n}$, whose vertex set is partitioned into two classes $A,B$ with $A$ indexed by the rows and $B$ indexed by the columns, the entry $a_{i,j}$ being the ``colour'' assigned to the edge corresponding to the $i$-th row and $j$-th column. In this context, the occurrence of a certain pattern in the matrix corresponds to a certain configuration in the coloured graph. This configuration can be more or less interesting from a graph-theoretic viewpoint according to the specific pattern. If the pattern uses only the integer 0, then avoidance of the pattern corresponds to avoidance of a monochromatic copy of this configuration (in any colour); otherwise, the configuration would involve edges of different colours. For certain patterns or sets of patterns, the numbers $c_{m,n}$ turn out to be 0 for large $m,n$; this gives an unexpected connection to Ramsey Theory in the form of the following question: how large can $m,n$ (or $m+n$) be so that $c_{m,n}>0$? Equivalently, how small can $m,n$ be so that the pattern is ``unavoidable'' in a matrix of dimension $m \times n$? Let us consider a few examples. If we take the patterns \udo and \hdo, the matrices simultaneously avoiding these two patterns correspond to proper edge colourings of $K_{m,n}$ (an edge colouring is \emph{proper} if no two edges with the same colour are incident with the same vertex), and it is easy to see that $c_{m,n}> 0 \Leftrightarrow \max\{m,n\} \leq t+1$. These edge-colourings can be characterized equally well by requiring that they do not contain a monochromatic copy of $P_3$ (for a positive integer $k$ we indicate by $P_k$ a path with $k$ vertices and $k-1$ edges). In this paper, we shall only consider the simple case where $t=1$; that is, our matrices will have entries in $\{0,1\}$. This does not trivialize the connection to Ramsey Theory. The above considerations imply that, in the language of \cite{hahame}, the bipartite Ramsey numbers $b(P_3,P_3)$ and $b'(P_3,P_3)$ are 3 and 4 respectively. Given a pair of bipartite graphs $B_1, B_2$, the \emph{bipartite Ramsey number} $b(B_1,B_2)$ (respectively $b'(B_1,B_2)$) is defined as the minimum value of $p$ for which any red/blue edge colouring of $K_{p,p}$ (respectively $K_{m,n}$ for some $m+n=p$) contains a blue copy of $B_1$ or a red copy of $B_2$. We shall write $b(B), b'(B)$ as abbreviations for $b(B,B), b'(B,B)$ respectively. We may generalize the above example by taking as patterns the two matrices $\mathcal{O}_{\ell,k}$ and $\mathcal{O}_{k,\ell}$, of dimensions $\ell \times k$ and $k \times \ell$ respectively, with all entries 0. The 0-1 matrices simultaneously avoiding these patterns correspond to edge-colourings which do not contain monochromatic copies of $K_{\ell,k}$. In the special case $\ell=k$, it is enough to exclude the single pattern $\mathcal{O}_{\ell,\ell}$. Harary, Harborth and Mengersen \cite{hahame} determined the bipartite Ramsey numbers (and the vanishing borders for $c_{m,n}$) for all pairs of bipartite (not necessarily equal) graphs on at most 5 vertices with no isolated vertices. The situation may be more complicated when we consider patterns which are not matrices. The pattern \aaa, for example, corresponds to a monochromatic copy of $P_4$ \emph{in which both vertices of degree 2 occur before (with respect to the ordering on $A$ and $B$) the other vertex in the same class}; to eliminate this qualification and simply exclude a monochromatic $P_4$, we need to take all 4 rotations of this pattern together. We may even consider patterns in which the entries are not all equal; for example the matrices \amm \ , \mam \ \ %$\left(\tiny\begin{array}{cc} 1&0\\0&1 \end{array}\right)$ %$\left(\tiny\begin{array}{cc} 0&1\\1&0 \end{array}\right)$ together exclude the appearance of an alternating cycle of length 4; the four rotations of \aba exclude the appearance of a copy of $P_4$ in which only the middle edge is coloured 1, and taking also the complements (replacing the entry $i$ by $1-i$) gives a set of eight patterns which together exclude alternating paths. In general, for the excluded configuration to have a natural graph-theoretic interpretation, one would want the set of possible occurrences to be closed under at least row and column permutations, preferably under taking the transpose as well, and perhaps even under complementation. Moreover, this on its own may not necessarily imply that the numbers $c_{m,n}$ become 0 for sufficiently large $m,n$ (thus leading to a Ramsey-type problem), as is trivially verified in the case of the alternating cycle. Thus, apart from the patterns $\mathcal{O}_{k,\ell}$ (which we shall discuss in Section 3.1), in order to obtain natural \emph{graph-theoretic} Ramsey-type situations in our context one needs to consider simultaneous avoidance of specific, and sometimes large, sets of patterns. On the other hand, as we shall see, a single simple pattern can force the numbers $c_{m,n}$ to vanish for sufficiently large $m,n$. It is not uncommon to consider Ramsey problems outside the context of graph theory (indeed, Ramsey theory did not arise in the context of graphs at all), so we say that a pattern $P$ is \emph{eventually unavoidable} if there exists a value $q$ such that every matrix of dimension $q \times q$ has an occurrence of $P$, and for an eventually unavoidable pattern, we define the Ramsey number $b(P)$ to be the smallest possible choice of $q$. Note that, in general, $c_{m',n'}=0 \Rightarrow \forall m \geq m', n \geq n'$ we have $c_{m,n} = 0$. We also define the Ramsey number $b'(P)$ to be the smallest value $p$ for which there exist $m,n$ with $m+n=p$ such that $c_{m,n}=0$. Finally, the \emph{vanishing border} of $P$, denoted by $V(P)$, is the set of pairs $(m,n)$ such that every matrix of dimension $m \times n$ has an occurrence of $P$, but both $(m-1,n)$ and $(m,n-1)$ do not have this property (we adopt the convention that there exist matrices of dimension $0 \times n$ and $m\times 0$). All these definitions are analogous to those given in \cite{hahame} for pairs of bipartite graphs. The focus of this paper is intended to be enumerative, rather than extremal: to determine the numbers $c_{m,n}$, rather than just their vanishing border. We shall consider almost exclusively avoidance of a single pattern $P$, for certain small examples of $P$, and we shall not aim for results of Ramsey type. However, we shall state a few extremal results that we obtain as by-products, and attempt to raise relevant questions which are interesting from the point of view of Ramsey Theory. \subsection{Equivalent patterns and some specific shapes} Recall that shapes are formally subsets of $\mathbb{Z}^2$, and all their elements have both coordinates positive. Let $S$ be any shape; reflecting $S$ about any one of the four axes of symmetry of $\mathbb{Z}^2$, (the vertical, horizontal and diagonal lines through the origin) yields a set $S'$ which may not be a shape; however, there always exists a unique translation $S''$ of $S'$ that is itself a shape. We shall always assume that these reflections are accompanied by this translation, so that they associate shapes to shapes, patterns to patterns and matrices to matrices. Thus, for example, \upleft is obtained by reflecting \upright about the horizontal axis. For a fixed value of $t$, another useful operation on patterns and matrices is that of \emph{complementation}: replacing each entry $i$ by $z-i$, where $z=s$ in the case of a pattern $P: S \rightarrow [0,s]$, and $z=t$ in the case of matrices (formally, this amounts to post-composing the pattern/matrix with the function $i \mapsto z-i$). Thus for example, the pattern \aaa is its own complement, \aab is the complement of \xcompp, %$\left(\tiny\begin{array}{cc} 1&0\\1 & \\ \end{array}\right)$ and for $t=1$, the matrix $\left(\tiny\begin{array}{cc} 0&0\\0 & 1 \\ \end{array}\right)$ %\aaab is the complement of $\left(\tiny\begin{array}{cc} 1&1\\1 & 0 \\ \end{array}\right)$. The above operations of reflection and complementation are all involutions on the sets of patterns and matrices which preserve occurrences, in the sense that if $\chi$ is one of the above operations, $P$ is a pattern and $M$ is a matrix, then $P$ occurs in $M$ if and only if $ \chi(P)$ occurs in $\chi(M)$\footnote{Note that, if $\chi$ is the operation of complementation, $\chi(M)$ may actually depend on whether we are considering $M$ as a pattern or a matrix avoiding a given pattern.}. Clearly, the same is true if $\chi$ is any composition of these operations. Note that reflecting a matrix about the line $y=x$ corresponds to taking its transpose\footnote{Recall the row-numbering increases \emph{downwards}.}. For this reason, we also refer to the reflection of a pattern $P$ about this line as the \emph{transpose} of $P$. As in classical permutation avoidance, these operations are useful in reducing the enumeration of pattern-avoiding matrices to a smaller number of cases (patterns). %\end{remark} The analysis of avoidance of a single pattern of dimension $1 \times n$ or $m \times 1$ can easily be reduced to that of avoidance of the pattern in each row (column) of the matrix independently. This problem has been considered by Burstein and Mansour \cite{buma1,buma2,buma3}. In this paper we do not attempt to deal with such patterns. Instead, we consider the following two basic configurations: \emph{right angled} and \emph{square} shapes, and all possible binary patterns on these shapes (note that given any shape $S$ and an integer $t$, there is only a finite number of patterns $P: S \rightarrow [0,s]$ with $s \leq t$). The right angled shapes are\, \downright, \downleft, \upleft and\, \upright; a pattern is right angled if its domain is a right angled shape. The square shape is \eempty, and the square patterns are the $2 \times 2$ matrices. If $t=1$, each right angled shape can be numbered in 8 ways, which reduce to 7 patterns, for a total of 28 possible right angled patterns. The operations mentioned above reduce these to three equivalence classes, which we represent by \aaa, \bab and \aab. In Section 2 we shall see that these three cases in fact reduce to two: the numbers $c_{m,n}$ are the same for the patterns \bab and \aab. The 16 square binary matrices reduce to $15$ square patterns, but the above operations allow us to restrict our attention to the following four patterns: \aaaa, \aaab, \abab, and \abba. %----------------------------------- \section{Right angled patterns} \subsection*{2.1 Avoidance of the pattern \aaa \label{sec_aaa}} We observe that since the pattern \aaa is its own transpose, a matrix avoids \aaa if and only if its transpose does. So it is enough to consider matrices of size $m\times n$, where $m\geq 2$ and $n\geq m$. In the proof of Proposition~\ref{prop1} and throughout the paper, we use phrases like ``this column does not affect the rest of the matrix" to mean ``the entries in this column can not occur as part of a forbidden pattern in the matrix"; this allows us to obtain recurrence relations. \begin{prop}\label{prop1} In the case of the pattern \aaa, we have that $c_{2,n}=2^{n+2}-4$ for $n\geq 1$; $c_{3,3}=16$; $c_{3,n}=0$ for $n\geq 4$; and $c_{m,n}=0$ for $n\geq m\geq 4$. \end{prop} \begin{proof} Assuming that $n\geq m$, let $A$ be an $m\times n$ matrix that avoids the pattern \aaa. {\em The case $m=2$.} If the first column of $A$ is $\binom{1}{0}$ or $\binom{0}{1}$, then obviously this column does not affect the rest of the matrix, and we have $2c_{2,n-1}$ possibilities to choose $A$ in this case. If the first column of $A$ is $\binom{0}{0}$ (respectively, $\binom{1}{1}$), then from the second entry onwards the first row of $A$ can consist only of $1$'s (respectively, $0$'s) since otherwise we have an occurrence of the pattern \aaa with the first column of $A$ as the first column of the occurrence. All the entries in the second row, except possibly the last one, must be 0 (respectively, 1), for otherwise we would have a literal occurrence of the numbered shape \bbb (respectively, \aaa)---which is an occurrence of the pattern \aaa---with the first row of the occurrence contained in the first row of the matrix. Thus, in this case we can choose the first row in 2 ways and then choose the rightmost bottom entry in 2 ways. Summarizing our considerations, we get the following recurrence relation $$c_{2,n}=2c_{2,n-1}+4,$$ with $c_{2,1}=4$. This gives that $c_{2,n}=2^{n+2}-4$. {\em The case $m=3$}. Obviously it suffices to consider the case $n=4$. Suppose, by way of contradiction, that the matrix $A$ avoids \aaa. Without loss of generality $A_{1,1}=0$. If the remaining three elements of the first row are 1, then all the elements in the lower right $2\times 3$ submatrix, except possibly $A_{3,4}$, are 0, and a contradiction results. So some other entry of the first row is also 0. Then it immediately follows that $A_{2,1}=A_{3,1}=1$ and hence also that $A_{2,2}=A_{2,3}=A_{2,4}=0$ and $A_{3,2}=A_{3,3}=1$. This yields the partially filled matrix $$\left( \begin{array}{cccc} 0&*&*&*\\ 1& 0 & 0& 0 \\ 1&1&1&* \end{array} \right)$$ with at least two $0$'s in the first row. One can see that we can not have three $0$'s in the first row, and thus we have two $1$'s in the first row which also creates the forbidden pattern. {\em The case $m=4$}. Follows from the case $m=3$ and $n\geq 4$. \end{proof} %\begin{figure} \caption{ %} \begin{center} \begin{tabular}{ccc} \hline\\ &\begin{footnotesize} \begin{tabular}{c|c|c|c|c|c} %\hline\\ &2&3&4&5&$\cdots$\\ \hline 2&4&12&28&60&$\cdots$\\ 3&12&16&0&\\ 4&28&0&&\\ 5&60&&&\\ $\vdots$&$\vdots$&&&&\\ %\hline \end{tabular} \end{footnotesize}&\\ \\ &The numbers $c_{m,n}$ for the pattern \aaa&\\ \\ \hline \end{tabular} \end{center} %\end{figure} \begin{cor} The pattern \aaa is eventually unavoidable. Its Ramsey numbers satisfy $\displaystyle b\left(\mbox{\aaa}\right) = 4$, $b'\left(\mbox{\aaa}\right) = 7$. The vanishing border is given by $\displaystyle V\left(\mbox{\aaa}\right) = \{(3,4),(4,3)\}$. \end{cor} \subsection*{2.2 Avoidance of the pattern \bab \label{sec_bab}} \begin{prop}\label{refaa} In the case of the pattern \bab, we have that %% $$\sum_{m,n\geq0}c_{m,n}x^my^n=\sum_{m\geq0}\frac{\frac{x^ny}{1-(n+1)y}}{\prod_{j=0}^m\left(x+\frac{(1-x)y}{1-jy}\right)}.$$ \end{prop} \begin{proof} Let $A$ be an $m\times n$ matrix avoiding the pattern \bab. Clearly, an empty matrix avoids $\pi$, so $c_{m,0}=c_{0,n}=1$. Suppose that $A$ is a matrix of size $m\times n$ with $m,n\ge 1$. If the top row of $A$ contains only zeros, then it does not affect the rest of the matrix and can be removed to obtain a \bab-avoiding matrix of $m-1$ rows and $n$ columns. Now suppose the top row of $A$ contains a $1$. Suppose that in the top row there are $i$ zeros to left of the rightmost $1$. Since $A$ avoids \bab, the $i$ columns containing those top zeros must be zero columns. Thus, these columns can not be involved in an occurrence of \bab, so they may be removed. The resulting top row has all $1$s to the left of all $0$s, so this top row can not be involved in an occurrence of \bab, and hence, may be removed as well. Each choice of $i+1$ positions (those of the rightmost $1$ in the top row and $i$ zeros to its left) yields, after the two removals, an $(m-1)\times(n-i)$ matrix avoiding \bab. Thus, \[ c_{m,n}=c_{m-1,n}+\sum_{i=0}^{n-1}{\binom{n}{i+1}c_{m-1,n-i}}, \quad m,n\ge 1. \] Straightforward technical manipulations, which are omitted, the ordinary generating function $a(x,y)=\sum_{n,m\geq0}c_{m,n}x^my^n$ satisfies the following recurrence $$a(x,y)=\frac{y}{(1-y)(x+(1-x)y)}+\frac{x}{x+(1-x)y}a\left(x,\frac{y}{1-y}\right).$$ The result follows by repeatedly applying this recursion and taking the limit.\end{proof} \subsection*{2.3 Avoidance of the pattern \aab} One can apply the same considerations made in Subsection~\ref{sec_bab}. The only difference between these cases is that instead of 0's below each 0 in the first row, we have 1's. This gives a recursive bijection between the matrices avoiding the pattern \bab and those avoiding the pattern \aab. Thus we obtain the following analogous result. \begin{prop} In the case of the pattern \aab, we have that $$\sum_{m,n\geq0}c_{m,n}x^my^n= \sum_{m\geq0}\frac{\frac{x^ny}{1-(n+1)y}}{\prod_{j=0}^m\left(x+\frac{(1-x)y}{1-jy}\right)}.$$ \end{prop} %----------------------------------- \section{Square patterns} \subsection*{3.1 Avoidance of the pattern \aaaa}\label{sec_aaaa} We make the same observation made in Subsection 2.1, that is, a matrix avoids the pattern \aaaa if and only if its transpose avoids the transpose of \aaaa, which is \aaaa itself. So it is enough to consider matrices of size $m\times n$ with $m\geq 2$ and $n\geq m$. Moreover, the pattern \aaaa has the following properties that are easy to see \begin{itemize} \item[1)] a matrix avoids \aaaa if and only if its complement does; \item[2)] permuting columns and rows of a matrix $M$ produces a matrix that avoids the pattern \aaaa if and only if $M$ does. \end{itemize} \begin{prop} In the case of the pattern \aaaa, we have that $c_{2,n}=(n^2+3n+4)2^{n-2}$ for $n\geq 0$; $c_{3,3}=168$; $c_{3,4}=408$; $c_{4,4}=3240$; $c_{3,n}=c_{4,n}=720$ for $n=5,6$; $c_{3,n}=c_{4,n}=0$ for $n>6$; and $c_{m,n}=0$ for $n\geq m\geq 5$. \end{prop} \begin{proof} Let $A$ be an $m\times n$ matrix, that avoids the pattern \aaaa. {\em The case $m=2$.} We consider only the case $A_{1,1}=0$, since the case $A_{1,1}=1$ gives the same number of matrices avoiding \aaaa, by property 1 above. If $A_{2,1}=1$, then the first column of $A$ does not affect the rest of the matrix, and therefore we have $c_{2,n-1}$ possibilities to choose $A$ in this case. If $A_{2,1}=0$ then no column of $A$ other than the first can be $\binom{0}{0}$, since this leads to an occurrence of \aaaa in $A$. On the other hand, $A$ obviously can not contain two columns which are both copies of $\binom{1}{1}$. So, either $A$ does not contain $\binom{1}{1}$ or else it contains precisely one such column. In the first case we have $2^{n-1}$ possibilities for $A$, since any column except the first one is either $\binom{1}{0}$ or $\binom{0}{1}$. In the second case, we can choose the position in which we have $\binom{1}{1}$ in $(n-1)$ ways, and then choose all other columns in $2^{n-2}$ ways. Thus we get the recurrence $$c_{2,n}=2\cdot(c_{2,n-1}+(n+1)2^{n-2}),$$ which gives the desired result. {\em The case $m=3$.} To deal with this case we make use of the following four facts. \noindent {\bf Fact 1.} There are no columns in $A$ that are equal to each other. This is easy to see, since otherwise we have an occurrence of the pattern \aaaa. \noindent {\bf Fact 2.} If both of the columns $\left(\tiny\begin{array}{c} 0 \\ 0 \\ 0 \end{array}\right)$ and $\left(\tiny\begin{array}{c} 1 \\ 1 \\ 1 \end{array}\right)$ appear in $A$, then $A$ can not have more than two columns. Indeed, using the fact that permuting the columns of $A$ does not affect avoidance of the pattern \aaaa, we can assume that the first two columns of $A$ are $\left(\tiny\begin{array}{c} 0 \\ 0 \\ 0 \end{array}\right)$ and $\left(\tiny\begin{array}{c} 1 \\ 1 \\ 1 \end{array}\right)$. Adding one more column will introduce an occurrence of the pattern \aaaa, since it will contain either two 1's or two 0's. \noindent {\bf Fact 3.} If $A$ contains either the column $\left(\tiny\begin{array}{c} 0 \\ 0 \\ 0 \end{array}\right)$ or the column $\left(\tiny\begin{array}{c} 1 \\ 1 \\ 1 \end{array}\right)$, then the other columns can only be chosen from a set consisting of three columns, without repetitions. In the first case these columns are $\left(\tiny\begin{array}{c} 0 \\ 1 \\ 1 \end{array}\right)$, $\left(\tiny\begin{array}{c} 1 \\ 0 \\ 1 \end{array}\right)$, and $\left(\tiny\begin{array}{c} 1 \\ 1 \\ 0 \end{array}\right)$, whereas in the second case they are $\left(\tiny\begin{array}{c} 1 \\ 0 \\ 0 \end{array}\right)$, $\left(\tiny\begin{array}{c} 0 \\ 1 \\ 0 \end{array}\right)$, and $\left(\tiny\begin{array}{c} 0 \\ 0 \\ 1 \end{array}\right)$. This is easy to see, since otherwise we obviously have an occurrence of the pattern \aaaa. \noindent {\bf Fact 4.} If $A$ does not contain $\left(\tiny\begin{array}{c} 0 \\ 0 \\ 0 \end{array}\right)$ or $\left(\tiny\begin{array}{c} 1 \\ 1 \\ 1 \end{array}\right)$, then the columns of $A$ can be chosen from among all the other six binary columns of length 3, without repetitions. This follows from the fact that once these two columns are excluded, any column must contain the same letter in two positions, and once these two entries are given, the third is uniquely determined; thus any two columns will give an occurrence of \aaaa if and only if they are equal. %no two of these six columns consider in two positions, %and thus contain the patterns \aaaa. As a corollary of Facts 1--4 we have the following $$c_{3,3}=2\cdot 3\cdot 3\cdot 2 + \frac{6!}{3!}=156;\ \ \ c_{3,4}=2\cdot4!+\frac{6!}{2!}=408;$$ $$c_{3,5}=c_{3,6}=6!=720;\ \ \ c_{3,n}=0 \mbox{ if }n>6;$$ where, for instance, to obtain $c_{3,3}$ we first count the number of those matrices that have either $\left(\tiny\begin{array}{c} 0 \\ 0\\ 0 \end{array}\right)$ or $\left(\tiny\begin{array}{c} 1 \\ 1 \\ 1\end{array}\right)$ as a column (of which, according to Fact~3, there are precisely $2\cdot 3\cdot 3\cdot 2$), and then we add the number of matrices that do not contain $\left(\tiny\begin{array}{c} 0 \\ 0 \\ 0 \end{array}\right)$ or $\left(\tiny\begin{array}{c} 1 \\ 1 \\ 1 \end{array}\right)$ (of which, according to Fact~4, there are as many as there are permutations of three columns chosen from six columns). {\em The case $m=4$.} Suppose first that $n\geq 5$. If a column of $A$ has either at least three 0's or at least three 1's, then we can consider the three rows that form a matrix having the column $\left(\tiny\begin{array}{c} 0 \\ 0 \\ 0 \end{array}\right)$ or $\left(\tiny\begin{array}{c} 1 \\ 1 \\ 1 \end{array}\right)$. The length of such a matrix, according to Fact~3, does not exceed 4, and the columns of $A$ in this case are those that have exactly two 0's and two 1's. It is easy to see that any combination of such columns gives no occurrences of the pattern \aaaa, and there are six such columns. Thus, $c_{4,5}=c_{4,6}=6!=720$. Now let $n=4$. If any column of $A$ has exactly two 0's and two 1's, the number of ways to choose $A$ in this case is $\frac{6!}{2!}=360$. If some column has only 0's or only 1's, say only 0's, then the number of columns does not exceed 2, since the other columns can not have more than one $0$, and two such columns must have an occurrence of the pattern \aaaa. So, we need only consider the case when there is a column in $A$ having three 0's or three 1's. Suppose there is a column with three 0's. In this case we can assume, permuting rows or columns if necessary, that $A_{1,1}=A_{2,1}=A_{3,1}=0$ and $A_{4,1}=1$. If we consider the submatrix that is formed by the first three rows and the four columns, then according to the considerations of the case $m=3$, this submatrix is a permutation of the columns $\left(\tiny\begin{array}{c} 0 \\ 1 \\ 1 \end{array}\right)$, $\left(\tiny\begin{array}{c} 1 \\ 0 \\ 1 \end{array}\right)$, and $\left(\tiny\begin{array}{c} 1 \\ 1 \\ 0 \end{array}\right)$. Obviously, the entries $A_{4,2}A_{4,3}A_{4,4}$ form a word that has at most one 1. Thus, there are 4 ways to choose this word, and then we can permute columns and rows in $4!\cdot4!$ ways to get different $4\times4$ matrices avoiding \aaaa. So, in this case we have $4\cdot24\cdot24=2304$ different matrices. Finally, we need to count the number of matrices that have a column with three 1's and have no columns with three 0's. We use the same considerations as in the case of three 0's, but now we observe that the entries $A_{4,2}A_{4,3}A_{4,4}$ can only form the word 111 (otherwise we have a column with three 0's or an occurrence of the pattern \aaaa). Thus this case gives us $4!\cdot 4!=576$ different matrices. So the total the number of $4\times4$ matrices avoiding the pattern \aaaa is given by $360+2304+576=3240$. {\em The case $m\geq 5$.} The first row of $A$ has either at least three 0's or at least three 1's. In either case, if we consider the three rows of $A$ that begin with the same letter, we have that, according to Fact~3, the length of these rows does not exceed 4, since otherwise they will contain the pattern \aaaa. Thus, $A$ must have at most four columns in order to avoid \aaaa. \end{proof} \begin{center} \begin{tabular}{ccc} \hline\\ &\begin{footnotesize} \begin{tabular}{c|c|c|c|c|c|c|c|} %\hline\\ &2&3&4&5&6&7&$\cdots$\\ \hline 2&14&44&128&352&928&2368&$\cdots$\\ 3&44&168&408&720&720&0&\\ 4&128&408&3240&720&720&&\\ 5&352&720&720&0&&&\\ 6&928&720&720&&&&\\ 7&2368&0&&&&&\\ $\vdots$&$\vdots$&&&&&&\\ %\hline \end{tabular} \end{footnotesize}&\\ \\ &The numbers $c_{m,n}$ for the pattern \aaaa&\\ \\ \hline \end{tabular} \end{center} \begin{remark} From the above proposition we can deduce some known (and easy) facts about the bipartite Ramsey numbers of $K_{2,2}$. First of all, the pattern \aaaa is eventually unavoidable; moreover, the vanishing border $V\left(\mbox{\aaaa}\right)$ is $\{(3,7),(5,5),(7,3)\}$ (equivalently, the ``bipartite Ramsey set $\beta(K_{2,2},K_{2,2})$'' is $\{(3,7),(5,5)\}$, in the language of \cite{hahame}), and $\displaystyle b\left(\mbox{\aaaa}\right)=b(K_{2,2}) = 5$ and $b'\left(\mbox{\aaaa}\right) = b'(K_{2,2}) = 10$. All these results are contained explicitly or implicitly in \cite{hahame}, and any credit for the computation of $b(K_{2,2})$ should probably be attributed to Beineke and Schwenk \cite{beisch}. \end{remark} \begin{prop}\label{gener_aaaa} Let $c_{m,n}$ denote the number of matrices that avoid the pattern $\mathcal{O}_{\ell,k}$. If we set $\overline{m} = 2\ell -1, \ \bar{n} = 2(k-1){2\ell -1\choose \ell} +1$, we have that \begin{description} \item[(1)] $c_{m,n}>0$ for $m < \overline{m}$; \item[(2)] $c_{\overline{m},n} = 0 \Leftrightarrow n \geq \bar{n}$; \item[(3)] $c_{m,n} = 0$ for $m > \overline{m}, n \geq \bar{n}$. \end{description} In particular, $\mathcal{O}_{\ell,k}$ is eventually unavoidable and $(\overline{m},\bar{n})$ belongs to its vanishing border. \end{prop} \begin{proof} Suppose $A=(a_{i,j})$ is a matrix of dimensions $\overline{m} \times \bar{n}$. By the Dirichlet Principle, each column of $A$ has either at least $\ell$ 1's or at least $\ell$ 0's (but not both). For $p=0,1$, let $C_p$ be the set of indices $j$ such that column $j$ has a majority of $p$'s. Again by the Dirichlet principle, there is some $q \in \{0,1\}$ such that $|C_q| \geq \lceil\frac{\bar{n}}{2}\rceil =(k-1){2\ell -1\choose \ell} + 1$. Then for all $j \in C_q$, there exists some subset $S_j \subseteq [\overline{m}]$ with $|S_j|=l$ such that for all $i \in S_j$, we have $a_{i,j}=q$. Since the total number of subsets of $[\overline{m}]$ with $l$ elements is ${2\ell-1 \choose l}$, again by the Dirichlet principle our choices of $S_i$ must agree for at least $k$ columns, that is, $S_i = S \ \forall \ i \in T$ for some $S \subseteq [\overline{m}]$ and $T \subseteq C$ with $|T|=k$. Then $S \times T$ is an occurrence of $\mathcal{O}_{\ell,k} $. Thus $c_{\overline{m},\bar{n}}=0$. This proves (3) and the backward implication in (2). On the other hand, for any $m \leq 2\ell -2$ and any $n$, a matrix of dimensions $(\overline{m}-1) \times \bar{n}$ avoiding $\mathcal{O}_{\ell,k}$ can easily be constructed by allowing at most $\ell -1$ $0$'s and $\ell -1$ $1$'s in each column. This proves (1). Moreover, the matrix of dimensions $\overline{m} \times (\bar{n} -1)$ whose columns all have precisely $\ell$ $0$'s or $\ell$ $1$'s, and such that for all $S \subseteq [\overline{m}]$ with $|S|=\ell$ there are precisely $k$ columns with $1$'s precisely on rows indexed by $S$, and precisely $k$ (other) columns with $0$'s precisely on rows indexed by $S$, for a total of $2(k-1){2\ell-1\choose \ell}$ columns, avoids the pattern $\mathcal{O}_{\ell,k}$. This concludes the proof of (2). Thus both $c_{\overline{m}-1,\bar{n}}$ and $c_{\overline{m},\bar{n}-1}$ are positive and $(\overline{m},\bar{n}) \in V(\mathcal{O}_{\ell,k})$. \end{proof} \begin{cor} \label{bounds} % Let $f(\ell,k)= 2(k-1){2\ell-1 \choose \ell} + 1$. Let $\ell,k$ be positive integers. We have that $b(\mathcal{O}_{\ell,k}) = b(\mathcal{O}_{k,\ell})$ and $b'(\mathcal{O}_{\ell,k}) = b'(\mathcal{O}_{k,\ell})$. Assuming without loss of generality that $\ell \leq k$, the following upper bounds hold \begin{equation} \label{latter} b(K_{\ell,k}) \leq b(\mathcal{O}_{\ell,k}) \leq %\min\{f(\ell,k),f(k,l)\} = \left\{ \begin{array}{ccc} %&{\mathrm{ if }} & k \leq \ell \\ 2(k-1){2l-1 \choose l}+1 %& {\mathrmrm{ if }} & k \geq \ell \end{array}\right. \end{equation} \begin{equation} \label{former} b'(K_{\ell,k}) \leq b'(\mathcal{O}_{\ell,k}) \leq 2(k-1){2l-1 \choose l}+2\ell. \end{equation} \end{cor} \begin{proof} Note that a matrix avoids $\mathcal{O}_{\ell,k}$ if and only if its transpose avoids $\mathcal{O}_{k,\ell}$. From this it follows that $V(\mathcal{O}_{\ell,k}) = \{ (b,a) \ | \ (a,b) \in V(\mathcal{O}_{k,\ell})\} $. As observed in $\cite{hahame}$, for any bipartite graph $G$, $b(G) = \min\{\max\{a,b\} \ | \ (a,b) \in V(G)\}$ and $b'(G) = \min\{a+b \ | \ (a,b) \in V(G)\}$, and the analogous statements hold for any pattern $P$ instead of a graph $G$. In particular, since the sum and the maximum of two variables are commutative, these minima coinicide when taken over the two vanishing borders. Moreover, since $(\overline{m},\overline{n}) \in V(\mathcal{O}_{\ell,k})$ (with $\overline{m},\overline{n}$ defined as in Proposition \ref{gener_aaaa}), $\overline{m} + \overline{n}$ and $\max\{\overline{m},\overline{n}\} $ are upper bounds for $b'(\mathcal{O}_{\ell,k})$ and $b(\mathcal{O}_{\ell,k})$ respectively. The former simplifies to the rightmost expression in (\ref{former}), and the latter, with the assumption $\ell \leq k$, to the rightmost expression in (\ref{latter}). The inequalities $b(K_{\ell,k}) \leq b(\mathcal{O}_{\ell,k})$ and $b'(K_{\ell,k}) \leq b'(\mathcal{O}_{\ell,k})$ follow from the trivial observation that if the edges of $K_{m,n}$ can be coloured to avoid a monochromatic copy of $K_{\ell,k}$, the corresponding binary $m \times n$ matrix avoids $\mathcal{O}_{\ell, k}$ (as well as $\mathcal{O}_{k,\ell}$). \end{proof} \begin{remark} We have no reason to believe that the above bounds are good, and we expect that they can be improved. Good bounds are known for $b(K_{\ell,k})$; see for example \cite{thomason}. The Ramsey number $b'(K_{\ell,k})$ seems to have received less attention, but an obvious upper bound is given by $2b(K_{\ell,k})$. The question arises as to how big the gap between $b(K_{\ell,k})$ and $b(\mathcal{O}_{\ell,k})$ is (and analogously for $b'$). This issue runs a parallel with the conjecture of Simonovits \cite{simonovits} that ${\mathrm{ex}}^*(n,L) = O(\mathrm{ex}(n,L))$, where for a bipartite graph $L$, $\mathrm{ex}(n,L)$ denotes the smallest number of edges of $K_{m,n}$ needed to ensure that the induced subgraph contains a copy of $L$, while $\mathrm{ex}^*(n,L)$ stands for the minimum number of $1$'s in an $m \times n$ matrix that ensures the existence of a ``submatrix'' whose entries all are 1, and equivalent to the bipartite adjacency matrix $B$ of $L$. The issue of equivalence is irrelevant in our context because our bipartite graphs are complete. The parallel lies in the distinction between the ``ordered'' and ``unordered'' versions: whether we care that the $\ell$ prescribed vertices in the copy of $K_{\ell,k}$ are among the prescribed $m$ of $K_{m,n}$ or not. Note however that there is a crucial difference between the two problems: we are here talking of excluding only $(\ell \times k)$-minors (for complete bipartite $L$) \emph{whose entries are all 1}, but not those whose entries are all $0$'s, which also need to be excluded to avoid the pattern $\mathcal{O}_{\ell,k}$ (or a monochromatic copy of $K_{\ell,k}$). Also note that, if $f(x) = 2x-1 $ and $g(x,y) = 2(y-1){2x-1\choose x}$, both $(f(\ell),g(\ell,k))$ and $(g(k,l),f(k))$ belong to the vanishing border of $\mathcal{O}_{\ell,k}$, and both points can be used to derive upper bounds; in Corollary \ref{bounds} we have given the stronger one, with the assumption that $\ell \leq k$. \end{remark} %=========================================== \subsection*{3.2 Avoidance of the patterns \aaab, \abab, and \abba} In this section we see how the transfer matrix method can be used to obtain, for fixed $m$, an explicit formula for the number of binary matrices of dimensions $m\times n$ avoiding a pattern from the set $S=\{$\aaab,\abab,\abba$\}$. For fixed $m\geq 1$ and $p\in S$, we denote by $\BB^{m,*}$ ($\BB^{m,n}$) the set of all binary matrices with $m$ rows (respectively, $m$ rows and $n$ columns), and define an equivalence relation $\sim_p$ on $\BB^{m,*}$ by $A \sim_p B$ if and only if for all vectors $u \in\BB^{m,1}$ we have $$A | u\mbox{ avoids } p \ \ \Longleftrightarrow \ \ B | u \mbox{ avoids } p,$$ where the notation $A | u$ stands for the matrix obtained by concatenating the vector $u$ to the matrix $A$. For example, if $p$ is \aaab, $m=3$, $A=\left(\begin{array}{lll} 1&0&1\\0&1&1\\0&0&0\end{array}\right)$ and $B=\left(\begin{array}{ll} 1&0\\0&1\\0&0\end{array}\right)$, then $A\sim_p B$, since the entries in the third column in $A$ are never involved in an occurrence of $p$. Let $\EE_p$ be the set of equivalence classes of $\sim_p$. We denote the equivalence class of a binary matrix $A$ by $\overline{A}$. For example, the equivalence classes of $\sim_p$ for $p=$\aaab and $m=2$ are $$\fstate,\quad \overline{\left(\begin{array}{l}0\\0\end{array}\right)},\mbox{ and } \overline{\left(\begin{array}{ll}0&0\\0&1\end{array}\right)}$$ where $\epsilon$ stands for the empty matrix. \begin{defin}\label{aut} Given a positive integer $m$ and a pattern $p$ we define a { finite automaton}\footnote{For a definition of a finite automaton, see \cite{ASU} and references therein.}, $\AA_p=(\EE_p, \delta, \fstate , \EE_p \setminus\{ \overline{p}\})$, by the following \begin{itemize} \item the set of {\em states}, $\EE_p$, consists of the equivalence-classes of $\sim_p$; \item $\delta : \EE_p \times \BB^{m,1} \rightarrow \EE_p$ is the {\em transition function} defined by $\delta(\overline{A},u)=\overline{A|u}$; \item $\fstate$ is the {\em initial state}; \item and all states but $\overline{p}$ are {\em final states}. \end{itemize} \end{defin} We wish to enumerate the number of binary matrices of size $m\times n$ avoiding the pattern $p$. We shall identify $\AA_p$ with the directed graph\footnote{Here we are allowing loops and multiple edges, and following the terminology of \cite{diestbook}.} with vertex set $\EE_p \setminus \{\overline{p}\}$ and with a (labelled) edge $\stackrel{u}{\longrightarrow}$ from $\overline{A}$ to $\overline{B}$ whenever $A|u \sim_p B$. Note that, whenever we have an edge from $\overline{A}$ to $\overline{B}$, the outdegree of $\overline{B}$, that is, the number of binary vectors $u \in \BB^{m,1}$ such that $B|u \not \sim_p B$ but $B|u$ still avoids $p$, is strictly less than the outdegree of $\overline{A}$. Hence, we may choose binary matrices $\{A^{(i)}\}_{i=1}^e$ as representatives of the vertices (equivalence classes), indexed in such a way that if $i1$ letters and simultaneously avoiding different sets of patterns. For example, the following result is true. \begin{cor} We have that {\rm(i)} the number of matrices of size $3\times n$ on $3$ letters avoiding the pattern \abba is given by $$\begin{array}{l} \frac{1}{2}(1582178-269829n+6241n^2)13^{n-2}\\ \qquad\qquad\qquad-(673920-61130n-4427n^2-106n^3-n^4)12^{n-2};\end{array}$$ {\rm(ii)} the number of binary matrices of size $2\times n$ simultaneously avoiding the patterns \aaab and \abba is given by $$2\cdot3^n-2^n.$$ \end{cor} {\bf Acknowledgements}. The authors are grateful to the referee for the careful reading of the manuscript and shortening the proof of Proposition~\ref{refaa}. %----------------------------------- \begin{thebibliography}{10} \bibitem{ASU} {\sc A. V. Aho, R. Sethi, J.D. Ullman}. \emph{Compilers: principles, techniques and tools}, Addison-Wesley, Reading, Mass., 1986. \bibitem{beisch} {\sc L.W. Beineke, A.J. Schwenk}. On a bipartite form of the Ramsey problem, \emph{Proc. Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975)} 17--22. Congressus Numerantium XV, \emph{Utilitas Math., Winnipeg, Man., 1976}. \bibitem{thes:burst} {\sc A. Burstein}. Enumeration of words with forbidden patterns, Ph.D. thesis, University of Pennsylvania, 1998. \bibitem{buma1} {\sc A. Burstein, T. Mansour}. Words restricted by patterns with at most 2 distinct letters. Permutation patterns (Otago, 2003). \emph{Electron. J. Combin.} {\bf9} (2002/2003), no. 2, Research paper 3, 14pp (electronic). \bibitem{buma2} {\sc A. Burstein, T. Mansour}. Counting occurrences of some subword patterns. \emph{Discrete Math. Theor. Comput. Sci.} {\bf6} (2003), no. 1, 1--11 (electronic). \bibitem{buma3} {\sc A. Burstein, T. Mansour}. Words restricted by 3-letter generalized multipermutation patterns. \emph{Ann. Combin.} {\bf7} (2003), no. 1, 1--14. \bibitem{diestbook} {\sc R. Diestel}. \emph{Graph Theory}, Springer-Verlag, New York, 1997. \bibitem{hahame} {\sc F. Harary, H. Harborth, I. Mengersen}. Generalized Ramsey Theory for Graphs XII: Bipartite Ramsey Sets, \emph{Glasgow Math. J.} {\bf22} (1981), 31--41. \bibitem{simsch} {\sc R. Simion, F.W. Schmidt}. Restricted Permutations, \emph{Europ. J. Combin.} {\bf6} (1985), 383--406. \bibitem{simonovits} {\sc M. Simonovits}. Paul {Erd\H{o}s}' Influence on Extremal Graph Theory, \emph{The Mathematics of Paul {Erd\H{o}s}} II, (Graham, Ne\v{s}et\v{r}il eds.) 148--192. Algorithms Combin. {\bf14}, Springer, Berlin, 1997. \bibitem{Stanley1} {\sc R.~Stanley}. \emph{Enumerative Combinatorics}, Volume {\bf 1}, Cambridge University Press, Cambridge, 1997. \bibitem{thomason} {\sc A. Thomason}. An upper bound for some Ramsey numbers, \emph{J. Graph Theory} {\bf12} (1988), no. 4, 509--517. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: Primary 05A05, 05A15; Secondary 05D10, 05C50. \noindent \emph{Keywords: } Binary matrices, Ramsey Theory, Forbidden subsequences, Forbidden submatrices, Transfer matrix. \bigskip \hrule \bigskip \noindent (Concerned with sequence \seqnum{A027649,A006234,A007466}.) \bigskip \hrule \bigskip %\vspace*{+.1in} %\noindent %Received September 6 2004; revised version received January 3 %2005. Published in {\it Journal of Integer Sequences}, January 10 %2005. %\bigskip %\hrule %\bigskip %\noindent %Return to %\htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}. %\vskip .1in % \end{document}