\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\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{psfig}
\usepackage{graphics,amsmath,amssymb,amsthm}
\usepackage{amsfonts}
\usepackage{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}}}
\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 \\
Department of Mathematics \\
University of Kentucky \\
Lexington, KY 40506-0027 \\
USA \\
\href{mailto:kitaev@ms.uky.edu}{\tt kitaev@ms.uky.edu}\\
\ \\
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.} \\
Department of Mathematics \\
University of Haifa \\
31905 Haifa \\
Israel\\
\href{mailto:toufik@math.haifa.ac.il}{\tt toufik@math.haifa.ac.il}\\
\ \\
Antoine Vella \\
Department of Combinatorics and Optimization \\
University of Waterloo \\
Waterloo, Ontario N2L 3G1 \\
Canada
\href{mailto:avella@math.uwaterloo.ca}{\tt avella@math.uwaterloo.ca}
\\
\end{center}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{lemma}{Lemma}[section]
% \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}
\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}
{\rm 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}
{\rm 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}. The first version of this paper was
written during the three authors stay at Chalmers University of
Technology. The authors want to express their gratitude to
Chalmers for the support.
%-----------------------------------
\begin{thebibliography}{10}
\bibitem{ASU}
A. V. Aho, R. Sethi, and J. D. Ullman, \emph{Compilers:
Principles, Techniques and Tools}, Addison-Wesley, Reading, Mass.,
1986.
\bibitem{beisch}
L. W. Beineke and 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} A. Burstein, Enumeration of words with
forbidden patterns, Ph.D. thesis, University of Pennsylvania,
1998.
\bibitem{buma1} A. Burstein and T. Mansour,
\href{http://www.combinatorics.org/Volume_9/Abstracts/v9i2r3.html}{Words restricted by
patterns with at most 2 distinct letters}, Permutation patterns
(Otago, 2003). \emph{Electron. J. Combin.} {\bf9} (2) (2002/2003)
\#R3, 14pp. (electronic).
\bibitem{buma2} A. Burstein and T. Mansour,
\href{http://dmtcs.loria.fr/volumes/abstracts/dm060101.abs.html}{Counting occurrences of some subword
patterns}, \emph{Discrete Math. Theor. Comput. Sci.} {\bf6} (2003),
no. 1, 1--11 (electronic).
\bibitem{buma3} A. Burstein and T. Mansour, Words restricted by
3-letter generalized multipermutation patterns. \emph{Ann.
Combin.} {\bf7} (2003), no. 1, 1--14.
\bibitem{diestbook}
R. Diestel, \emph{Graph Theory}, Springer-Verlag, New York,
1997.
\bibitem{hahame} F. Harary, H. Harborth, and I. Mengersen,
Generalized Ramsey Theory for Graphs XII: Bipartite Ramsey Sets,
\emph{Glasgow Math. J.} {\bf22} (1981), 31--41.
\bibitem{simsch}
R. Simion and F. W. Schmidt, Restricted Permutations,
\emph{Europ. J. Combin.} {\bf6} (1985), 383--406.
\bibitem{simonovits} 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}
R.~Stanley, \emph{Enumerative Combinatorics}, Volume {\bf
1}, Cambridge University Press, Cambridge, 1997.
\bibitem{thomason} A. Thomason, An upper bound for some Ramsey
numbers, \emph{J. Graph Theory} {\bf12} (1988), 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 sequences
\seqnum{A027649},\seqnum{A006234}, and \seqnum{A007466}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received December 8 2004; revised version received April 7 2005.
Published in {\it Journal of Integer Sequences}, April 7
2005.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}.
\vskip .1in
\end{document}