
%%%%%%%%%%%%%%%%%%%%%%%%%%%LaTeX%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\documentclass[12pt]{article}
\documentclass[12pt]{article}
\usepackage{e-jc}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{amssymb}
%\def\emph{#1}\textbf{#1}

\newenvironment{E}{\begin{equation}}{\end{equation}}
\def\proof{\noindent{\bf Proof: }}
\def\qed{\,\,\,{\vrule height7pt width6pt depth0pt}\hfil}
\def\forb{{\hbox{forb}}}
\def\0{{\bf 0}}
\def\1{{\bf 1}}
\def\Av{{\mathrm{Avoid}}}
\def\ext{{\mathrm{ext}}}
\def\rep{{\hbox{Rep}}}
\def\req{{\hbox{req}}}
\newcommand{\linelessfrac}[2]{\genfrac{}{}{0pt}{}{#1}{#2}}
\newcommand{\ncols}[1]{\| #1 \|}
\newcommand{\rf}[1]{(\ref{#1})}
\newcommand{\srf}[1]{Section \ref{#1}}
\newcommand{\rrf}[1]{Remark \ref{#1}}
\newcommand{\trf}[1]{Theorem \ref{#1}}
\newcommand{\lrf}[1]{Lemma \ref{#1}}
\newcommand{\crf}[1]{Corollary \ref{#1}}
\newcommand{\drf}[1]{Definition \ref{#1}}
\newcommand{\corf}[1]{Conjecture \ref{#1}}
\newcommand{\prf}[1]{Proposition \ref{#1}}
\setlength{\textwidth}{157mm}
\setlength{\textheight}{217mm}
\setlength{\evensidemargin}{0pt}
\setlength{\oddsidemargin}{0pt}
\setlength{\topmargin}{0pt}
\newcommand{\z}{\mbox{\sf Z\hspace{-.4em}Z}}
\newcommand{\q}{\mbox{\sf
\hspace{.18em}l\hspace{-.4em}Q}}
\newcommand{\f}{\mbox{\sf l\hspace{-.13em}F}}
\newcommand{\cc}{\mbox{\s
\newcommand{\ne1}{\ensuremath{\hspace{.2em}_{^{.^{.^{1^{.^.}}}}}}}
\hspace{.1em}l\hspace{-.4em}\rm C}}
\newcommand{\ep}{\rule{.5em}{.6em}}
\newcommand{\dne}{\ensuremath{\hspace{.2em}_{^{.^{.^{.^{.^.}}}}}}}
\newcommand{\dse}{\ensuremath{\hspace{.2em}\mbox{\raisebox{-.1em}
{$^{_{._{._{._{._.}}}}}$}}}}
\newcommand{\dd}{\ensuremath{\mbox{\tiny $\overset{\cdot}{\overset
{\cdot}{\underset{\cdot}{\underset{\cdot}{.}}}}$}}}
\newcommand{\dhh}{\ensuremath{\: \mbox{\tiny $^{\cdot \cdot \cdot
\cdot \cdot}$}\:}}
\newcommand{\lne}{\ensuremath{\hspace{.2em}_{^{.^{.^{1^{.^.}}}}}}}
\newcommand{\one}{\ensuremath{\hspace{.2em}\mbox{\raisebox{-.8em}
{$^{^{.^{.^{0^{.^.}}}}}$}}}}
\newcommand{\lse}{\ensuremath{\hspace{.2em}\mbox{\raisebox{-.1em}
{$^{_{._{._{1_{._.}}}}}$}}}}
\newcommand{\ose}{\ensuremath{\hspace{.2em}\mbox{\raisebox{-.1em}
{$^{_{._{._{0_{._.}}}}}$}}}}
\newcommand{\od}{\ensuremath{\mbox{\tiny $\overset{\cdot}
{\overset{\cdot}{\underset{\cdot}{\underset{\cdot}{0}}}}$}}}
\newcommand{\ld}{\ensuremath{\mbox{\tiny $\overset{\cdot}
{\overset{\cdot}{\underset{\cdot}{\underset{\cdot}{1}}}}$}}}
\newcommand{\lh}{\ensuremath{\: \mbox{\tiny
$^{\cdot \cdot 1 \cdot \cdot}$}\:}}
\newcommand{\oh}{\ensuremath{\: \mbox{\tiny
$^{\cdot \cdot 0 \cdot \cdot}$}\:}}
\def\fo{\hbox{forb}}
\def\arc{{\!\!\rightarrow\!\!}}
\def\Z{{\cal Z}}
\def\x{{\bf x}}
\renewcommand{\l}{\ell}
\newtheorem{thm}{Theorem}[section]
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{defn}[thm]{Definition}
\newtheorem{remark}[thm]{Remark}
\newtheorem{prob}[thm]{Problem}
\newtheorem{st}{Step}
\newtheorem{note}{Note}
\usepackage{amssymb}
\usepackage{amsmath}
\title{A Survey of  Forbidden Configuration Results}
\author{R.P.  Anstee\thanks{Research supported in part by
NSERC} 
  \\Mathematics Department\\The University of British Columbia\\Vancouver,
B.C. Canada V6T 1Z2\\ {\small\texttt{anstee@math.ubc.ca}}
\\\mbox{\ }}


\begin{document}
\maketitle 
\nocite{*}
\begin{abstract} Let $F$ be a $k\times \l$ (0,1)-matrix. We say a (0,1)-matrix $A$ has $F$ as a \emph{configuration} if there is a submatrix of $A$ which is a row and column permutation of $F$. In the language of sets, a configuration is a \emph{trace} and in the language of hypergraphs a configuration is a \emph{subhypergraph}.

We define a matrix to be {\it simple} if it is a (0,1)-matrix with no repeated columns. Let $F$ be a given $k\times \l$ (0,1)-matrix.  The matrix $F$ need not be simple. We define $\forb(m,F)$ as the maximum number of columns of any simple $m$-rowed matrix $A$ which do not contain $F$ as a configuration.  Thus if $A$ is an $m\times n$ 
simple matrix which has no submatrix which is a row and column permutation
of $F$ then $n\le\forb(m,F)$. Or alternatively if $A$ is an $m\times (\forb(m,F)+1)$ 
simple matrix then $A$ has a submatrix which is a row and column permutation
of $F$. We call $F$ a \emph{forbidden configuration}. 

The fundamental result is due to Sauer, Perles and Shelah, Vapnik and Chervonenkis. For $K_k$ denoting the $k\times 2^k$ submatrix of all 
(0,1)-columns on $k$ rows, then $\forb(m,K_k)=\binom{m}{k-1}+\binom{m}{k-2}+\cdots \binom{m}{0}$.
We seek asymptotic results for $\forb(m,F)$ for a fixed $F$ and as $m$ tends to infinity . A conjecture of Anstee and Sali predicts the asymptotically best constructions from which to derive the asymptotics of $\forb(m,F)$. The conjecture has helped guide the research and has been verified for $k\times \l$ $F$ with $k=1,2,3$ and for simple $F$ with $k=4$ as well as other cases including
 $\l=1,2$. We also  seek exact values for $\forb(m,F)$. 
\vskip 10 pt
Keywords: extremal set theory, extremal hypergraphs, (0,1)-matrices, forbidden configurations, trace, VC-dimension, subhypergraph, shattered set.
\end{abstract}

%section 1 intro including definition of forb(m,F)
%section 2 variations
%section 3 Conjecture
%section 3 the case k=2
%section 4 the case k=3
%section 5 the case l=2
%section 6 simple and k=4
%section 7 simple and k=5
%section 8 what is missing if F is avoided
%section 9 boundary m^{k-1} and m^k
%section 10 what is missing
%section 11 induction
%section 12 shifting
%section 13 graph theory
%section 14 linear algebra
%section 15 strong stability

\section{Introduction}\label{intro}




The study of forbidden configurations is a problem in extremal set
theory. It is convenient to use the language of matrix theory. 
We define a {\it simple} matrix as a (0,1)-matrix with no repeated columns.
Such an $m\times n$ simple matrix $A$ can be thought of a family ${\cal A}$ of $n$
subsets of $[m]=\{1,2,\ldots ,m\}$ with the rows indexing the elements
and the columns indexing the subsets. Let $\ncols{A}$ denote the number of columns in $A$ (which is $|{\cal A}|$). 
Assume we are given a $k\times \l$ (0,1)-matrix $F$. We say that a matrix $A$
has
a \emph{configuration} $F$ if a submatrix of $A$ is a row and column
permutation of $F$ and so $F$ is referred to as a \emph{configuration}
of $A$ (sometimes called \emph{trace} in the language of sets). 

The reader may ask of the importance of the  configuration idea in combinatorial investigations. I feel it is one of a few possible basic notions of substructure and it has arisen  in applications though admittedly not as frequently as some other substructures. The investigations into the extremal problem of the maximum number of edges in an $n$ vertex graph with no subgraph $H$ originated with Erd\H os and Stone \cite{ES} and Simonovits \cite{Simon} and has a large and illustrious literature. There are several ways to generalize to the hypergraph setting. Typically one considers \emph{simple hypergraphs}, those with no repeated edges. One can consider a $r$-uniform (simple) hypergaph $H$ and forbid a given \emph{subhypergraph} $H'$, itself a  $r$-uniform (simple) hypergraph.  Or one can extend to general hypergraphs and forbid a given \emph{subhypergraph} where it is now natural to allow repeated edges in the forbidden object. This latter problem in the language of matrices is our focus. It is to be noted that hypergraphs are sometimes not allowed to have the empty edge
 whereas our simple matrices naturally allow the column of 0's.
 
 There are interesting connections of results about forbidden configuration to other results.  Some related problems (VC-dimension, forbidden submatrices, patterns, covering arrays etc.) are given in Section~\ref{variations} as well as the relations between them.  



\begin{defn}
For two  $(0,1)$-matrices $F$ and $A$, we say that $F$ is a \emph{configuration} in $A$, and write $F \prec A$ if there is a row and column permutation of $F$ which is a submatrix of $A$. We say $A$ \emph{has no configuration} $F$ (or $F\not\prec A$) if $F$ is not a configuration in $A$. Let $\Av(m,F)$ denote the set of all $m$-rowed simple matrices with no configuration $F$.
\end{defn}


Our main extremal problem is to compute
  $$\forb(m,F)=\max_{A}\{\ncols{A}\ :\ A\in\Av(m,F)\}.$$
Thus  $\forb(m,F)$ is the smallest value (depending on $m$ and $F$) so
that if $A$ is a simple $m\times n$ matrix and  $A$ has no
configuration $F$ then $n\le \forb(m,F)$. Alternatively $\forb(m,F)$
is the smallest value so that if $A$ is an $m\times
(\forb(m,F)+1)$ simple  matrix then $A$ must have a configuration $F$.  This survey mostly considers a single given fixed forbidden configuration $F$ (though variations to forbidden families of configurations are in Section~\ref{variations}) and considers the asymptotics of $\forb(m,F)$ as we let $m$ grow.

One could define the equivalence class of matrices under row and column permutations. Let $\tilde{F}$ denote the equivalence class of matrices derived from $F$ by taking all row and column permutations of $F$. Thus a matrix $A$ has a configuration $F$ if $A$ has a submatrix in $\tilde{F}$. 
We often blur the distinction between a matrix $F$ and the related equivalence class $\tilde{F}$. A matrix $F$ is referred to as a 
{\it configuration} when we wish to consider whether  another matrix $A$ has $F$ as a configuration.

\begin{remark} Let $A^c$ denote the
0-1-complement of $A$. Then $\forb(m,F^c)=\forb(m,F)$.\end{remark}

\begin{remark}\label{subconfig} If $F'\prec F$ (i.e.  $F$ has
a configuration  $F'$), then $\forb(m,F')\le \forb(m,F)$. \end{remark}

When giving results it is often convenient to note when we discover $\forb(m,F')=\forb(m,F)$ where $F'\prec F$. Typically one has a construction working for $F'$ (a simple matrix $A$ with no configuration $F'$) which then necessarily works for $F$ and we have a bound for $\forb(m,F)$ which certainly applies to $\forb(m,F')$. Equality (or asymptotic equality) of the construction for $F'$ and the bound for $F$ then yields equality  (or asymptotic equality) for
$\forb(m,F')$ and $\forb(m,F)$ as well as for any matrices $F''$  with $F'\prec F''\prec F$).   The following defines some standard configurations.




\begin{defn} \label{basicmatrices}
Let $K_k$ be the
$k\times 2^k$ simple matrix of all possible (0,1)-columns on $k$ rows. Let  
$K_k^s$ be  the $k\times \binom{k}{s}$ simple matrix of all
possible columns of column sum $s$.
Let $\1_a\0_b$ denote the $(a+b)\times 1$ vector of $a$ 1's on top of $b$ 0's and for convenience
we let $\1_a$ denote the $a\times 1$ vector of $a$ 1's and $\0_b$ denote the $b\times 1$ vector of $b$ 0's.
Let $I_k$ be the $k\times k$ identity matrix (equivalent to $K_k^1$). Let $I_k^c$ be  the (0,1)-complement of the $k\times k$ identity matrix  (equivalent to $K_k^{k-1}$). Let $T_k$ be   the $k\times k$ triangular matrix $T_k$ whose $i,j$ entry is 1 if and only if $i\le j$. \end{defn}

We have a number of results for 2-columned $F$ and find the following notation useful.
\begin{defn}\label{2-rowed}
We define $F_{a,b,c,d}$ as the $(a+b+c+d)\times 2$ matrix consisting of $a$ rows $[1\,1]$, $b$ rows $[1\,0]$, $c$ rows $[0\,1]$ and $d$ rows $[0\,0]$.\end{defn}

We use the notation
$[A|B]$  to denote the matrix obtained from concatenating the two
matrices $A$ and $B$. We use the notation $k\cdot A$ to denote the
matrix $[A|A|\cdots |A]$ consisting of $k$ copies of $A$ concatenated
together. We give precedence to the operation $\cdot$
(multiplication) over concatenation so that for example $[2\cdot
A|B]$ is the matrix consisting of the concatenation of $B$ with the
concatenation of two copies of $A$.  


Some useful set notation is:
$$[m]=\{1,2,\ldots ,m\},\,\,\,
2^{[m]}=\{S\subseteq [m] \,:\,0\le|S|\le m\},\,\,\,
\binom{[m]}{k}=\{S\subseteq [m] \,:\,|S|=k\}.$$
Thus $K_k$ corresponds to $2^{[k]}$ and $K_k^s$ corresponds to
$\binom{[k]}{s}$. Considering simple $m\times n$ matrix $A$ as an element-set incidence matrix, $A$ can be thought of as a family of sets:
$${\mathcal A}\subseteq 2^{[m]},\qquad |{\mathcal A}|=n.$$
For a subset of rows $S$, we define $A|_S$ to be the submatrix of $A$ formed by the rows of $S$. Thus if $F$ is $k$-rowed, then
$F\prec A$ if there is some $S\in\binom{[m]}{k}$ with $F\prec A|_S$. We could also define
$${\mathcal A}|_S=\{B\cap S\,:\,B\in{\mathcal A}\},$$
but note that you should choose between the set system ${\mathcal A}|_S$ and the multiset which would correspond to $A|_S$.   Now $A$ being simple yields that ${\mathcal A}$ is a set system but we do not expect either $A|_S$ or a configuration $F$ to be simple . 
A \emph{$k$-uniform} set system $\mathcal F$ has ${\mathcal F}\subseteq\binom{[m]}{k}$. The  use of set notation  is sometimes preferable. In that setting a forbidden configuration is called a \emph{trace}.  

\vskip 5pt
There are alternate ways of describing simple matrices that could be considered. 
Another equivalent notation is to consider a square free integer
$x=\prod_{i=1}^mp_i$ and then consider all possible divisors of $x$. This notation was used in \cite{AA}. One can generalize to all divisors of some given but arbitrary integer. See this multiset version in Section~\ref{variations}.


\begin{defn}\label{product}Let $A$ be an $m_1\times n_1$ simple matrix and let $B$ be an $m_2\times n_2$ simple matrix. Then $A\times B$ denotes the 
$(m_1+m_2)\times (n_1n_2)$ simple matrix each column consisting of a column of $A$ placed on a column of $B$ and this is done in all possible ways.\end{defn}

$$\hbox{e.g. } K_3^1\times T_3
=\left[\begin{array}{ccc}
1&0&0\\
0&1&0\\
0&0&1\\
\end{array}\right]
\times
\left[\begin{array}{ccc}
1&1&1\\
0&1&1\\
0&0&1\\
\end{array}\right]
=\left[\begin{array}{ccccccccc}
1&0&0&1&0&0&1&0&0\\
0&1&0&0&1&0&0&1&0\\
0&0&1&0&0&1&0&0&1\\
1&1&1&1&1&1&1&1&1\\
0&0&0&1&1&1&1&1&1\\
0&0&0&0&0&0&1&1&1\\
\end{array}
\right]
$$
\vskip 3pt




Many
results have been obtained about $\forb(m,F)$ but the following is the most fundamental.

\begin{thm}\label{sauer} [Sauer  \cite{Sauer}, Perles and Shelah
\cite{PS}, Vapnik and Chervonenkis \cite{VC}] We have that
$$\forb(m,K_k)=\binom{m}{k-1}+\binom{m}{k-2}+\cdots +\binom{m}{0}.$$
Thus $\forb(m,K_k)$ is $\Theta(m^{k-1})$.\end{thm}

There is mention in the paper \cite{Sauer} that the problem is due to 
Erd\H{o}s.  Also there is an earlier citation in Russian for \cite{VC}.  If a matrix $A$ contains a copy of $K_k$ in a $k$-set of rows $S$ then we say that $S$ is  \emph{shattered} by $A$. 
There are many results on shattered sets. We define a (0,1)-matrix $A$ to have \emph{VC-dimension} $k$ if the largest cardinality of a shattered set is $k$ (alternatively $K_k\prec A$ and $K_{k+1}\not\prec A$) and so $\ncols{A}$ is $O(m^k)$. There are many results on VC-dimension.   
\begin{E}\hbox{Let }\ext(m,F)=\{A\in\Av(m,F)\,|\,\ncols{A}=\forb(m,F)\}.\label{extremalmatrices}\end{E}
There are a multiplicity of  matrices $A\in\ext(m,K_k)$ including \hfill
$[K_m^{k-1}\,|\,K_m^{k-2}\,|\,\cdots\,|\, K_m^0]$ or, for any $k\times 1$ (0,1)-column $\alpha$, for $A$ all columns with no \emph{submatrix} $\alpha$. There are interesting results about matrices in $\ext(m,K_k)$ in \cite{A88} and an interesting construction in \cite{AS97} with all column sums in $\{t,t+1,t+2,\ldots,t+k-1\}$.

\trf{sauer} has  induction proofs (Section~\ref{induction}) using the standard induction \cite{Sauer} and also with shattered sets (Thm 1.4,\cite{Pajor}), a shifting proof (Section~\ref{shifting}),  and  linear algebra proofs (Section~\ref{linalg}) \cite{FP83} and \cite{Smolensky}.  The asymptotic growth of $\Theta(m^{k-1})$ was what interested Vapnik
and Chervonenkis in Applied Probability. 
An easy consequence of Theorem~\ref{sauer} using Remark~\ref{subconfig} is the following:

\begin{cor}\label{subsauer}Let $F$ be a $k\times \l$ simple matrix. Then $\forb(m,F)$ is $O(m^{k-1})$.\qed \end{cor}

It would seem reasonable to consider (0,1)-matrices $F$ which are not simple as well. F\"uredi \cite{F} noted the following general bound that can be proved using Theorem~\ref{sauer}.

\begin{thm}\label{general}\cite{F} Let $F$ be a $k\times \l$
(0,1)-matrix. Then there is a constant $c_F$ so that $\forb(m,F)\le c_Fm^k$ i.e. $\forb(m,F)$ is $O(m^k)$.\qed \end{thm}

But what is the correct asymptotic growth as a function of $F$?  We can obtain more detailed general results. The first result below (simultaneously and independently obtained by F\"uredi and Quinn (generalizing a result of Ryser\cite{R72}) and the second result of Gronau are both exact and can be deduced by the existence of constructions since the bounds  follows from Remark~\ref{subconfig} in the first case using $F=K_k$ and in the second case using $F=K_{k+1}$.

\begin{thm} \cite{FQ}\label{K_k^s} Let $k,s$ be  given positive integers with $0\le s\le k$. Then
$$\forb(m,K_k^s)=\binom{m}{k-1}+\binom{m}{k-2}+\cdots +\binom{m}{0}.\hfil\qed$$\end{thm}

\begin{thm} \cite{G}\label{2K_k} We have
$$\forb(m,2\cdot K_k)=\binom{m}{k}+\binom{m}{k-1}+\cdots +\binom{m}{0}.\hfil\qed$$\end{thm}

The next result refines F\"uredi's result Theorem~\ref{general}.

\begin{thm} \cite{AF}\label{tKk} We have
$$\forb(m,t\cdot K_k)=\forb(m,t\cdot K_k^k)\le  \frac{t-2}{k+1}\binom{m}{k}(1-o(1))+\binom{m}{k}+\binom{m}{k-1}+\cdots +\binom{m}{0},$$
with equality if a $k$-design, of multiplicity $\lambda=t-1$ and blocksize $k+1$, exists on $m$ points.\qed \end{thm}

 The following four results are quite general refinements of \trf{sauer} and \trf{general}.
The following describes the boundary between $\Theta(m^{k-2})$ and $\Theta(m^{k-1})$
for simple $k\times \l$ $F$. 


\begin{thm}\cite{AFl10}\label{simple,k-2} Let $k$ be given.

\noindent If $F$ is a simple $k\times \l$ matrix with the property that there is a pair of rows of $F$ that do not contain $K_2^0$, a pair of rows of $F$ that do not contain $K_2^2$ and a pair of rows of $F$ that do not contain the configuration $K_2^1=I_2$, then $\forb(m,F)$ is $O(m^{k-2})$. 

\noindent If $F$ is a simple $k\times \l$ matrix with the property that either every pair of rows has $K_2^0$ or every pair of rows has $K_2^2$ or every pair of rows has $K_2^1$, then $\forb(m,F)$ is $\Theta(m^{k-1})$.\qed \end{thm}

The maximal $k$-rowed simple matrices $F$ with $\forb(m,F)$ being $O(m^{k-2})$are listed in Theorem~\ref{simple,k-2,matrices}. The following considers the boundary between $\Theta(m^{k-1})$ and $\Theta(m^{k})$
for arbitrary $k\times \l$ $F$. The result in Theorem~\ref{B}  was first proved for $k=3$ in \cite{AS05},\cite{AGS} (there were two proofs originally, one for each of the two possible choices of a $3\times 4$ $B$)  and Theorem~\ref{boundary} was first proved for $k=3$ in \cite{AS05}.
 Theorem~\ref{B} was proven for general $k$ in \cite{AFllinalg},\cite{AFFS} and Theorem~\ref{boundary} was proven for general $k$ in \cite{AFl10}.

\begin{thm}\label{B}\cite{AGS}\cite{AFFS}\cite{AS05} Let $B$ be a simple $k\times (k+1)$ matrix with the property that there is one column of each column sum. Let $K_k-B$ denote the $k\times (2^k-k-1)$ matrix obtained from $K_k$ by deleting the columns of $B$ (row order matters here). Let $t$ be given. Then $\forb(m,[K_k\,|\,t\cdot[K_k-B]])$ is $\Theta(m^{k-1})$. \qed\end{thm}


\begin{thm}\label{boundary}\cite{AS05}\cite{AFl10} Let $k$ be given and let $D_{12}$ denote the simple
matrix of all columns of column sum at least 1 with no $K_2^2$ on rows 1 and 2.
Then assuming $k\ge 3$ and  $t\ge 2$ then $\forb(m,[K_k^0\,|\,t\cdot D_{12}])$ is $\Theta(m^{k-1})$. \qed\end{thm}

Note that $t\cdot I_k\prec t\cdot D_{12}$.

\begin{thm}\label{completeboundary}\cite{AFl10} Let $F$ be a $k$-rowed matrix with maximum column multiplicity $t$. If $F\not\prec [K_k\,|\,(t-1)\cdot[K_k-B]])$ for any choice of $B$ as in Theorem~\ref{B} and $F\not\prec [K_k^0\,|\,t\cdot D_{12}])$ for $D_{12}$ as in Theorem~\ref{boundary} then $\forb(m,F)$ is $\Theta(m^k)$.\end{thm}

This completely determines the boundary between $\Theta(m^k)$ and $\Theta(m^{k-1})$. The matrices that Conjecture~\ref{grand} predicts to determine the boundary between $\Theta(m^{k-1})$ and $\Theta(m^{k-2})$ are described in Theorem~\ref{k-2,matrices}. Theorem~\ref{simple,k-2,matrices} helps in this analysis. There are complete asymptotic results for $k\times 2$ $F$ in \srf{l=2}.

A large number of exact bounds are sprinkled throughout this survey including complete exact results for $1\times \l$ $F$ in Section~\ref{k=2} and complete exact results for $k\times 1$ $F$ in Section~\ref{l=2}, a number of $2\times \l$ results in Section~\ref{k=2} and a number of general $k\times 2$ results in Section~\ref{l=2} as well as a number of $3\times 2$, $3\times 3$ and $3\times 4$ results in Section~\ref{k=3} and a number of $4\times 2$ and further $4$-rowed results in Section~\ref{k=4}. One gets an idea of what is typically driving the exact bounds for many $F$.  In \cite{AKarp}, we defined a \emph{critical substructure} of a configuration $F$ as a minimal configuration $F'\prec F$ with $\forb(m,F')=\forb(m,F)$. For $K_4$ we have the complete list of critical substructures but have not yet fully determined the list for $K_5$.

\begin{thm}\cite{miguelthesis} The critical substructures of $K_4$ are
$\0_4$, $I_4$, $K_4^2$, $I_4^c$, $\1_4$, $2\cdot \0_3$ and $2\cdot\1_3$. \qed\end{thm}

We have verified (Prop. 4.3.8 \cite{miguelthesis}) that the only $k$-rowed critical substructures of $K_k$ are $K_k^s$ for $s=0,1,\ldots ,k$.

\begin{prob}Show that $2\cdot \1_{k-1}$ and $2\cdot \0_{k-1}$ are the only $(k$-$1)$-rowed critical substructures of $K_k$. \end{prob}

The following result, while not best possible, indicates that \trf{sauer} can be extended.

\begin{thm}\label{sauerextend}\cite{AnsteeMeehan} Let $\alpha=\1_p\0_q$ where $p+q=k$ and $p,q\ge 2$. Then
$$\forb(m,[K_k|\alpha])=\forb(m,K_k).\qed $$
\end{thm}

It is believed that for any $t$ and  $m$ large enough (as a function of $t,k$), $\forb(m,[K_k|t\cdot \alpha])=\forb(m,K_k)$. Exact bounds often require a more complete understanding of what it means to forbid a configuration. In many cases we can also determine $\ext(m,F)$ (see \rf{extremalmatrices}).  In trying to establish exact bounds we have found some interesting `negative' results including Theorem~\ref{difficult} for the configuration $F_{2,1,1,0}$.




A purpose of this paper is to provide a single place to access existing results (Sections \ref{k=2}, \ref{k=3}, \ref{k=4}, \ref{l=2}, \ref{simplek=5}, \ref{generalboundary}) and the proof techniques employed (Sections \ref{missing}, \ref{induction}, \ref{shifting}, \ref{graphtheory}, \ref{linalg},   \ref{strongstability}). In doing so, we are encouraging the gentle reader to consider ways to make progress in proving the conjecture described in Section~\ref{conjecture} or perhaps obtaining exact bounds or exploring other related problems such as described in Section~\ref{variations}. Open problems are scattered throughout including
Conjecture~\ref{grand}, Problem~\ref{doubling}, Problem~\ref{4by4}, Problem~\ref{twocolprob}, Conjecture~\ref{classifyk=5}, Problem~\ref{exactbounds}, Conjecture~\ref{submatrix}. Here are two very concrete problems that I can suggest:

\begin{prob}Show that
$$\forb(m,\left[\begin{matrix}1&1&1&0&0&0\\ 1&1&1&0&0&0\\ 0&0&0&1&1&1\\ 0&0&0&1&1&1\\ \end{matrix}\right]) 
\hbox{ is }O(m^2).\qed$$\end{prob}

\begin{prob}Show that for those $m$ for which  a triple system of multiplicity 2 exists, 
$$\forb(m,\left[\begin{matrix}1&1&1&1\\ 1&1&1&1\\ 1&0&0&0\\ \end{matrix}\right])
=\frac{5}{3}\binom{m}{2}+\binom{m}{1}+\binom{m}{0}+\binom{m}{m}.\qed$$\end{prob}






I expect that I have missed many related results that have been stated in another context but have relevance here. I would be glad to hear about them; email me.

\section{Variations including Forbidden Submatrices}\label{variations}

\noindent{\bf Uniform Hypergraphs}

In generalizing from graphs to hypergraphs, it is often the case that we restrict to  $r$-uniform (simple) hypergraphs for a fixed $r$. In our setting this is the requirement that all column sums are $r$. 
Frankl and Pach \cite{FP94} considered \trf{sauer} for $r$-uniform hypergraphs for which they established a basic bound of $\binom{m}{k-1}$. Ahlswede and Khachatrian \cite{ AhKh97b} obtain a construction of size $\binom{m-1}{k-1}+\binom{m-1}{k-3}$ while Mubayi and Zhao \cite{MZ07} obtain an improved upper bound of $\binom{m}{k-1}-\log_p m+k!k^k$. Other cases of forbidden configurations such as $K_k^{\l}$ for $r$-uniform hypergraphs are considered \cite{MZ07}.  Asymptotically sharp values for the maximum number of edges in a 3-uniform hypergraph containing  no Fano plane are due to deCaen and F\"uredi \cite{dCF}. An asymptotically exact bound for Tur\'an's problem remains elusive.



\vskip 10pt
\noindent{\bf Families of forbidden configurations}

The notion of some forbidden substructure often can be described by some family (often infinite) of forbidden configurations. Many problems in extremal combinatorics could be phrased that way but typically there is no special insight gained.  We  have forbidden families arise using inductive arguments in \crf{onerow}.  We'll discuss a few other cases.  The result of Balogh and Bollab\'as seems the most interesting result.

\begin{thm}\cite{BB} Let $k$ be given. Then $\forb(m,\{I_k,I_k^c,T_k\})$ is $O(1)$.\end{thm}

   In some ways this seems to follow from \corf{grand} since no linear construction ($I_m$, $I_m^c$ or $T_m$) avoids all three forbidden configurations $I_k$, $I_k^c$, $T_k$. A less restrictive family of forbidden configurations also yielding a constant bound is in \cite{BaloghPrince}. A meta version of \corf{grand} namely that the product constructions yield the asymptotically best constructions is false in general  (\trf{c4} and \trf{I2xI2,I2xT2,T2xT2} below). An easy (not optimal) construction of an $m\times \binom{2k}{k}$ simple matrix $A$ that has no configurations $I_k$, $I_k^c$, $T_k$ is to take all columns of column sum $k-1$ in the $(k\,$-$1)$-fold product 
$T_{m/(k-1)}\times T_{m/(k-1)}\times\cdots T_{m/(k-1)}$.  With Laura Dunwoody, we  established some easy exact results.

\begin{thm}\cite{AD} $\forb(m,\{I_1,I_1^c,T_1\})=0$ and 
$\forb(m,\{I_2,I_2^c,T_2\})=2$,\hfil\break $\forb(m,\{I_3,I_3^c,T_3\})=6$. \qed \end{thm}

 A result of Balin Fleming (related to results in \cite{AFl10}) yields a remarkably good bound:

\begin{thm} Let $F_a=\biggl[ \begin{matrix}1&0&\\ 0&1&\end{matrix} t\cdot \begin{matrix}1\\ 1\\\end{matrix} \biggr]$, $F_b=\biggl[ \begin{matrix}1&0&\\ 0&1&\end{matrix} t\cdot \begin{matrix}0\\ 0\\\end{matrix} \biggr]$, and $F_c=t\cdot \begin{bmatrix}0&1&1\\ 0&0&1\\\end{bmatrix}$. \hfill \\ Then for $t\ge 2$, $\forb(m,\{ F_a,F_b,F_c\} )\le 6t-6$. \end{thm}

The following three results follow from results of Balogh, Keevash and Sudakov \cite{BKS}. Somewhat different bounds occur if one  adds $\0$ to $I$, adds $\1$ to $I^c$ and adds $\0$ to $T$. 
\begin{thm} Let $k\ge 2$ be given. Then $\forb(m,\{I_k,I_k^c\})$ is $\Theta(m^{k-1})$.\end{thm}
\proof We note that $\forb(m,\{I_k\})$ is $O(m^{k-1})$ and hence
$\forb(m,\{I_k,I_k^c\})$ is $O(m^{k-1})$. The construction of the $(k\,$-$1)$-fold product $T_{m/(k-1)}\times T_{m/(k-1)}\cdots \times T_{m/(k-1)}$ show that $\forb(m,\{I_k,I_k^c\})$ is $\Omega(m^{k-1})$ since if we take two rows from any one term of the product, we are unable to have $I_2$ and yet $I_k$ and $I_k^c$ have $I_2$ in every pair of rows.
\qed

\begin{thm} Let $k\ge 2$ be given. Then $\forb(m,\{I_k^c,T_k\})$ is $\Theta(m^{k-1})$.\end{thm}
\proof We note that $\forb(m,\{I_k^c\})$ is $O(m^{k-1})$ and hence
$\forb(m,\{I_k^c,T_k\})$ is $O(m^{k-1})$. The construction of the $(k\,$-$1)$-fold product $I_{m/(k-1)}\times I_{m/(k-1)}\cdots \times I_{m/(k-1)}$ show that $\forb(m,\{I_k^c,T_k\})$ is $\Omega(m^{k-1})$ since if we take two rows from any one term of the product, we are unable to have $\binom{1}{1}$ and yet $I_k^c$ and $T_k$ have $\binom{1}{1}$\qed\vskip 10pt

\begin{thm} Let $k\ge 2$ be given. Then $\forb(m,\{I_k,T_k\})$ is $\Theta(m^{k-2})$.\end{thm}
\proof We note that both $I_k$ and $T_k$ have a column with $k-1$ 0's and so neither can be found in the $(k\,$-$2)$-fold product $I_{m/(k-2)}^c\times I_{m/(k-2)}^c\cdots \times I_{m/(k-2)}^c$,  hence  $\forb(m,\{I_k,T_k\})$ is $\Omega(m^{k-2})$. To prove the upper bound, we use induction on $\l$ in the statement $\forb(m,\{I_{k},T_\l\})$ is $O(m^{\l-2})$, for $\l\ge 2$. When $\l=2$, we note that forbidding $T_2$ means that any two sets (thinking of columns as sets)  must be disjoint. Then the condition no configuration $I_{k}$ means that there are at most $k-1$ disjoint nonempty sets (column sum at least 1) and the empty set (the column of 0's). Thus $\forb(m,\{I_{k},T_2\})=k$ which is $\Theta(m^{2-2})$.
Now we use induction on $\l$ and the standard decomposition of (\ref{standarddecomp}) noting that applying \lrf{onerow} to $F=T_{\ell}$ yields $F_s=T_{\ell-1}$ for $s\ne 1$. Thus $\forb(m,\{I_k,T_{\ell})\le \forb(m-1,\{I_k,T_{\ell}\}) +\forb(m-1,\{I_k,T_{\ell-1}\})$. Applying induction, we obtain the desired bound. 
\qed
\vskip 5pt
The following result shows that our constructions of Conjecture~\ref{grand} are no longer sufficient for asymptotics with families of forbidden configurations. General forbidden subgraph problems could be given this way.

\begin{thm}\label{c4} Let $C_4$ denote the $4\times 4$ matrix that is the incidence matrix of a cycle of length 4. Then $\forb(m,\{\1_3, C_4\})$ is $\Theta(m^{3/2})$.\end{thm}
\proof Forbidding $\1_3$  makes this into a graph problem since apart from columns of sum 0 or 1, all remaining columns must have two 1's. A simple matrix with column sums 2 can be viewed as the vertex-edge incidence matrix of a graph on $m$ vertices.  Now the maximum number of edges in a graph on $m$ vertices with no  no cycle of length 4 is $\Theta(m^{3/2})$.\qed

\vskip 5pt
We have obtained a stronger version of this by a complicated induction argument. Note that $I_2\times I_2$ is $C_4$ as a configuration.

\begin{thm}\label{I2xI2,I2xT2,T2xT2}\cite{IIcT} We have that $\forb(m,\{I_2\times I_2, I_2\times T_2,T_2\times T_2\})$ is $\Theta(m^{3/2})$. \qed
\end{thm}

While these result are `negative' and suggests that handling families of forbidden configurations will be enormously more difficult than forbidding a single configuration, it is also the case that some of our inductive proofs for a single conjecture naturally consider families of forbidden configurations and perhaps in those cases our product constructions are still asymptotically optimal.



Assume $t$ is given. Kleitman considered the maximum size of a set system ${\cal F}\subseteq 2^{[m]}$ with the property that for every pair $A,B\in{\cal F}$, $|A\backslash B|+|B\backslash A|\le 2t$. The bound is $\forb(m,K_{t+1})$.
One can think of this as having forbidden the $(2t+1)\times 2$ configurations
$F_{0,2t+1,0,0}, F_{0,2t,1,0},\ldots, F_{0,t+1,t,0}$. 



\emph{Balanced} and \emph{Totally Balanced} matrices are easily defined in terms of forbidden configurations. Let $C_k$ denote the $k\times k$ matrix that is the incidence matrix of a cycle of length $k$. A matrix is {\it Balanced} if and only if it has no configuration $C_{k}$ for $k\in\{3,5,7,9,\ldots\}$. A matrix is 
{\it Totally Balanced} 
if and only if it has no configuration $C_{k}$ for $k\in\{3,4,5,6,\ldots\}$. The result that $\forb(m,C_3)=\binom{m}{2}+\binom{m}{1}+\binom{m}{0}$ can be found in \cite{R72} but also follows from Theorem~\ref{sauer} since $C_3$ is a configuration of $K_3$.
\begin{thm}\cite{AFa84} Let $C_k$ denote the $k\times k$ matrix that is the incidence matrix of a cycle of length k. Then 
$\forb(m,\{C_3,C_4,C_5,\ldots\})=\forb(m,C_3)=\binom{m}{2}+\binom{m}{1}+\binom{m}{0}$.\qed\end{thm}

One has the remarkable result that any $m\times (\binom{m}{2}+\binom{m}{1}+\binom{m}{0})$ simple matrix with no configuration $C_3$ is also totally balanced (Remark 3.1\cite{A80}). Totally balanced matrices have been studied in many papers (e.g. \cite{AFa84}) with a survey contained in \cite{Sp}. 

\vskip 10pt
\noindent{\bf Forbidden Submatrices: Fixed Row and Column Order}

Another variation is to ask whether the row or column order is important. In most combinatorial investigations, permuting the row and column order is just a relabelling. Forbidding a configuration can be thought of as forbidding all submatrices in the equivalence class $\tilde{F}$. In other circumstances either the row order or the column order or both may be crucial. For example, there are algorithms that proceed by assuming you have a special ordering and then the algorithm exploits this special ordering \cite{AFa84}. It is a somewhat remarkable fact (due to Hoffman, Kolen and Sakarovitch \cite{HKS} as well as \cite{AFa84}) that a matrix is \emph{Totally Balanced} if and only if the rows and columns can be ordered so that the resulting matrix has no submatrix
$$\left[\begin{matrix}1&1\\ 1&0\\\end{matrix}\right].$$
Spinrad has a survey on some results in this area.

 Results on Forbidden Submatrices  can be found in \cite{A85}, \cite{AF}, \cite{FFP}, \cite{A00}. One can restate Theorem~\ref{one-way} as a forbidden submatrix problem where we view $F_{0,k,0,0}$ as a matrix (not configuration).

\begin{thm}\label{kx2submatrix}\cite{FFP} Let $k,m$ be given and let $f(m,k)$ denote the maximun number of columns in a simple $m$-rowed matrix $A$ such that $A$ has no submatrix $F_{0,b,0,0}$ (we are viewing $F_{0,b,0,0}=[\1_k\,|\,\0_k]$  as a $k\times 2$ matrix and not as a configuration). Then $f(m,2)=\binom{m}{2}+2m-1$ and $f(m,k)<\binom{m}{k}+5k^2\binom{m}{k-1}$. \end{thm}

As noted above the theorem on bounding one-way differences  yields a forbidden configuration result. The following is the general result for forbidden submatrices.
\begin{thm}\cite{A00}
Let $F$ be a $k\times \l$ (0,1)-matrix. Let $A$ be an $m\times n$ (0,1)-matrix with no $k\times \l$ submatrix of $A$ being equal to $F$. Then
$$n\le m^{2k-1-((k-1)/(13\log_2\l))}$$\label{submatrixbound}\end{thm}
\vskip 10pt

This was an improvement on the  result that $n\le m^{2k-1}$ proved in
\cite{FFP} via a pigeonhole argument and on the first bound of $n\le m^ {13k\log_2\l}$ in \cite{A85}. In any event the conjecture was made both in \cite{AF}, \cite{FFP} that:
\begin{conj}\label{submatrix}
Let $F$ be a $k\times \l$ (0,1)-matrix. Let $A$ be an $m\times n$ (0,1)-matrix with no $k\times \l$ submatrix of $A$ being equal to $F$. Then there exists a constant
$c_F$ depending only on $F$ so that 
$$n\le c_Fm^k. $$\end{conj}

Some recent progress is in \cite{AnsteeChen}.

\vskip 10pt
\noindent{\bf Fixed Row order for Configurations}

There have been some investigations for cases where only column permutations of $F$ are allowed. Some linear algebra proofs have this as an essential character \cite{A95}. We note that a row permutation of $K_k$ (or $K_k^s$) is a column permutation of $K_k$ (or $K_k^s$). Thus in the standard cases we can avoid row permutations.
Some induction proofs generalize, using this idea, to the idea of \emph{order shattered sets} \cite{ARS}.

\vskip 10pt
\noindent{\bf Forbidding configurations on some selection of subsets of rows}

There are cases where one might want to forbid a configuration of $k$ rows on only some subset of the possible $k$-sets of rows or indeed on a collection of subsets of rows of varying sizes. Induction, shifting and linear algebra proofs continue to work. \trf{f(m,S)} of Alon \cite{Alon} is central to this.
An exploration of the proof techniques and some generalizations are in \cite{A88}.
An application of the result is \trf{submatrixbound} \cite{A00} to the problem of forbidden submatrices.

The main results on shattered sets are stated from a different point of view (typically assuming some configurations are present on certain subsets of the rows) but are related (e.g. \cite{ARS}).

\vskip 10pt
\noindent{\bf Multiset versions}

Many results easily extend to allowing the elements of our family ${\cal A}$ to themselves be multisets, the usual approach being to allow element $i$ (corresponding to row $i$) to have maximum multiplicity $e_i$. Thus rather than entries 0 or 1 the entries in row $i$ of $A$ are in $[e_i]$. The extension of Theorem~\ref{sauer} to multisets with $e_1=e_2=\cdots =e_m=e$ is in
\cite{St} and the extension of Theorem~\ref{sauer} to multisets allowing different $e_i$'s is in
\cite{KM}. The extension to forbidding $K_{|S|}$ on rows $S$ for a family of sets $S\in T\subseteq 2^{[m]}$ while having various element multiplicities is in \cite{Alon}. Define an
$(m,e_1,e_2,\ldots ,e_m)$-column as a column on $m$ rows with the entry in the $i$th row of the column  chosen from $\{0,1,\ldots ,e_i\}$ for $i=1,2,\ldots ,m$.  Define an $m$-rowed matrix $A$ to be $e$-simple if each column is an $(m,e_1,e_2,\ldots ,e_m)$-column and there are no repeated columns.  In this context, we use 
$K_S$ to denote the $k\times \bigl(\prod_{i\in S}(e_i+1)\bigr)$ $e$-simple matrix.
 
\begin{thm}\cite{Alon}. Let $m,e_1,e_2,\ldots ,e_m$ be given positive integers and let ${\cal S}$ be given with ${\cal S}\subseteq 2^{[m]}$. Let $f(m,{\cal S})$ be the number of 
$(m,e_1,e_2,\ldots ,e_m)$-columns which do not have all 0's for the rows indexed by $S$ for any $S\in {\cal S}$. Then if $A$ is $m\times n$ $e$-simple matrix with  $K_{|S|}\not\prec A|_S$ for any $S\in {\cal S}$, then
$$n\le f(m,{\cal S}).\qed$$
\label{f(m,S)}\end{thm}


There are some forbidden configuration ideas in \cite{AM} that explore the natural generalization of $K_k^s$
 and Theorem~\ref{K_k^s} to multisets. 
The results in \cite{AA} are stated in terms of divisors of an integer $\prod_{i=1}^m
p_i^{e_{i}}$.  

A recent variation of F\"uredi and Sali \cite{FurediSali} considers forbidding versions of $K_k$ consisting of two symbols. Let $K_k(\{i,j\})$ denote the $k\times 2^k$ matrix consisting of all possible columns on the two symbols $i,j$.  Let $A$ be an $m\times n$ matrix
 with entries in $\{0,1,2,\ldots ,e\}$ and no repeated columns. Assume that for each pair $i,j\in \{0,1,2,\ldots ,m\}$ we have a bound $k(i,j)$. Assume
$A$ has no configuration $K_{k(i,j)}(i,j)$ for each pair $i,j\in \{0,1,2,\ldots ,e\}$. Then we can obtain a polynomial bound on $n$ (polynomial in $m$ where $e$ and the values $k(i,j)$ are viewed as constants)   that reduces to \trf{sauer} in the case $e=1$ and $k(0,1)=k$.

Interestingly, the Bixby and Cunningham \cite{BC} proof of the bound on the number of distinct columns for a totally unimodular matrix, a (-1,0,1)-matrix, uses Theorem~\ref{sauer} for $k=2$. Further applications to matrices with more than just two possible entries are found in \cite{A90}.

Results where we allow our family ${\cal A}$ to be a multiset are more problematic and we quickly would have $\forb(m,F)$ be infinite by either repeating the column of 0's or the column of 1's. The design theoretic results of \cite{AB} do use such an interpretation when the column sums are restricted. 

\vskip 10pt
\noindent{\bf VC-dimension} 

VC-dimension is defined in the Introduction. Vapnik and Chevonenkis \cite{VC} were interested in applied probablility when they developed the fundamental result \trf{sauer}. Applications to learning theory continue to be developed while raising interesting related questions \cite{SSYZ}.   There are other applications. Some have described VC-dimension as a good measure of the complexity of a hypergraph \cite{LT}. An important application is to transversals. For this concept, a column of 0's causes difficulties (or an empty edge in the hypergraph) so in what follows assume we do not have the column of 0's.
Let $S\subseteq [m]$ be a \emph{transversal} of $A$ if each column of $A$ has at least one 1 in a row of $S$. Seeking a minimum cardinality transversal, we let  $\x$ be the (0,1)-incidence vector of $S$, and compute:

$$\tau=\min \left\{\1\cdot\x\hbox{ subject to }A^T\x\ge\1, \quad\x\in\{0,1\}^m\right\}.$$
 
The natural fractional problem is: 

$$\tau^*=\min \left\{\1\cdot\x\hbox{ subject to }A^T\x\ge\1, \quad\x\ge\0\right\}.$$

Haussler and Welzl  obtained a `close' connection between $\tau$ and $\tau^*$.

\begin{thm} (Haussler and Welzl \cite{HW}) Assume $A$ is a (0,1)-matrix with no column of 0's. If $A$ has VC-dimension $k$ then 
 $\tau\le 16k\tau^*\log(k\tau^*)$.\end{thm}
 
 An example of the use of this is by {\L}uczak and Thomass\'e  \cite{LT} to solve a colouring problem.
 
 VC-dimension has been used in Computational Geometry \cite{M}.  Goldberg  \break\cite{ADFGW}  used low VC-dimension of map data to help determine efficiently (in suitable real time) shortest highway paths.
 
 
 



\vskip 10pt
\noindent{\bf Patterns} 

A  problem which sounds very similar to forbidding a configuration is to consider how many 1's an $m\times n$ matrix can have subject to some `forbidden configuration' of 1's sometimes called a \emph{pattern}. There are several differences including that we do not allow row and column permutations (although one could do this by forbidding patterns in $\tilde F$) and the fact we do not concern ourselves with 0's (if we think of patterns as subgraphs then our forbidden configurations are like induced subgraphs).  If we choose to forbid a $k\times \l$ submatrix of 1's then this is the problem of Zarankiewicz \cite{KST}. A number of papers study problems related to patterns: \cite{F90},\cite{BG},\cite{FH},\cite{MT},\cite{T05}. Assume you have been given some $k\times \l$ (0,1)-matrix $F$ which we can call a \emph{pattern}. We ask for the  maximum number of 1's in  an $m\times n$ matrix $A$ which has the property that there is no $k\times \l$ submatrix $B$ with $F\le B$. Here we are using the definition that for two $a\times b$ matrices $C=(c_{ij})$ and $D=(d_{ij})$, we say $C\le D$ if and only if $c_{ij}\le d_{ij}$ for all choices $i=1,2,\ldots ,a$ and $j=1,2,\ldots ,b$.
F\"uredi and Hajnal \cite{FH} considers all patterns of 4 1's as well as other patterns. Marcus and Tardos \cite{MT} solve an important conjecture of F\"uredi and Hajnal and also a conjecture of Stanley and Wilf by considering a pattern corresponding to a permutation matrix \cite{MT} . Various bounds such as $m\log n$ arise for forbidden patterns so some results have quite different character from forbidden configuration bounds.
Results from patterns have been useful in our investigations \cite{IIcT}. When applying \corf{grand}, it is natural to ask how many columns can we select from a large product (e.g. $T_{m/2}\times T_{m/2}$) while still avoiding some configuration (e.g. $T_2\times T_2$). We may encode each chosen column of the product $T_{m/2}\times T_{m/2}$ as a 1 in an $m/2\times m/2$ matrix $A$ and the forbidden configuration $T_2\times T_2$ forces $A$ to avoid a pattern of a $4\times 4$ permutation  matrix (as well as other patterns). Results in \cite{IIcT} expand on this.  

\vskip 10pt
\noindent{\bf Covering Arrays} 

A \emph{covering array of strength} $k$ is a (0,1)-matrix such that every $k$-set of rows contains a copy of $K_k$ (this is usually done for the transposed matrix).  One would be interested in the minimum number of columns for which a covering array on $m$ rows exist.  The following result of Kleitman and Spencer answers most of the asymptotic questions.

\begin{thm}\label{reqK_k} Kleitman and Spencer\cite{KS} Let $k$ be given. Then there exists an $m$-rowed (0,1)-matrix $A$ such that for every $S\in\binom{[m]}{k}$, that $K_k\prec A|_S$ such that
$\ncols{A}$ is $\Theta(\log {m})$.
\end{thm}

A survey article on binary covering arrays by Lawrence et al \cite{LKLKF} is recommended. Note that in the area of covering arrays, the great interest is in \emph{exact} results. In \cite{AnsteeMeehan} we defined
$$\req(m,F)=\min_A\{|A|\,:\,A\hbox{ is }m\hbox{-rowed and simple; for all }
S\in\binom{[m]}{k}\,\,F\prec A|_S\}.$$
An application to forbidden configurations occurs when we consider what we must delete in order to avoid a configuration. The question is typically only relevant for the number of rows small with respect to the forbidden configuration.

\begin{lemma}\label{Kp+qp}\cite{AnsteeMeehan} Let $k,p,q$ be given with $p+q\leq k$. Let $A$ be a $k$-rowed simple matrix with no configuration $F = \1_p\0_q \times K_{k - (p + q)}$. Then for every $S\subseteq\binom{[k]}{p+q}$ set of rows of the matrix $K_{p+q}^p\prec (K_k\backslash A)|_S$. Thus
$\forb(k, (\1_p\0_q) \times K_{k - (p + q)})=2^k-\req(k, K_{p+q}^p)$.\end{lemma} 

Erd{\H{o}}s, Frankl and F\"uredi obtained the following, where containing $I_k$ in every set of $k$-rows was equivalent to saying that you have a family of sets so that no set of the family is contained in the union of $k-1$ other sets. Here is one result.

\begin{thm}\label{EFFIk}\cite{EFF}. Let $m,k$ be given with $k\leq m<\binom{k+1}{2}$, then $\req(m,I_k)= m$. 
\end{thm}

Korner\cite{Korner} used $\req(m,I_3)$ (Problem C) and  $\req(m,K_3)$ (problem D) in the context of Coding Theory.



\section{Main Conjecture for asymptotic bounds}\label{conjecture}

Our investigations have led us to a conjecture on the asymptotic growth of
$\forb(m,F)$ for a fixed $F$ as $m$ goes to infinity. We had noted  that all our results  had $\forb(m,F)=\Theta(m^e)$ for an integer $e$. Our conjecture involves the product construction (\drf{product}). Let $A_i$ be an $m_i\times n_i$ simple matrix
for $1\le i\le t$. The $t$-fold product 
$A=A_1\times A_2\times \cdots \times A_t$ is an
$(\sum_{i=1}^t m_i)\times (\Pi_{i=1}^t n_i)$ simple matrix. Let $I_h$ denote the $h\times h$ identity matrix and $I_h^c$ denotes its (0,1)-complement. Let
$T_h$ denote the
$h\times h$ {\it triangular} matrix
$$T_h=\begin{bmatrix}
1&&&1's\\ &1&&\\ &&\ddots&\\ 0's&&&1\\
\end{bmatrix}.$$
The three matrices $I,I^c,T$ are our proposed building blocks for  product constructions. Note that if each $A_i$ in the $t$-fold product above is of size $m/t\times m/t$ then the $t$-fold product has $m$ rows and $\Theta(m^t)$ columns.  
Let $F$ be a $k\times \l$ (0,1)-matrix.  


\begin{defn} Let $X(F)$ be the smallest $p$
so that $F$ is a configuration in
$A_1\times A_2\times \cdots \times A_p$ for every choice of $A_i$ as either
$I_{m/p}$, $I_{m/p}^{c}$ or $T_{m/p}$. Alternatively, assuming $F$ is not a configuration in at least one of $I$, $I^c$, $T$, then $X(F)-1$ is the largest choice of $p$ so that $F$ is not a configuration in
$A_1\times A_2\times \cdots \times A_p$ for some choice of $A_i$ as either
$I_{m/p}$, $I_{m/p}^{c}$ or $T_{m/p}$.\end{defn}

We are assuming $m$ is
large and divisible by $p$, in particular that $m\ge (k+1)(k\l+1)$ so that $m/p\ge k\l+1$. Divisibility by $p$ does not affect the asymptotics since we can use a simple submatrix of a simple matrix that avoids $F$ for construction purposes.  We are also
using the fact that we need only consider $p$-fold products for $p\le k+1$,
since $F$ is a configuration in $\l\cdot K_k$ and we can find $\l\cdot K_k$ (and hence $F$) as a configuration in $A_1\times A_2\times \cdots
\times A_{k+1}$  by taking one row from each of the first $k$ products (each
row has [01]) and then, since we are taking no rows from the final
$A_{k+1}$, we get the configuration $(m/(k+1))\cdot K_k$ in the product. Or we could appeal to Theorem~\ref{general} which has $\forb(m,\l\cdot K_k)$ being $O(m^k)$ and hence $\l\cdot K_k$ must be in a $(k+1)$-fold product else this would yield $(\forb(m,\l\cdot K_k)$ is $\Omega(m^{k+1})$, a contradiction. 
If $F$ is a configuration
in the $p$-fold product
$A_1\times A_2\times \cdots \times A_p$, assume that $a_i$ rows of
$A_i$ are used 
with $\sum_{i=1}^pa_i=k$. If we form the submatrix of $A_i$ of $a_i$
rows, then we would be interested in at most $\l$ copies of a given
column on these rows  ($F$ has $\l$ columns) if this is possible. Now
for $t\ge k+\l$, any $a_i$ rows of $K_t^1$ contains $\l$
columns of 0's as well as a copy of $K_{a_i}^1$. The analogous result is true for
$K_t^{t-1}$.    Also for $t\ge kl+l$, the $a_i$ rows of $T_t$ consisting of rows $\l+1,2\l+1,3\l+1,\ldots , k\l+1$ have $\l$
columns of 0's and $\l\cdot T_{a_i}$. Thus as long as $m\ge (k+1)(k\l+1)$ we are
able to use the matrices $A_i$ as if they were arbitrarily large.


\begin{conj}\label{grand}\cite{AS05} We believe that 
$$\forb(m,F)= \Theta(m^{X(F)-1}).\qed$$\end{conj}


Note that the definition  of $X(F)$ ensures $\forb(m,F)$ is
$\Omega(m^{X(F)-1})$, via the product construction, although for $X(F)=1$ a little care must be
taken.
The  use of the product construction for forbidden configurations is introduced in \cite{AGS} with non-trivial applications to Theorem 2.6 \cite{AGS} and Theorem 3.4 \cite{AGS} for cases with $k=2$ and $k=3$. The Conjecture~\ref{grand}  has been verifed for $k=2$ in Theorem~\ref{classifyk=2}, $k=3$ in Theorem~\ref{classifyk=3},  $l=2$ in Theorem~\ref{twocol},  $k=4$ and $F$ simple in Theorem~\ref{classifyk=4}, and other cases. Moreover the Conjecture has motivated work such as in Conjecture~\ref{classifyk=5}. 

It is important to note that the constant in front of the leading term $m^{X(F)-1}$ of $\forb(m,F)$ is not predicted by the Conjecture and so the Conjecture  is little help with exact bounds.
Also computing $X(F)$ is non-trivial (for large $F$).

\begin{thm}\label{NP-hard}\cite{RNP} Computing $X(F)$ is NP-hard.\end{thm}

Perhaps the problem Partition into Cliques would be useful. We have yet to make a direct
connection between our proofs of asymptotic bounds for $\forb(m,F)$  with
the derivation of $X(F)$. We think of this problem as a configuration version of the 
Erd\H os-Stone-Simonovits Theorem \cite{ES}  for the maximum number of edges in a graph avoiding some specified subgraph $H$ where $\chi(H)$ is relevant.

Some consequences of the conjecture can be considered problems.

\begin{prob}\label{doubling} Let $\forb(m,F)$ be $\Theta(m^p)$. Is it true that $\forb(m,t\cdot F)$ is $O(m^{p+1})$?\hfil\break 
Let $\forb(m,2\cdot F')$ be $\Theta(m^q)$.
Is it true that $\forb(m,t\cdot F')$ is $\Theta(m^q)$ for any $t\ge 2$? \end{prob}

Problem~\ref{4by4} is a specific instance of this problem.


%---------------2-rowed F (and 1-rowed F)-------------

\section{$F$ is a $1\times \l$ or $2\times \l$ (0,1)-matrix}\label{k=2}

For completeness we consider $1\times \l$ $F$ (Theorem 5.1 and Corollary 5.2 from \cite{AFS}).

\begin{thm}Assume $F$ is a $1\times \l$ (0,1)-matrix with $p$ 1's and with $p\ge \l-p\ge 0$ and let $F'$ be the $1\times p$ (0,1)-matrix with $p$ 1's. Assume $m\ge p-1\ge 1$. Then
$$\forb(m,F')=\forb(m,F)=\lfloor\frac{pm}{2}\rfloor+1.\qed$$
\end{thm}

For the case $F$ is $2\times \l$, the asymptotic classification of $\forb(m,F)$ is completed in \cite{AGS}. We need some special matrices given below. 
Let us use the following notation for 2-rowed configurations (as opposed to notation for 2-columned configurations):
$$F_2(r,p,q,s)=\left[\begin{matrix}\\ \\ \\ \end{matrix}\right.
\overbrace{\begin{matrix}00\cdots 0\\ 00\cdots 0\\\end{matrix}}^r
\overbrace{\begin{matrix}11\cdots 1\\ 00\cdots 0\\\end{matrix}}^p
\overbrace{\begin{matrix}00\cdots 0\\ 11\cdots 1\\\end{matrix}}^q
\overbrace{\begin{matrix}11\cdots 1\\ 11\cdots 1\\\end{matrix}}^s
\left.\begin{matrix}\\ \\ \end{matrix}\right].$$


\begin{thm}\label{classifyk=2}  Let $F$ be a $2\times \l$
(0,1)-matrix.\hfill\break
(Constant Cases) If $F=F_2(0,1,0,0)$,  then $\forb(m,F)=\Theta(1)$.\hfill\break
(Linear Cases) If $F$  has at least one configuration from $K_2^0$, $K_2^1$,
$K_2^2$, \hfill\break $F_2(0,2,0,0)$,  and if $F$ is
a configuration in
$F_2(1,t,1,1)$, $F_2(1,t,t,0)$, $(F_2(1,t,t,0))^c$ for some $t\ge 1$, then
$\forb(m,F)=\Theta(m)$.\hfill\break
(Quadratic Cases) If $F$  has at least one configuration from $2\cdot K_2^0$, 
$[K_2^0 | 2\cdot K_2^1 | K_2^2]$,   or  $2\cdot K_2^2$ then
$\forb(m,F)=\Theta(m^2)$.\hfill\break
In addition, any $2\times \l$ (0,1)-matrix $F$ will fall into one of the three Cases.

\end{thm}

\proof    The linear bound for $\forb(m,F_2(1,t,1,1))$ is Theorem 2.2\cite{AGS}. The
linear bound for $\forb(m,F_2(1,t,t,0))$ is Theorem 2.3\cite{AGS}.
The quadratic construction for $[K_2^0 | 2\cdot K_2^1 | K_2^2]$ is  Theorem 2.6\cite{AGS}. The quadratic bound in general for 2-rowed forbidden configurations follows from Theorem~\ref{general}. All the lower bounds follow from the constructions given
in Conjecture~\ref{grand}  but were developed in  \cite{AGS}. For example a linear construction for $F_2(0,2,0,0)$ is $I_m$.
\qed

A large number of exact or nearly exact bounds are available for 2-rowed $F$. Table 1 below considers cases $F_2(0,p,q,0)$.
\vfill\break{\bf Table 1}.



$$\hbox{\hfil
\vbox{\offinterlineskip
\hrule
\halign{&\vrule#&
\strut\,\,\hfil#\hfil\,\,\cr
height2pt&\omit&&\omit&&\omit&\cr
&configuration $F$&&$\forb(m,F)$&&reference&\cr
height2pt&\omit&&\omit&&\omit&\cr
\noalign{\hrule}
height2pt&\omit&&\omit&&\omit&\cr
&$\biggl[ 
\overbrace{\begin{matrix}0\cdots 0\cr 1\cdots 1\cr\end{matrix}}^{q}\biggr]$&
&$\left\lfloor\frac{(q+1)m}{2}\right\rfloor+2,\,\,m\hbox{ large}$&
&Thm~\ref{q10}\cite{AB}&\cr
&$\begin{bmatrix} 0 \\1 \end{bmatrix}$&&$2$&
&\cite{AFS}&\cr
&$\begin{bmatrix} 0&0 \\1&1 \end{bmatrix}$&&$m+2$&
&\cite{AFS}&\cr
&$\begin{bmatrix} 0&0&0 \\1&1&1 \end{bmatrix}$&&$2m+2$&
&\cite{AFS}&\cr
&$\begin{bmatrix} 0&0&0&0 \\1&1&1&1 \end{bmatrix}$&&$\left\lfloor\frac{5m}{2}\right\rfloor+2$&
&\cite{AKa}&\cr
&$\begin{bmatrix} 1&0&0 \\0&1&1 \end{bmatrix}$&&$\left\lfloor\frac{3m}{2}\right\rfloor+1$&
&\cite{AGS}&\cr
&$\begin{bmatrix} 1&0&0&0 \\0&1&1&1 \end{bmatrix}$&&$\left\lfloor\frac{7m}{3}\right\rfloor+1$&
&\cite{AFS}&\cr
&$\begin{bmatrix} 1&0&0&0&0 \\0&1&1&1&1 \end{bmatrix}$&&$\left\lfloor \frac{11m}{4}\right\rfloor+1$&
&\cite{AKa}&\cr
&$\begin{bmatrix} 1&0&0&0&0&0 \\0&1&1&1&1&1 \end{bmatrix}$&&$\left\lfloor \frac{15m}{4}\right\rfloor+1$&
&\cite{AKa}&\cr
&$\begin{bmatrix} 1&1&0&0&0 \\0&0&1&1&1 \end{bmatrix}$&&$\left\lfloor \frac{8m}{3}\right\rfloor$&
&\cite{AFS}&\cr
&$\begin{bmatrix} 1&1&0&0&0&0 \\0&0&1&1&1&1 \end{bmatrix}$&&$\left\lfloor \frac{10m}{3}-\frac{4}{3}\right\rfloor$&
&\cite{AKa}&\cr
&$\begin{bmatrix} 1&1&0&0&0&0&0 \\0&0&1&1&1&1&1 \end{bmatrix}$&&$4m$&
&\cite{AKa}&\cr
&$\biggl[
\overbrace{\begin{matrix}1\cdots 1\cr 0\cdots 0\cr\end{matrix}}^{p}
\overbrace{\begin{matrix}0\cdots 0\cr 1\cdots 1\cr\end{matrix}}^{p}
\biggr]$
&&$pm-p+2$&&\cite{AFS}&\cr
height2pt&\omit&&\omit&&\omit&\cr}
\hrule}
\hfil
}$$

An interesting case for which we do not know the exact bound is the following.
\begin{thm} \cite{AKa}, \cite{AFS} Let $p,q$ be given with $p< q$. Then $$(\frac{p+q}{2}+O(1))m \le\forb(m,\biggl[
\overbrace{\begin{matrix}1\cdots 1\cr 0\cdots 0\cr\end{matrix}}^{p}
\overbrace{\begin{matrix}0\cdots 0\cr 1\cdots 1\cr\end{matrix}}^{q}
\biggr])\le qm-q+2.\qed$$
\end{thm}

From Theorem 2.6 and Corollary 2.7 of \cite{AFS} we obtain:
\begin{thm}
$$\forb(m,\left[\begin{matrix}0&1&1&1\\ 0&0&0&0\\\end{matrix}\right])
=\forb(m,\left[\begin{matrix}0&1&1&1\\ 1&0&0&0\\\end{matrix}\right])
=\forb(m,\left[\begin{matrix}0&1&1&1&0&1\\ 0&0&0&0&1&1\\\end{matrix}\right])$$
$$
=\Bigl\lfloor\frac{7m}{3}\Bigr\rfloor+1$$\end{thm}

From Theorem 2.3 and Corollary 2.5 of \cite{AFS} we obtain:
\begin{thm}
$$\forb(m,\left[\begin{matrix}0&1&1\\ 1&0&0\\\end{matrix}\right])
=\forb(m,\left[\begin{matrix}0&1&1&0&1\\ 0&0&0&1&1\\\end{matrix}\right])
=\lfloor\frac{3m}{2}\rfloor+1.\qed$$\end{thm}


We have the following exact bound (for large $m$) which is 
Theorem 1.3 in \cite{AB}. A pigeonhole argument yields a bound that exceeds the bound below by a linear amount and 
for small $m$ the larger pigeonhole bound can be achieved.

\begin{thm}\label{q10}\cite{AB} Let $q\ge 3$ be given. Then for $m\ge \max\{5q-4, 8q-18\}$, \begin{E}\forb(m, F_2(0,q,0,0)=\Bigl[\left.
\overbrace{\begin{matrix}1& 1& \cdots &1\\ 0 &0& \cdots &0\end{matrix}}^{q}\right.\Bigr])=\lfloor\frac{q+1}{2}m\rfloor +2.
\hskip 1in\qed\label{q10bd}\end{E}
\end{thm}

Here is a table of bounds for 2-columned $F$ with 1 or 2 rows (using notation for 2-columned configurations).
\vskip 10pt
\begin{tabular}{|c|c|c|}
\hline
Configuration&$\forb(m,F)$&Proof\\
\hline
$F_{1,0,0,0}=\begin{bmatrix}1&1\\   \end{bmatrix}$&$\binom{m}{1}+\binom{m}{0}$
&Thm~\ref{sauer}\\
\hline
$F_{0,1,0,0}=\begin{bmatrix}1&0\\   \end{bmatrix}$&$\binom{m}{0}$
&Thm~\ref{sauer}\\
\hline
$F_{2,0,0,0}=\begin{bmatrix}1&1\\ 1&1\\ 
\end{bmatrix}$&$\binom{m}{2}+\binom{m}{1}+\binom{m}{0}$
&Thm~\ref{sauer}\\
\hline
$F_{1,1,0,0}=\begin{bmatrix}1&1\\ 1&0\\ 
\end{bmatrix}$&$\binom{m}{1}+\binom{m}{0}$
&Thm~\ref{sauer}\\
\hline
$F_{1,0,0,1}=\begin{bmatrix}1&1\\ 0&0\\ 
\end{bmatrix}$&$\binom{m}{1}+\binom{m}{0}+\binom{m}{m}$
&\cite{AFS} or Thm~\ref{repeatedcol}\\
\hline
$F_{0,2,0,0}=\begin{bmatrix}1&0\\ 1&0\\ 
\end{bmatrix}$&$\binom{m}{1}+\binom{m}{0}$
&Thm~\ref{sauer}\\
\hline
$F_{0,1,1,0}=\begin{bmatrix}1&0\\ 0&1\\ 
\end{bmatrix}$&$\binom{m}{1}+\binom{m}{0}$
&Thm~\ref{sauer}\\
\hline
\end{tabular}
\vskip 5pt





\begin{thm}(Thm 2.2  \cite{AFS}) \label{1pp0} Let $p\ge 1$ be given. Then $\forb(m,F_2(1,p,p,0))=pm-p+2$.\qed\end{thm}

\begin{thm}(Thm 2.3  \cite{AFS}) Let $p\ge 1$ be given. Then
$\forb(m,F_2(1,p,1,1))
\le
(p-\frac{1}{2})m+1.\qed$\end{thm}




\begin{thm}(Thm 3.4 \cite{AFS}) We have $\forb(m,F_2(1,2,2,1))=\lfloor\frac{m^2}{4}\rfloor+m+1.$\qed\end{thm}

\begin{thm}(Thm 3.3 \cite{AFS}) Let $p\ge 4$ be given. There exists an $m_0$ and a $c$ so that for $m\ge m_0$ and $m\ge 4(p-1)^{3/2}$,
$$\frac{m^2}{4}+(p-1\frac{1}{2}-{\sqrt p-1})m+O(p)
\le \forb(m,F_2(1,p,p,1))
\le \frac{m^2}{4}+(p-1)(m-2)+c.\qed$$\end{thm}

The following result follows from forbidding the $2\times r$ block of 0's and so the bounds in
\cite{AF} yield the result.

\begin{thm}(Thm 3.1 \cite{AFS}) Let $r,p,q,s$ be given with  $r\ge 2$, $r\ge p,q,s$. Then
$$\forb(m,F_2(r,0,0,0))=\forb(m,F_2(r,p,q,s))=\frac{r+1}{6}m^2+O(m). \qed$$\end{thm}

The bounds do grow for larger $p$ as the coefficient of $m^2$ increases from
$\frac{r+1}{6}$ to $\frac{r-1}{2}$.

\begin{thm}(Thm 3.6 \cite{AFS}) Let $r,p,q,s$ be given with $r,p,s\ge 2$ and $r\ge s$. Then
$$\forb(m,F_2(r,p,p,s))\le \frac{r-1}{2}m^2+O(m),$$
and for $r,s\ge 3$,
$$\lim_{p\longrightarrow\infty}\frac{\forb(m,F_2(r,p,p,s))}{m^2}= \frac{r-1}{2}.\qed$$
 \end{thm}

The following (Theorem 3.5 \cite{AFS}) would be a useful (and somewhat surprising) tool in extending exact bounds.

\begin{thm}Let $r,p,q,s$ be given with  $2\le p<q$. If there exist $a,b,c$ with
$\forb(m,F_2(r,p,p,s))\le am^2+bm+c$ and $a,b>0$, then there exists an $m_0$ (depending on $r,p,q,s,a$) so that for $m\ge m_0$  then
$\forb(m,F_2(r,p,q,s))\le am^2+bm+c$.
\end{thm}

%----------------3 rowed configurations------------

\section{$F$ is a $3\times \l$ (0,1)-matrix}\label{k=3}
  
For the case $F$ is $3\times \l$, the asymptotic classification of $\forb(m,F)$ is begun in \cite{AGS}, \cite{AFS} and was completed in \cite{AS05}.
The following configurations are
needed for Theorem~\ref{classifyk=3}. We will number them consecutively $F_1,F_2,\ldots$ for this section etc. and will reuse the names applied to different matrices in \srf{k=4} and \srf{simplek=5}.

$$F_1=\begin{bmatrix}1\\ 0\\ 0\\\end{bmatrix},
\qquad F_2=\begin{bmatrix}1&0&1&0\\ 0&1&1&1\\ 0&0&0&1\\\end{bmatrix},
\qquad F_3=\begin{bmatrix}1&0&1&0\\ 0&1&0&1\\ 0&0&1&1\\\end{bmatrix},
$$
$$F_4(t)=\left[\begin{matrix}\cr \cr \cr\end{matrix}\right.
\begin{matrix}0\\ 0\\ 0\\ \end{matrix}
\overbrace{\begin{matrix}1\cdots 1\cr 0\cdots 0\cr 0\cdots
0\cr\end{matrix}}^{t}
\overbrace{\begin{matrix}0\cdots 0\cr 1\cdots 1\cr 0\cdots
0\cr\end{matrix}}^{t}
\begin{matrix}0\\ 0\\ 1\\ \end{matrix}
\overbrace{\begin{matrix}1\cdots 1\cr 1\cdots 1\cr 0\cdots
0\cr\end{matrix}}^{t}
\begin{matrix}1\\ 0\\ 1\\ \end{matrix}
\overbrace{\begin{matrix}0\cdots 0\cr 1\cdots 1\cr 1\cdots
1\cr\end{matrix}}^{t}
\begin{matrix}1\\ 1\\ 1\\ \end{matrix}
\left.\begin{matrix}\cr \cr \cr\end{matrix}\right],$$

$$F_5(t)=\left[\begin{matrix}\cr \cr \cr\end{matrix}\right.
\begin{matrix}0\\ 0\\ 0\\ \end{matrix}
\overbrace{\begin{matrix}1\cdots 1\cr 0\cdots 0\cr 0\cdots
0\cr\end{matrix}}^{t}
\overbrace{\begin{matrix}0\cdots 0\cr 1\cdots 1\cr 0\cdots
0\cr\end{matrix}}^{t}
\begin{matrix}0\\ 0\\ 1\\ \end{matrix}\,
\begin{matrix}1\\ 1\\ 0\\ \end{matrix}
\overbrace{\begin{matrix}1\cdots 1\cr  0\cdots 0\cr 1\cdots
1\cr\end{matrix}}^{t}
\overbrace{\begin{matrix}0\cdots 0\cr 1\cdots 1\cr 1\cdots
1\cr\end{matrix}}^{t}
\begin{matrix}1\\ 1\\ 1\\ \end{matrix}
\left.\begin{matrix}\cr \cr \cr\end{matrix}\right],$$

$$F_6(t)=\left[\begin{matrix}\cr \cr \cr\end{matrix}\right.
\begin{matrix}0\\ 0\\ 0\\ \end{matrix}
\overbrace{\begin{matrix}1\cdots 1\cr 0\cdots 0\cr 0\cdots
0\cr\end{matrix}}^{t}
\overbrace{\begin{matrix}0\cdots 0\cr 1\cdots 1\cr 0\cdots
0\cr\end{matrix}}^{t}
\overbrace{\begin{matrix}0\cdots 0\cr 0\cdots 0\cr 1\cdots
1\cr\end{matrix}}^{t}
\overbrace{\begin{matrix}1\cdots 1\cr 1\cdots 1\cr 0\cdots
0\cr\end{matrix}}^{t}
\overbrace{\begin{matrix}1\cdots 1\cr 0\cdots 0\cr 1\cdots
1\cr\end{matrix}}^{t}
\left.\begin{matrix}\cr \cr \cr\end{matrix}\right].$$


\begin{thm}\label{classifyk=3}  Let $F$ be a $3\times \l$
(0,1)-matrix.\hfill\break
(Linear Cases) If $F$  has at least one column and if $F$ is a
configuration in $F_2$ then $\forb(m,F)=\Theta(m)$.\hfill\break
(Quadratic Cases) If $F$  has at least one configuration from $K_3^0$, $K_3^1$,
$K_3^2$, $K_3^3$, $2\cdot F_1$, $2\cdot F_1^c$ or $F_3$ and if $F$ is
a configuration in
$F_4(t)$, $F_5(t)$, $F_6(t)$ or  $F_6(t)^c$ for some $t\ge 1$, then
$\forb(m,F)=\Theta(m^2)$.\hfill\break
(Cubic Cases) If $F$  has at least one configuration from $2\cdot K_3^0$, 
$[2\cdot K_3^1 | K_3^2]$,  $[2\cdot K_3^1 | K_3^3]$, $[K_3^0 | 2\cdot K_3^2]$,
$[K_3^1 | 2\cdot K_3^2]$ or  $2\cdot K_3^3$ then
$\forb(m,F)=\Theta(m^3)$.\hfill\break
In addition, any $3\times \l$ (0,1)-matrix $F$ will fall into one of the three Cases.
\end{thm}

\proof The linear bound for $\forb(m,F_2)$ is Theorem 3.3\cite{AGS}. The
quadratic bound for $\forb(m,F_4(t))$ is Theorem 3.9\cite{AGS}.
The quadratic bound for $\forb(m,F_5(t))$ is
Theorem 4.2 in \cite{AS05} and the quadratic bound for $\forb(m,F_6(t))$ is
Theorem 4.1 in \cite{AS05}.  The cubic bound for all 3-rowed $F$ follows
from Theorem~\ref{general} above. All the lower bounds follow from the constructions given
in Conjecture~\ref{grand} but had been developed as follows.
Quadratic lower bounds for $\forb(m,K_3^1),\forb(m,K_3^2), \forb(m,F_3)$ are
in Corollary 3.5\cite{AGS}, quadratic lower bound for
$\forb(m,K_3^3)$ (and hence $\forb(m,K_3^0)$ by taking the
0-1-complement) is in Theorem 3.6\cite{AGS}, quadratic lower bound
for $\forb(m,2\cdot F_1)$ (and hence $\forb(m,2\cdot F_1^c)$) is in
Theorem 3.7\cite{AGS}. A cubic lower bound for $\forb(m,2\cdot K_3^3)$ (and
hence $\forb(m,2\cdot K_3^0)$) is in Theorem 3.9\cite{AGS} and cubic
lower bounds for $\forb(m,[2\cdot K_3^2|K_3^0])$ and
$\forb(m,[2\cdot K_3^2|K_3^1])$ (and hence also for $\forb(m,[2\cdot
K_3^1|K_3^3])$,$\forb(m,[2\cdot K_3^1|K_3^2])$) are in  Theorem
3.10\cite{AGS}.\qed

\vskip 10pt 
There are a number of exact results. 

\begin{thm}\label{F_2} (Theorem 3.3 \cite{AGS}) $\forb(m,F_2)=2m$.\qed\end{thm}

\begin{thm}\label{F_3} $\forb(m,F_3)=\lfloor m^2/4\rfloor+m+1$.\end{thm}
\proof The construction of taking $[K_{m/2}^0\,|\,T_{m/2}]\times
[K_{m/2}^0\,|\,T_{m/2}]$ is Theorem 3.4 \cite{AGS}. To prove the bound, one can use  shifting (Section \ref{shifting}) and Theorem~\ref{shiftingineq}. The number of different columns of $A_{|_S}$ on a given set $S$ with $|S|=3$ is at most 6 and so the same is true for the shifted matrix $T(A)$. But then since $T(A)$ is a downset, all columns in $T(A)$ have at most 2 1's and considering the columns of 2 1's as edges of a graph on a vertex set identified with the rows, we see that the graph has no triangles on any triple $S$
(or $T(A)_{|_S}$ would have 7 different columns). Thus by Mantel's bound (Tur\'an) there are at most $\lfloor m^2/4\rfloor$ columns of 2 1's and up to $m+1$ additional columns of less than 2 1's. \qed

$$\qquad\hbox{Let }\qquad F_7(k)= 
\left[\begin{matrix}1&1&1\\ 1&1&1\\ 
\vdots&\vdots&\vdots\\
1&1&1\\ 1&0&0\end{matrix}\right] \begin{matrix}\left.\begin{matrix}\\ \\ \\ \\ \end{matrix}\right\}{k-1}
\\
\\ \end{matrix}.$$
Note that $F_7(3)$ is  in Table 2. The generality of this result for larger $k$ costs nothing.



\begin{thm}\label{matcharg}\cite{AKarp} 
Let $m$ be given. 
$$\forb(m,F_7(3))
=\forb(3\cdot\1_2\0_0)\le\frac{4}{3}\binom{m}{2}+\binom{m}{1}+\binom{m}{0},$$
with equality if $m\equiv 1,3(\hbox{mod }6)$. Let $k$ be given.
\begin{E}\hbox{then }\forb(m,F_7(k))=\forb(m,3\cdot\1_{k-1})
\le\frac{k+1}{k}\binom{m}{k-1}+\binom{m}{k-2}+\cdots +\binom{m}{0},
\label{q1(k-1)bd}\end{E}
with equality if there exists a design on $[m]$ of blocks of size $k$ such that for each subset $S\in\binom{[m]}{k-1}$, there is exactly one block of size $k$ containing it. \qed
\end{thm}


We have the following exact bound (for large $m$) which is Theorem 1.5 in \cite{AB}.  A pigeonhole argument yields a bound that exceeds the bound below by a linear amount and 
for small $m$ the larger pigeonhole bound can be achieved.


\begin{thm}\cite{AB}\label{q110} Let $q>2$ be given. There exists a constant $M$ so that for $m>M$, 
\begin{E}\forb(m,q\cdot (\1_2\0_1)=
\left[\begin{matrix}\\ \\ \\\end{matrix}\right.
\overbrace{\begin{matrix}1& 1& \cdots &1\\ 1&1&\cdots &  1\\ 0 &0& \cdots &0\end{matrix}}^{q}
\left.\begin{matrix}\\ \\ \\\end{matrix}\right]
)\le m+2+\frac{q+1}{3}\binom{m}{2},\label{q110bd}\end{E}
with equality for $m\equiv 1,3(\hbox{mod }6)$.\qed\end{thm}

A number of exact results follow from the following result. 

\begin{thm}\label{3rowed110}\cite{AKarp}
Let $F$ be one of the following three matrices:
$$
\begin{bmatrix}
1&1&1&0&0\\
1&1&0&1&0\\
0&0&1&0&0\\
\end{bmatrix},
\quad
\begin{bmatrix}
1&1&1&0&0\\
1&1&0&1&0\\
0&0&0&0&0\\
\end{bmatrix},
\quad
\begin{bmatrix}
1&1&1&1&0&0\\
1&1&0&0&0&0\\
0&0&1&0&1&0\\
\end{bmatrix}.$$
Then for $m \ge 3$,
$\forb(m,F) = \forb(m, 2\cdot \1_2\0_1) = \forb(m, \1_3\0_1)$.\qed
\end{thm}

The following two results were obtained with the assistance of a Genetic Algorithm. Here a genetic algorithm suggested both the bound and the structure of matrices that achieve the bound. Moreover it was used to help in the inductive steps by predicting the structures that would be encountered.
$$V=\begin{bmatrix}
1 & 1 & 0 & 0\\ 
1 & 1 & 0 & 0\\ 
0 & 0 & 1 & 1\\
\end{bmatrix}, \qquad
W=\begin{bmatrix}
1 & 1 & 1 & 1\\
1 & 1 & 0 & 0\\
0 & 0 & 1 & 1\\
\end{bmatrix}.$$
\begin{thm}\label{Wthm}\cite{genetic} Let $m\ge 2$. Then  $\forb(m,W) = \binom{m}{2} +2m - 1$.\qed\end{thm}

\begin{thm}\label{Vthm}\cite{genetic} Let $m\ge 6$. Then $\forb(m,V) = \binom{m}{2}+m+4$.\qed\end{thm}

\vskip 10pt

{\bf $3\times 2$ Forbidden Configurations}
\vskip 5pt
\begin{tabular}{|c|c|c|}
\hline
Configuration&$\forb(m,F)$&Proof\\
\hline
$F_{3,0,0,0}=\begin{bmatrix}1&1\\ 1&1\\ 1&1\\ 
\end{bmatrix}$&$\binom{m}{3}+\binom{m}{2}+\binom{m}{1}+\binom{m}{0}$
&Thm~\ref{2K_k}\\
\hline
$F_{2,1,0,0}=\begin{bmatrix}1&1\\ 1&1\\ 1&0\\ \end{bmatrix}$&$\binom{m}{2}+\binom{m}{1}+\binom{m}{0}$&Thm~\ref{sauer}\\
\hline
$F_{2,0,0,1}=\begin{bmatrix}1&1\\ 1&1\\ 0&0\\ 
\end{bmatrix}$&$\binom{m}{2}+\binom{m}{1}+\binom{m}{0}+\binom{m}{m}$&Thm~\ref{repeatedcol}\\
\hline
$F_{1,2,0,0}=\begin{bmatrix}1&1\\ 1&0\\ 1&0\\
\end{bmatrix}$&$\binom{m}{2}+\binom{m}{1}+\binom{m}{0}$
&Thm~\ref{sauer}\\
\hline
$F_{1,1,1,0}=\begin{bmatrix}1&1\\ 1&0\\ 0&1\\ \end{bmatrix}$&$2m$
&Thm 3.3 in \cite{AGS}\\
\hline
$F_{1,1,0,1}=\begin{bmatrix}1&1\\  1&0\\ 0&0\\ 
\end{bmatrix}$&$\binom{m}{1}+\binom{m}{0}+\binom{m}{m}$
&Thm 3.2 in \cite{AGS} (Thm~\ref{repeatedcol})\\
\hline
$F_{0,3,0,0}=\begin{bmatrix}1&0\\ 1&0\\ 1&0\\ 
\end{bmatrix}$&$\binom{m}{2}+\binom{m}{1}+\binom{m}{0}$
&Thm~\ref{sauer}\\
\hline
$F_{0,2,1,0}=\begin{bmatrix}1&0\\ 1&0\\ 0&1\\ \end{bmatrix}$&$\lfloor 
3m/2\rfloor+1$
&Thm 3.1 in \cite{AGS}\\
\hline
\end{tabular}

\vfill\eject
{\bf $3\times 3$ Forbidden Configurations}
\vskip 5pt
\begin{tabular}{|c|c|c|}
\hline
Configuration $F$&$\forb(m,F)$&Proof\\
\hline 
$\begin{bmatrix}1&1&1\\ 1&1&0\\ 1&0&1\\ \end{bmatrix}$,
$\begin{bmatrix}1&1&1\\ 1&1&0\\ 1&0&0\\ \end{bmatrix}$,
$\begin{bmatrix}1&1&0\\ 1&1&0\\ 1&0&1\\ \end{bmatrix}$,
&&\\ 
$\begin{bmatrix}1&1&0\\ 1&1&0\\ 1&0&0\\ \end{bmatrix}$
 or 
$\begin{bmatrix}1&1&0\\ 1&0&0\\ 1&0&0\\ \end{bmatrix}$
&\large{$\binom{m}{2}+\binom{m}{1}+\binom{m}{0}$}
&Thm~\ref{sauer}\\
\hline 
$\begin{bmatrix}1&1&0\\ 1&0&1\\ 0&1&1\\
\end{bmatrix}$&\large{$\binom{m}{2}+\binom{m}{1}+\binom{m}{0}$}
&Thm~\ref{K_k^s}\\
\hline
$\begin{bmatrix}1&1&1\\ 1&0&0\\ 0&1&0\\ \end{bmatrix}$
 or 
$\begin{bmatrix}1&1&0\\ 1&0&1\\ 0&1&0\\ \end{bmatrix}$
&$2m$
&\cite{AGS}\\
\hline 
$\begin{bmatrix}1&1&1\\ 1&1&1\\ 1&1&1\\ \end{bmatrix}$
&\large{$\frac{5}{4}\binom{m}{3}+\binom{m}{2}+\binom{m}{1}+\binom{m}{0}$}
&Thm~\ref{tKk}\\
\hline
$\begin{bmatrix}1&1&1\\ 1&1&1\\ 1&1&0\\ \end{bmatrix}$, 
$\begin{bmatrix}1&1&1\\ 1&1&0\\ 1&1&0\\ \end{bmatrix}$ or 
$\begin{bmatrix}1&1&0\\ 1&1&0\\ 1&1&0\\ \end{bmatrix}$
&\large{$\binom{m}{3}+\binom{m}{2}+\binom{m}{1}+\binom{m}{0}$}
&Thm~\ref{2K_k}\\
\hline
$\begin{bmatrix}1&1&1\\ 1&1&1\\ 0&0&0\\
\end{bmatrix}$
&\large{$\frac{4}{3}\binom{m}{2}
+\binom{m}{1}+\binom{m}{0}+\binom{m}{m}$}
&Thm~\ref{q110}\\
\hline 
$\begin{bmatrix}1&1&1\\ 1&1&1\\ 1&0&0\\
\end{bmatrix}$&
\large{$\frac{4}{3}\binom{m}{2}+\binom{m}{1}+\binom{m}{0}$}
&Thm~\ref{matcharg}\\
\hline
$\begin{bmatrix}1&1&1\\ 1&0&0\\ 1&0&0\\ \end{bmatrix}$,
$\begin{bmatrix}1&1&1\\ 1&1&0\\ 0&0&1\\ \end{bmatrix}$,
&&\\
$\begin{bmatrix}1&1&1\\ 1&1&0\\ 0&0&0\\ \end{bmatrix}$
or
$\begin{bmatrix}1&1&0\\ 1&1&0\\ 0&0&1\\ \end{bmatrix}$
&\large{$\binom{m}{2}+\binom{m}{1}+\binom{m}{0}+\binom{m}{m}$}
&Thm~\ref{3rowed110}\\
\hline
\end{tabular}

\vskip 10pt
It is an exercise to verify that all $3\times 3$ forbidden configurations (or their (0,1)-complements have been included in the table.
We cannot complete the table for $3\times 4$ matrices but perhaps it is instructive to see how many are solved by the general results. I've organized the cases by first considering the number of columns of 3 1's and then the number of columns $\1_2\0_1$.

\vfill\eject
{\bf $3\times 4$ Forbidden Configurations}
\vskip 5pt

\begin{tabular}{|c|c|c|}
\hline
Configuration&$\forb(m,F)$&Proof\\
\hline
$\begin{bmatrix}1&1&1&1\\ 1&1&1&1\\ 1&1&1&1\\ \end{bmatrix}$
&\large{$\frac{6}{4}\binom{m}{3}+\binom{m}{2}+\binom{m}{1}+\binom{m}{0}$}
&Thm~\ref{tKk}, $t=4$\\
\hline
$\begin{bmatrix}1&1&1&1\\ 1&1&1&1\\ 1&1&1&0\\ \end{bmatrix}$,
$\begin{bmatrix}1&1&1&1\\ 1&1&1&0\\ 1&1&1&0\\ \end{bmatrix}$,
&&\\
$\begin{bmatrix}1&1&1&0\\ 1&1&1&0\\ 1&1&1&0\\ \end{bmatrix}$

&\large{$\frac{5}{4}\binom{m}{3}+\binom{m}{2}+\binom{m}{1}+\binom{m}{0}$}
&Thm~\ref{tKk}, $t=3$\\
\hline
$\begin{bmatrix}1&1&1&1\\ 1&1&1&1\\ 1&1&0&0\\ \end{bmatrix}$,
$\begin{bmatrix}1&1&1&1\\ 1&1&1&0\\ 1&1&0&1\\ \end{bmatrix}$,
&&\\
$\begin{bmatrix}1&1&1&1\\ 1&1&1&0\\ 1&1&0&0\\ \end{bmatrix}$,
$\begin{bmatrix}1&1&1&0\\ 1&1&1&0\\ 1&1&0&1\\ \end{bmatrix}$,
&\large{$\binom{m}{3}+\binom{m}{2}+\binom{m}{1}+\binom{m}{0}$}
&Thm~\ref{2K_k} \\
$\begin{bmatrix}1&1&1&0\\ 1&1&1&0\\ 1&1&0&0\\ \end{bmatrix}$,
$\begin{bmatrix}1&1&1&1\\ 1&1&0&0\\ 1&1&0&0\\ \end{bmatrix}$,
&&\\
$\begin{bmatrix}1&1&1&0\\ 1&1&0&1\\ 1&1&0&0\\ \end{bmatrix}$,
$\begin{bmatrix}1&1&1&0\\ 1&1&0&0\\ 1&1&0&0\\ \end{bmatrix}$, 
&&\\ 
$\begin{bmatrix}1&1&0&0\\ 1&1&0&0\\ 1&1&0&0\\ \end{bmatrix}$
&&\\
  
\hline
$\left[\begin{matrix}1&1&1&1\\ 1&1&1&1\\ 1&0&0&0\\ \end{matrix}\right]$,
$\left[\begin{matrix}1&1&1&1\\ 1&1&1&0\\ 1&0&0&1\\ \end{matrix}\right]$,
&&\\
$\left[\begin{matrix}1&1&1&1\\ 1&1&1&0\\ 1&0&0&0\\ \end{matrix}\right]$,
$\left[\begin{matrix}1&1&1&0\\ 1&1&1&0\\ 1&0&0&1\\ \end{matrix}\right]$,
&Exact bounds not known
&\\
 or $\left[\begin{matrix}1&1&1&0\\ 1&1&1&0\\ 1&0&0&0\\ \end{matrix}\right]$&&\\
\hline
\end{tabular}
\vfill
\eject
\begin{tabular}{|c|c|c|}
\hline
Configuration&$\forb(m,F)$&Proof\\
\hline
$\left[\begin{matrix}1&1&1&0\\ 1&1&0&1\\ 1&0&1&1\\ \end{matrix}\right]$,
$\left[\begin{matrix}1&1&1&1\\ 1&1&0&0\\ 1&0&1&0\\ \end{matrix}\right]$,
&&\\
$\left[\begin{matrix}1&1&1&0\\ 1&1&0&1\\ 1&0&1&0\\ \end{matrix}\right]$,
$\left[\begin{matrix}1&1&1&0\\ 1&1&0&0\\ 1&0&1&0\\ \end{matrix}\right]$,
&\large{$\binom{m}{2}+\binom{m}{1}+\binom{m}{0}$}
&Thm~\ref{sauer} \\
$\left[\begin{matrix}1&1&1&0\\ 1&1&0&1\\ 1&0&0&0\\ \end{matrix}\right]$, 
$\left[\begin{matrix}1&1&1&0\\ 1&1&0&0\\ 1&0&0&1\\ \end{matrix}\right]$,
&&\\
$\left[\begin{matrix}1&1&1&0\\ 1&1&0&0\\ 1&0&0&0\\ \end{matrix}\right]$,
$\left[\begin{matrix}1&1&0&0\\ 1&1&0&0\\ 1&0&1&0\\ \end{matrix}\right]$,
&&\\
or $\left[\begin{matrix}1&1&0&0\\ 1&0&1&0\\ 1&0&0&1\\ \end{matrix}\right]$
&&\\
\hline
$ \left[\begin{matrix}1&1&1&1\\ 1&1&1&1\\ 0&0&0&0\\ \end{matrix}\right]$
&\large{$\frac{5}{3}\binom{m}{2}+\binom{m}{1}+\binom{m}{0}+\binom{m}{m}$}
&Theorem~\ref{q110}\\
\hline
$\left[\begin{matrix}1&1&1&1\\ 1&1&1&0\\ 0&0&0&1\\ \end{matrix}\right]$,
$\left[\begin{matrix}1&1&1&1\\ 1&1&1&0\\ 0&0&0&0\\ \end{matrix}\right]$
&&\\
$\left[\begin{matrix}1&1&1&0\\ 1&1&1&0\\ 0&0&0&1\\ \end{matrix}\right]$,
$ \left[\begin{matrix}1&1&1&0\\ 1&1&1&0\\ 0&0&0&0\\ \end{matrix}\right]$
&Exact bounds not known
&\\
\hline 

$\begin{bmatrix}1&1&1&1\\ 1&1&0&0\\ 0&0&1&0\\ \end{bmatrix}$,
$\begin{bmatrix}1&1&1&0\\ 1&1&0&1\\ 0&0&1&0\\ \end{bmatrix}$,
&&\\
$\begin{bmatrix}1&1&1&0\\ 1&1&0&0\\ 0&0&1&1\\ \end{bmatrix}$,
$\begin{bmatrix}1&1&1&0\\ 1&1&0&0\\ 0&0&1&0\\ \end{bmatrix}$,
&\large{$\binom{m}{2}+\binom{m}{1}+\binom{m}{0}+\binom{m}{m}$}
&Thm~\ref{3rowed110}\\$\begin{bmatrix}1&1&1&0\\ 1&1&0&1\\ 0&0&0&0\\ \end{bmatrix}$,
$\begin{bmatrix}1&1&1&0\\ 1&1&0&0\\ 0&0&0&1\\ \end{bmatrix}$,
&&\\
$\begin{bmatrix}1&1&1&0\\ 1&1&0&0\\ 0&0&0&0\\ \end{bmatrix}$
or
$\begin{bmatrix}1&1&0&0\\ 1&1&0&0\\ 0&0&1&0\\ \end{bmatrix}$
&&\\
\hline
\end{tabular}
\vfill
\eject
\begin{tabular}{|c|c|c|}
\hline
Configuration&$\forb(m,F)$&Proof\\
\hline
$\begin{bmatrix}1&1&1&1\\ 1&1&0&0\\ 0&0&1&1\\ \end{bmatrix}$
&$\binom{m}{2}+\binom{m}{1}+\binom{m}{0}+m-2$&Thm~\ref{Wthm}\\
\hline
$\begin{bmatrix}1&1&0&0\\ 1&1&0&0\\ 0&0&1&1\\ \end{bmatrix}$
&$\binom{m}{2}+\binom{m}{1}+\binom{m}{0}+3$&Thm~\ref{Vthm}\\
\hline
$\begin{bmatrix}1&1&1&0\\ 1&1&0&1\\ 0&0&1&1\\ \end{bmatrix}$
&Exact bound not known
&\\
\hline
$\begin{bmatrix}1&1&1&1\\ 1&1&0&0\\ 0&0&0&0\\ \end{bmatrix}$&$\binom{m}{2}+m+2$&Thm~\ref{4x4critical}\\
\hline
$\left[\begin{matrix}1&1&0&1\\ 1&0&1&0\\ 0&1&1&0\\ \end{matrix}\right]$
&$\binom{m}{2}+\binom{m}{1}+\binom{m}{0}$&Thm~\ref{K_k^s}\\
\hline 
$\left[\begin{matrix}1&1&1&0\\ 1&0&0&1\\ 0&1&0&0\\ \end{matrix}\right]$ 
&2m&Thm~\ref{F_2}\\
\hline
$\left[\begin{matrix}1&1&0&0\\ 1&0&1&0\\ 0&1&0&1\\ \end{matrix}\right]$ 
&\large{$\left\lfloor\frac{m^2}{4}\right\rfloor+\binom{m}{1}+\binom{m}{0}$}
&Thm~\ref{F_3} \\
\hline
\end{tabular}





%-----------------4 rowed F

\section{$F$ is a $4\times \l$ (0,1)-matrix}\label{k=4}

In this section we begin by considering $F$ to be itself a simple matrix. For the case that $F$ is simple and $4\times \l$, the asymptotic classification of $\forb(m,F)$ was completed by Balin Fleming \cite{AFl10}. The main tools are Theorem~\ref{simple,k-2} and Corollary~\ref{subsauer}.

We are able to establish the complete classification for the asymptotics of $\forb(m,F)$ for any $4\times \l$ simple matrix $F$ and the result is consistent with the conjecture. To state the result we need a number of matrices.  We will number them consecutively $F_1,F_2,\ldots$ for this section etc. and will reuse the names for different matrices than those used in  \srf{k=3} and \srf{simplek=5}.
$$F_1=\begin{bmatrix}1\\ 1\\ 0\\ 0\\\end{bmatrix}, \quad 
F_2=\begin{bmatrix}1&1\\ 1&0\\ 0&1\\ 0&0\\\end{bmatrix},\quad F_3=\begin{bmatrix}1\\ 1\\ 1\\ 0\\\end{bmatrix}, \quad 
F_4=\begin{bmatrix}1&0\\ 1&0\\ 0&1\\ 0&1\\\end{bmatrix}, \quad
F_5=\begin{bmatrix}1&0&0\\ 0&1&0\\ 0&0&1\\ 1&1&1\\\end{bmatrix},$$

$$F_6\hbox{=}\left[\begin{array}{@{}cccccccc@{}}1&0&1&1&1&0&1&1\\ 0&1&1&0&1&1&0&0\\ 0&0&1&1&0&1&0&1\\ 0&0&0&1&0&0&1&0\\\end{array}\right],
F_7\hbox{=}\left[\begin{array}{@{}cccccccc@{}}1&0&1&1&1&1&0&1\\ 0&1&1&1&1&0&1&0\\ 0&0&1&0&0&0&1&1\\ 0&0&0&1&0&1&0&0\\\end{array}\right],$$
$$F_8\hbox{=}\left[\begin{array}{@{}cccccc@{}}1&0&1&0&0&1\\ 0&1&0&1&1&0\\ 0&0&1&1&1&1\\ 0&0&1&1&0&0\\\end{array}\right],$$

$$F_9=\begin{bmatrix}1&0&0\\ 0&1&0\\ 0&0&1\\ 0&0&1\\\end{bmatrix}, F_{10}=\begin{bmatrix}1&0&0\\ 0&1&0\\ 0&0&1\\ 0&0&0\\\end{bmatrix},$$  $$F_{11}=\begin{bmatrix}1&0&1&0\\ 1&0&0&1\\ 0&1&1&0\\ 0&1&0&1\\\end{bmatrix}, F_{12}=\begin{bmatrix}1&0&0&1\\ 0&1&0&1\\ 0&0&1&1\\ 1&1&1&0\\\end{bmatrix}, F_{13}=\begin{bmatrix}1&1&0&0\\ 0&1&1&0\\ 0&1&0&1\\ 0&0&1&1\\\end{bmatrix}.$$

\begin{thm}\label{classifyk=4}  Let $F$ be a $4\times \l$ simple matrix.\hfill\break
(Linear Cases) If $F$  has a configuration $F_1$  and if $F$ is a configuration in $F_2$ then $\forb(m,F)=\Theta(m)$.\hfill\break
(Quadratic Cases) If $F$  has a configuration  $F_3$, $F_3^c$, $F_4$, $F_5$, or $F_5^c$ and if $F$ is a configuration in
$F_6$, $F_7$, or  $F_8$, then  $\forb(m,F)=\Theta(m^2)$.\hfill\break
(Cubic Cases) If $F$  has a configuration $K_4^0$, $F_9$, $F_9^c$,  $F_{10}$, $F_{10}^c$, $F_{11}$,  $F_{12}$, $F_{12}^c$, $F_{13}$, 
 or  $K_4^4$ then  $\forb(m,F)=\Theta(m^3)$.\hfill\break
In addition, any $4\times \l$ simple matrix $F$ will fall into one of the three Cases.
\end{thm}


\proof The lower bounds are established by constructions of \corf{grand}.
For definiteness, note that $F_1\notin I$, $F_3\notin I\times I$, $F_4\notin T\times I$, $F_5\notin  I^c\times I^c$, $K_4^0, F_9, F_{10}\notin I^c\times I^c\times I^c$, $F_{11}, F_{12}, F_{13}\notin T\times T\times T$. The arguments are not entirely trivial. We see that any two rows of $I^c$ do not have $\begin{bmatrix}0\\ 0\\\end{bmatrix}$ and so a $k$-rowed matrix which has $\begin{bmatrix}0\\ 0\\\end{bmatrix}$ on every pair of rows is not a configuration in the $k-1$-fold product $I^c\times I^c\times\cdots\times I^c$. Similarly,
any two rows of $T$ do not have $\begin{bmatrix}1&0\\ 0&1\\\end{bmatrix}$ and so a $k$-rowed matrix which has $\begin{bmatrix}1&0\\ 0&1\\\end{bmatrix}$ on every pair of rows is not a configuration in the ($k-1$)-fold product $T\times T\times\cdots\times T$. This was noted following Corollary 3.5 in \cite{AGS}.   Theorem~\ref{twocol}, Theorem~\ref{simple,k-2} and Theorem~\ref{sauer}  establish the upper bounds. 


To show that any $4\times \l$ matrix $F$ is included in one of the three categories, assume that $F$ is a matrix that falls into neither the linear case or the cubic case. For convenience, think of a column of column sum 2 as an edge $(i,j)$ if the column has 1's in rows $i,j$. A matrix $F$ falls into the linear case only if
$F=F_1$ or $F=F_2$.  Examining the configurations $K_4^0$, $F_9$, $F_9^c$,  $F_{10}$, $F_{10}^c$, $F_{11}$, $F_{11}$, $F_{12}$, $F_{12}^c$, $F_{13}$, $F_{13}^c$
 or  $K_4^4$, we deduce that $F$ cannot have a column of all 0's ($K_4^0$)or a column of all 1's ($K_4^4$). $F$ has at most two columns of column sum 1 and at most two columns of column sum 3 (using $F_{10},F_{10}^c$). In addition four edges forming a four cycle  yields $F_{11}$ and so there are at most 4 edges in $F$ which must be a subgraph of a triangle plus one edge from the triangle to the remaining vertex. (From this and Corollary~\ref{subsauer} it follows that any  4-rowed configuration with a quadratic bound has at most 8 column types).

If $F$ has no columns of either three 1's or three 0's then, assuming it is not $F_1$ or $F_2$, it must contain two disjoint edges and hence $F_4$ or have three columns of column sum 2  forming a triangle  ($F_5^c$) or three columns of column sum 2  sharing a vertex ($F_5$).   \qed

For the general case $F$ is $4\times \l$, the asymptotic classification of $\forb(m,F)$ is not complete but we can use the conjecture to predict the answer.
 The following configurations are
needed for Conjecture~\ref{classifynotsimplek=4}:


$$F_6(t)=\left[\begin{matrix}1&0&1&1\\ 0&1&1&0\\  0&0&1&1\\ 0&0&0&1\\ \end{matrix}\right. \, t\cdot\left[\begin{matrix}1&0&1&1\\ 1&1&0&0\\ 0&1&0&1\\ 0&0&1&0\\ \end{matrix}\right] \left.\begin{matrix}\\ \\ \\ \\ \end{matrix}\right],$$
$$F_7(t)=\left[\begin{matrix}1&0&1&1\\ 0&1&1&1\\  0&0&1&0\\ 0&0&0&1\\ \end{matrix}\right. \, t\cdot\left[\begin{matrix}1&1&0&1\\ 1&0&1&0\\ 0&0&1&1\\ 0&1&0&0\\ \end{matrix}\right] \left.\begin{matrix}\\ \\ \\ \\ \end{matrix}\right],
F_8(t)=
\left[\begin{matrix}1&0&1&0\\ 0&1&0&1\\  0&0&1&1\\ 0&0&1&1\\ \end{matrix}\right. \, t\cdot\left[\begin{matrix}0&1\\ 1&0\\ 1&1\\ 0&0\\ \end{matrix}\right] \left.\begin{matrix}\\ \\ \\ \\ \end{matrix}\right],$$



$$B_1=\begin{bmatrix}0&0&0&0&1\\0&0&0&1&1\\0&0&1&1&1\\0&1&1&1&1\\\end{bmatrix},
  B_2=\begin{bmatrix}0&0&0&1&1\\0&0&0&1&1\\0&0&1&1&1\\0&1&1&0&1\\\end{bmatrix},
  B_3=\begin{bmatrix}0&0&0&1&1\\0&0&0&1&1\\0&0&1&0&1\\0&1&1&1&1\\\end{bmatrix},$$
$$B_4=\begin{bmatrix}0&0&0&0&1\\0&0&1&1&1\\0&0&1&1&1\\0&1&0&1&1\\\end{bmatrix},
  B_5=\begin{bmatrix}0&0&0&1&1\\0&0&1&1&1\\0&0&1&0&1\\0&1&0&1&1\\\end{bmatrix},
  B_6=\begin{bmatrix}0&0&0&1&1\\0&0&1&1&1\\0&0&1&1&1\\0&1&0&0&1\\\end{bmatrix},$$
$$D_{12}=
\left[\begin{array}{ccccccccccc}
0&0&0&0&0&0&0&1&1&1&1\\
0&0&0&1&1&1&1&0&0&0&0\\
1&0&1&0&1&0&1&0&1&0&1\\
0&1&1&0&0&1&1&0&0&1&1\\\end{array}\right].$$
\begin{thm}\cite{F8} Let $t$ be given. Then $\forb(m,F_8(t))$ is $\Theta(m^2)$.\qed\end{thm}
\begin{conj}\label{classifynotsimplek=4}  Let $F$ be a $4\times \l$
(0,1)-matrix.\hfill\break
(Linear Cases) If $F$  has $F_1$ as a configuration and if $F$ is a
configuration in $F_2$ then $\forb(m,F)=\Theta(m)$.\hfill\break
(Quadratic Cases) If $F$  has at least one configuration from $F_3$, $F_3^c$, $F_4$, $F_5$, $F_5^c$ or $2\cdot F_1$, 
and if $F$ is a configuration in $F_6(t)$, $F_7(t)$ or $F_8(t)$ for some $t$
, then
$\forb(m,F)=\Theta(m^2)$.\hfill\break
(Cubic Cases) If $F$  has at least one configuration from $K_4^0$, $2\cdot F_3$, 
$F_9$, $F_9^c$, $F_{10}$, $F_{10}^c$, $F_{11}$, $F_{12}$, $F_{12}^c$, $F_{13}$, $2\cdot F_3^c$ or $K_4^4$ and if $F$ is
a configuration in
$[K_4\,|\,t\cdot[K_4-B_i]]$ or $[K_4\,|\,t\cdot[K_4-B_i]]^c$ for $i=1,2,\ldots 6$
or $[K_4^0\,|\,t\cdot D_{12}]$ then
$\forb(m,F)=\Theta(m^3)$.\hfill\break
(Quartic Cases) If $F$  has at least one configuration from $2\cdot K_4^0$, 
$[2\cdot K_4^2]$,  $[2\cdot K_4^4]$ or $[2\cdot K_4^1|C]$ or $[2\cdot K_4^1|C]^c$ where $C$ is one of $K_4^2$, $F_{12}$, $F_9^c$, $F_{10}^c$, $K_4^4$,    then
$\forb(m,F)=\Theta(m^4)$.\hfill\break
In addition, any $4\times \l$ (0,1)-matrix $F$ will fall into one of the four cases.
\end{conj}



The boundary between linear and quadratic follows easily from Theorem~\ref{onecol} and Theorem~\ref{twocol}.  The boundary between quadratic and cubic is partly  proven. The cubic lower bounds are from the constructions.
The boundary between cubic and quartic is in Theorem~\ref{B} and Theorem~\ref{boundary}. The quartic bound of Theorem~\ref{general} completes the cases. We would need to establish $\forb(m,F_6(t))$ and $\forb(m,F_7(t))$ are both quadratic to prove this conjecture. 

\vskip 10pt
The Conjecture~\ref{grand} predicts the following and it would be a helpful first step. 

\begin{prob}\label{4by4} Is $\forb(m,t\cdot F_4)$ equal to $\Theta(m^2)$ for $t\ge 3$? \qed\end{prob}

An argument special for the case $t=2$ proves the following:

\begin{thm}\cite{Aunpub} We have that $\forb(m,2\cdot F_4)$ is $\Theta(m^2)$. \qed\label{twiceF0220}\end{thm}

An exact bound for $F_4=F_{0,2,2,0}$ follows from a result of Frankl, F\"uredi, Pach \cite{FFP} who asked the following problem (which can be viewed as a forbidden submatrix problem).

\begin{thm}\label{one-way}\cite{FFP} Let $f(n,k)$ denote the length of the longest sequence \hfil\break $\{S_1,S_2,\ldots \}$ of distinct subsets of $[m]$ such that
$|S_i\backslash S_j|<k$ for all $i<j$.  Then \hfill\break
$f(m,2)= \binom{m}{2}+2m-1$ and $f(m,k)<\binom{m}{k}+5k^2\binom{m}{k-1}$.\end{thm}

Without loss of generality we may assume the sequence of sets is in non-decreasing order by cardinality. Now consider any simple $m$-rowed matrix  which has no configuration $F_{0,k,k,0}$. If we reorder the columns so that columns sums are never decreasing from left to right then the resulting matrix has no submatrix $F_{0,k,0,0}=[\1_k\,|\,\0_k]$ and so interpreting the columns as subsets of $[m]$, we identify a sequence with the desired property. Moreover,
interpreting the sequence as a simple matrix, the resulting matrix has no
\emph{submatrix} $F_{0,k,0,0}=[\1_k\,|\,\0_k]$ and hence no configuration $F_{0,k,k,0}$. 

\begin{cor}\cite{FFP}\label{4x2} We have $\forb(m,F_4)=\binom{m}{2}+m-2$. \qed\end{cor}

This can also be viewed as a variation of a result of Kleitman \cite{K}. In that result the condition was that pairs of sets $B,C$ have $|B\backslash C|+ |C\backslash B|\le 2t$. The condition of forbidding $F_4$ is slightly weaker than the condition for $t=1$ and so the bound for the result below is slightly larger than Kleitman's bound. The matrices in $\ext(m,F)$ are determined. This is modest progress for Problem~\ref{exactbounds}.


  

We have the following exact bound (for large $m$) which is Theorem 1.6 in \cite{AB}. A pigeonhole argument yields a bound that exceeds the bound below by a linear amount.
For small $m$ the larger pigeonhole bound can be achieved.
\begin{thm}\label{q1100} Let $q>2$ be given. There exists a constant $M$ so that for $m>M$, 
\begin{E}\hbox{forb}(m, q\cdot F_1=
\left[\begin{matrix}\\ \\ \\ \\ \end{matrix}\right.
\overbrace{\begin{matrix}1& 1& \cdots &1\\ 1&1&\cdots &  1\\ 0 &0& \cdots &0\\ 0 &0& \cdots &0\\ \end{matrix}}^{q}
\left.\begin{matrix}\\ \\ \\ \\ \end{matrix}\right])\le 2+2m+\frac{q+3}{3}\binom{m}{2},\label{q1100bd}\end{E}
with equality if in addition $m\equiv 1,3(\hbox{mod }6)$.
Moreover, for $m>M$, if the bound is achieved by an $m$-rowed matrix $A$, then $A$ has all columns of sum 0, 1, 2, $m-2$, $m-1$, $m$ and for some integers $a,b$ with $a+b=q-3$, the columns of sum 3 correspond to a simple $(m,3,a)$-design and the columns of sum $m-3$ correspond to the (0,1)-complement of a simple $(m,3,b)$-design and there are no other columns. \qed\end{thm}

A more general result for $q\cdot(\1_t\0_1)$, and so involving $t$-designs, is proven by Niranjan Balachandran \cite{Balachandran}.

\vfill\eject
{\bf $4\times 2$ Forbidden Configurations}
\vskip 5pt

\begin{tabular}{|c|c|c|}
\hline
Configuration&$\forb(m,F)$&Proof\\
\hline
$F_{4,0,0,0}=\begin{bmatrix}1&1\\ 1&1\\ 1&1\\ 1&1\\ 
\end{bmatrix}$&$\binom{m}{4}+\binom{m}{3}+\binom{m}{2}+\binom{m}{1}+\binom{m}{0}$
&Thm~\ref{sauer}\\
\hline
$F_{3,1,0,0}=\begin{bmatrix}1&1\\ 1&1\\ 1&1\\ 1&0\\ 
\end{bmatrix}$&$\binom{m}{3}+\binom{m}{2}+\binom{m}{1}+\binom{m}{0}$
&Thm~\ref{sauer}\\
\hline
$F_{3,0,0,1}=\begin{bmatrix}1&1\\ 1&1\\ 1&1\\ 0&0\\ 
\end{bmatrix}$&$\binom{m}{3}+\binom{m}{2}+\binom{m}{1}+\binom{m}{0}+\binom{m}{m}$
&Thm~\ref{repeatedcol}\\
\hline
$F_{2,2,0,0}=\begin{bmatrix}1&1\\ 1&1\\ 1&0\\ 1&0\\ 
\end{bmatrix}$&$\binom{m}{3}+\binom{m}{2}+\binom{m}{1}+\binom{m}{0}$
&Thm~\ref{sauer}\\
\hline
$F_{2110}=\begin{bmatrix}1&1\\ 1&1\\ 1&0\\ 0&1\\ \end{bmatrix}$&
$\begin{matrix}\ge(\frac{29}{21})\binom{m}{2}+\binom{m}{1}+\binom{m}{0}\\
\\
\le 2\binom{m}{2}+\binom{m}{1}+\binom{m}{0}\\ \end{matrix}$ &
\cite{ABS}\\
\hline
$F_{2,1,0,1}=\begin{bmatrix}1&1\\ 1&1\\ 1&0\\ 0&0\\ 
\end{bmatrix}$&$\binom{m}{2}+\binom{m}{1}+\binom{m}{0}+\binom{m}{m}$&
Thm~\ref{repeatedcol}\\
\hline
$F_{2,0,0,2}=\begin{bmatrix}1&1\\ 1&1\\ 0&0\\ 0&0\\ 
\end{bmatrix}$&$\binom{m}{2}+\binom{m}{1}+\binom{m}{0}+\binom{m}{m-1}+\binom{m}{m}$&Thm~\ref{repeatedcol}\\
\hline
$F_{1,3,0,0}=\begin{bmatrix}1&1\\ 1&0\\ 1&0\\ 1&0\\ 
\end{bmatrix}$&$\binom{m}{3}+\binom{m}{2}+\binom{m}{1}+\binom{m}{0}$&Thm~\ref{sauer}\\
\hline
\end{tabular}

\vfill\eject
\begin{tabular}{|c|c|c|}
\hline
Configuration&$\forb(m,F)$&Proof\\
\hline
$F_{1,2,1,0}=\begin{bmatrix}1&1\\ 1&0\\ 1&0\\ 0&1\\ 
\end{bmatrix}$&$\binom{m}{2}+\binom{m}{1}+\binom{m}{0}+\binom{m}{m}$&\cite{ABS}\\
\hline
$F_{1,2,0,1}=\begin{bmatrix}1&1\\ 1&0\\ 1&0\\ 0&0\\ 
\end{bmatrix}$&$\binom{m}{2}+\binom{m}{1}+\binom{m}{0}+\binom{m}{m}$&\cite{ABS}\\
\hline
$F_{1,1,1,1}=\begin{bmatrix}1&1\\ 1&0\\ 0&1\\ 0&0\\ 
\end{bmatrix}$&$4m-4$&\cite{ABS}\\
\hline
$F_{0,4,0,0}=\begin{bmatrix}1&0\\ 1&0\\ 1&0\\ 1&0\\ 
\end{bmatrix}$&$\binom{m}{3}+\binom{m}{2}+\binom{m}{1}+\binom{m}{0}$&Thm~\ref{sauer} 
\\
\hline
$F_{0,3,1,0}=\begin{bmatrix}1&0\\ 1&0\\ 1&0\\ 0&1\\ 
\end{bmatrix}$&$\binom{m}{2}+\binom{m}{1}+\binom{m}{0}+\binom{m}{m}$&\cite{ABS}\\
\hline
$F_{0,2,2,0}=\begin{bmatrix}1&0\\ 1&0\\ 0&1\\ 0&1\\ 
\end{bmatrix}$&$\binom{m}{2}+2m-1$&Thm~\ref{one-way}\cite{FFP}\\\hline
\end{tabular}
\vskip 5pt

The following suggests that an exact bound for $F_{2,1,1,0}$ would be difficult to obtain.
In a similar way one expects that determining an exact bound for $F_{a,1,1,0}$ would be difficult.

\begin{thm}\label{difficult}(Thm 9.1 \cite{AKarp}) Let $m$ be a given integer and let $c$ be a positive real number. Let $A$ be an 
$m\times \left(c\binom{m}{2}+m+2\right)$ simple matrix with no $F_{2,1,1,0}$. Then for some $M>m$, there is an 
$M\times \left((c+\frac{2}{m(m-1)})\binom{M}{2}+M+2\right)$ simple matrix with no $F_{2,1,1,0}$. \qed\end{thm} 

Results of Peter Dukes \cite{Dukes} give a fairly tight estimate on the coefficient of $m^2$ in the bound for $\forb(m,F_{2,1,1,0})$. The following are in \cite{AKarp}. \trf{4rowedgen} would yield many exact bounds using \rrf{subconfig}.

\begin{thm}\label{4x4critical}
Let $F = 
\begin{bmatrix}
1&1&1&1\\
1&1&0&0\\
1&0&1&0\\
0&0&0&0\\
\end{bmatrix}.$
Then for $m \ge 3$ we have 
$\forb(m,F) = \binom{m}{2} + m + 2.\qed$
\end{thm}


\begin{thm}\label{4rowedgen}
Let $m \ge 4$. Let $F$ be one of the following three matrices. 
$$
\begin{array}{l}
\begin{bmatrix}
1&1&1&1&1&0&0&0&0&0\\
1&1&1&0&0&1&1&1&0&0\\
1&1&0&1&0&1&1&0&1&0\\
0&0&1&0&0&0&0&1&0&0\\
\end{bmatrix}
\hbox{ or }
\begin{bmatrix}
1&1&1&1&1&0&0&0&0&0\\
1&1&1&0&0&1&1&1&0&0\\
1&1&0&1&0&1&1&0&1&0\\
0&0&0&0&0&0&0&0&0&0\\
\end{bmatrix} \\[28pt]
\hbox{ or }
\left[{\!\!\begin{array}{cccccccccccc}
1&1&1&1&1&1&0&0&0&0&0&0\\
1&1&1&1&0&0&1&1&1&1&0&0\\
1&1&0&0&0&0&1&1&0&0&0&0\\
0&0&1&0&1&0&0&0&1&0&1&0\\
\end{array}\!\!}\right].\\
\end{array}
$$
Then 
$\forb(m,F) = \forb(m, 2\cdot\1_{3}\0_{1}) = \forb(m, \1_{4}\0_{1}) = \binom{m}{3}+\binom{m}{2}+m+2.\qed$
\end{thm}

Let 
$$F_{11}=\left[\begin{matrix}1&1&1\\ 1&1&1\\ 
1&0&0\\ 1&0&0\\ \end{matrix}\right].
$$
The following result (Thm 4.1 \cite{AKarp})  considers a $k$-rowed $F$ with $2^{k-4}$ pairs of repeated columns.  Note the difference and connection to \trf{sauerextend}.
For a number of cases including $k=4$, this result is generalized by the result in \cite{AnsteeMeehan}.
\begin{thm}\label{manyrepeated}\cite{AKarp} For $m\ge 5$, $\forb(m,F_{11})=\forb(m,\1_4)=\forb(m,K_4)$.
Assume $k\ge 5$  and $m\ge k+1$. Then
\begin{E}\forb(m,K_{k-4}\times F_{11})=\sum_{i=0}^{k-1}\binom{m}{i}=\forb(m,\1_k)=\forb(m,K_k).\label{4rowedex}\end{E}
\end{thm}

\proof The proof in the paper \cite{AKarp} is a little light on details for $k\ge 5$. We need the base case $\ncols{A}\le\forb(k+1,K_k)$. Let $A\in\Av(k+1,K_{k-4}\times F_{11})$. Using the standard induction we have $\ncols{A}=\ncols{[B(r)C(r)D(r)]}+\ncols{C(r)}$ where $[B(r)C(r)D(r)]$ has no $K_{k-4}\times F_{11}$ and $C(r)$ has no $K_{k-3}\times F_{11}$. Now by induction $\ncols{C(r)}\le\forb(k,K_{k-1})$ and $\ncols{[B(r)C(r)D(r)]}\le 2^{k}$. If $\ncols{[B(r)C(r)D(r)]}\le 2^{k}-1$,
then we obtain $\ncols{A}\le\forb(k+1,K_k)$ establishing the base case. If not, then $[B(r)C(r)D(r)]$ contains all possible  columns. Now this is true for every choice of $r$ and so we deduce that $A\in\Av(k+1,(\1_2\0_2)\times K_{k-4})$ from which we find $\ncols{A}\le\forb(k+1,K_k)$.
\qed




%--------------two columned configurations (and 1 column configurations)--------

\section{$F$ is a $k\times 1$ or $k\times 2$ (0,1)-matrix.}\label{l=2}

Recall the definitions of the $(a+b)\times 1$ vector $\1_a\0_b$ and allow me to extend it to $\1_a\0_b\1_c\0_d$ to refer to the $(a+b+c+d)\times 1$ columns obtained as $\1_a\0_b$ placed on top of $\1_c\0_d$. We recall the $(a+b+c+d)\times 2$ matrix 
$F_{a,b,c,d}=[\1_{a+b}\0_{c+d}|\1_a\0_b\1_c\0_d]$ from \srf{intro}. We first consider $k\times 1$ $F$.

\begin{thm}\label{onecol} Let $s,k$ be given positive integers with $s\le k$. Then
$$\forb(m,\1_s\0_{k-s})=\sum_{i=0}^{s-1}\binom{m}{i}+\sum_{i=0}^{k-s-1}\binom{m}{i}.\qed$$
\end{thm}

For the case $F$ is $k\times 2$, the asymptotic classification of $\forb(m,F)$ is  in \cite{AK}.  
By interchanging columns we see that
$\forb(m,F_{a,b,c,d})=\forb(m,F_{a,c,b,d})$, and by considering
(0,1)-complements we see that $\forb(m,F_{a,b,c,d})=
\forb(m,F_{d,c,b,a})$. Therefore we may  assume
 that $a\ge d$ and $b\ge c$.
Our result for the function $\forb(m,F_{a,b,c,d})$ is the following.

\begin{thm}\label{twocol}\cite{AK}
Suppose $a \geq d$ and $b \geq c$. Then
$\forb(m,F_{a,b,c,d})$ is $\Theta(m^{a+b-1})$ if either $b>c$ or $a,b\ge 1$.
Also $\forb(m,F_{a,0,0,d})$ is $\Theta(m^a)$ and
$\forb(m,F_{0,b,b,0})$ is $\Theta(m^{b})$. \qed
\end{thm}

We should note that we have a sharper bound for $F_{0,b,b,0}$ from
Theorem~\ref{one-way} \cite{FFP}.
We prove \trf{twocol} using the strong stability result Theorem~\ref{strong} and induction such as Lemma~\ref{tworow}.
A number of exact results for $k\times 2$ $F$ have been obtained.

\begin{thm}\label{repeatedcol}\cite{ABS}Assume $a,d,m$ are given integers with $a\ge d$ and $m\ge a+d$, then $$\forb(m,2\cdot\1_a\0_{d})=\forb(m,F_{a,0,0,d})=\forb(m,F_{a,1,0,d})
=\sum_{j=0}^{a}\binom{m}{j}+\sum_{j=m-d+1}^{m}\binom{m}{j}.\qed$$\end{thm}

\begin{thm}\label{2colbds}\cite{AKarp}
Let $m,a,b$ be given integers. For $m \ge 1$, $a \ge 2$ and $b \ge 2$,
$$\forb(m,F_{a,b,0,1})=\forb(m,F_{a,b,1,0})=\forb(m,\1_{a+b}\0_{1})$$
$$\hbox{ and }\quad
\forb(m,F_{a,b,1,1}) =\forb(m,\1_{a+b}\0_{2}).$$
Also for $a\ge 2$, 
$$\forb(m,F_{a,1,0,1})=
\forb(m,\1_{a+b}\0_{1}),$$
and for $b\ge 2$,
$$\forb(m,F_{1,b,1,0})= forb(m,\1_{1+b}\0_{1}),$$
$$\forb(m,F_{1,b,1,1})=\forb(m,\1_{1+b}\0_{2}).$$
Also for $b\ge 3$ \cite{ABS},
$$\forb(m,F_{0,b,1,0})=\forb(m,\1_{b}\0_{1}).\qed $$
\end{thm}
\begin{prob}\label{twocolprob} Assume we are given positive integers $a,b,c,d$ with $a\ge d$ and $b\ge c$.
Find some mild conditions on $a,b,c,d$ so that $\forb(m,F_{a,b,c,d})=\forb(m,\1_{a+b}\0_{c+d})$.\qed\end{prob}




%---------------5 rowed forbidden configurations---------

\section{$F$ is a simple $5\times \l$ matrix}\label{simplek=5}

For the case that $F$ is a $5\times \l$ simple matrix, we can use Conjecture~\ref{grand} to predict the results. The non-trivial calculations to achieve this are in \cite{AR}. Some of the asymptotic bounds have proofs. The numbered matrices are given after the conjecture. We will number them consecutively $F_1,F_2,\ldots$ for this section etc. and will reuse the names for different matrices than those used in  \srf{k=3} and \srf{k=4}. Theorem~\ref{simple,k-2} establishes the cubic bounds. The quadratic bounds for $F_3,F_4,\ldots F_{11}$ are an open problems except for $F_7$.
\vskip 12pt
\begin{conj}\label{classifyk=5}
Let $F$ be a $5\times \l$ simple matrix. \hfill\break
(Quadratic Cases)\ If $F$ has a configuration of $F_1$ or $F_2$ and if $F$ is a configuration in
$F_3, F_4, \ldots, F_{11}$ then $\forb(m,F)$ is $\Theta(m^2)$. \hfill\break
(Cubic Cases)\ If $F$ has a configuration of one of $F_{12}, F_{13}, \ldots, F_{24}$ and if $F$ is
a configuration in $F_{25}, F_{26}, \ldots, F_{29}$ then $\forb(m,F)$ is $\Theta(m^3)$. \hfill\break
(Quartic Cases)\ If $F$ has a configuration one of $F_{30}, F_{31}, \ldots, F_{87}$
then $\forb(m,F)$ is $\Theta(m^4)$. \hfill\break
In addition, any $5 \times \l$ simple matrix $F$ will fall into one of these three cases.
\end{conj}

 {\bf Minimal quadratics}:

$$F_1=\begin{bmatrix}1\\ 1\\ 1\\ 0\\ 0\\ \end{bmatrix}, \qquad
  F_2=\begin{bmatrix}0\\ 0\\ 0\\ 1\\ 1\\ \end{bmatrix}. $$
\vskip 10pt
{\bf Maximal quadratics} (by \corf{grand}):

$$ F_3 = \begin{bmatrix} 1& 1& 0& 1& 1& 1 \\
                         1& 0& 1& 1& 1& 1 \\
                         0& 1& 1& 1& 0& 0 \\
                         0& 0& 0& 0& 1& 0 \\
                         0& 0& 0& 0& 0& 1 \\
                         \end{bmatrix},
\quad
F_4 = \begin{bmatrix}   1&  1&  0&  1&  1&  1  \\
                        1&  0&  1&  1&  1&  0  \\
                        0&  1&  1&  1&  0&  1  \\
                        0&  0&  0&  0&  1&  0  \\
                        0&  0&  0&  0&  0&  1  \\
                        \end{bmatrix},
\quad
F_5 = \begin{bmatrix} 0&  0&  1&  0&  0&  0  \\
                        0&  1&  0&  0&  0&  1  \\
                        1&  0&  0&  0&  1&  0  \\
                        1&  1&  1&  1&  0&  1  \\
                        1&  1&  1&  1&  1&  0\\
                         \end{bmatrix}, $$

$$ F_6 = \begin{bmatrix}   1&  1&  0&  1&  1&  1  \\
                        1&  0&  1&  1&  1&  0  \\
                        0&  1&  0&  1&  0&  1  \\
                        0&  0&  1&  0&  1&  0  \\
                        0&  0&  0&  0&  0&  1  \\
                        \end{bmatrix},
\quad
F_7 = \begin{bmatrix} 1&  1&  0&  1&  1&  0  \\
                         1&  0&  1&  1&  1&  1  \\
                        0&  1&  0&  1&  0&  1  \\
                        0&  0&  1&  0&  0&  1  \\
                        0&  0&  0&  0&  1&  0  \\
                         \end{bmatrix},
\quad
F_8 = \begin{bmatrix}  1&  1&  0&  1&  1&  0  \\
                        1&  0&  1&  1&  1&  1  \\
                        0&  1&  0&  1&  0&  0  \\
                        0&  0&  1&  0&  0&  1  \\
                        0&  0&  0&  0&  1&  1  \\
                        \end{bmatrix}, $$

$$ F_9 = \begin{bmatrix} 0&  0&  1&  0&  0&  1  \\
                        0&  1&  0&  0&  0&  0  \\
                        1&  0&  1&  0&  1&  1  \\
                        1&  1&  0&  1&  1&  0  \\
                        1&  1&  1&  1&  0&  0 \\
                         \end{bmatrix},
\quad
F_{10} = \begin{bmatrix}   1&  1&  0&  1&  0&  0  \\
                        1&  0&  1&  1&  1&  1  \\
                        0&  1&  0&  1&  1&  0  \\
                        0&  0&  1&  0&  1&  1  \\
                        0&  0&  0&  0&  0&  1  \\
                        \end{bmatrix},
\quad
F_{11} = \begin{bmatrix} 1&  1&  0&  1&  1&  0 \\
                        1&  0&  1&  1&  0&  1  \\
                        0&  1&  0&  0&  1&  0  \\
                        0&  0&  1&  0&  0&  1  \\
                        0&  0&  0&  1&  1&  1  \\
                         \end{bmatrix}.
$$
\vskip 10pt
{\bf Minimal Cubics} (cubic constructions exist but minimal by \corf{grand}):
$$ F_{12} = \begin{bmatrix} 1\\1\\1\\1\\0\\ \end{bmatrix} \qquad
F_{13} = \begin{bmatrix} 0\\0\\0\\0\\1\\ \end{bmatrix} \qquad
F_{14}=\begin{bmatrix} 1&1&0\\1&0&1\\0&1&1\\0&0&1\\1&1&0\\
\end{bmatrix} \qquad
F_{15}=\begin{bmatrix} 0&0&1\\0&1&0\\1&0&0\\1&1&0\\0&0&1\\
\end{bmatrix} $$
$$ F_{16}=\begin{bmatrix} 1&1&0\\1&0&1\\0&1&1\\1&1&1\\0&0&0\\
\end{bmatrix} \qquad
F_{17} = \begin{bmatrix} 0&0&1\\0&1&0\\1&0&0\\0&0&0\\1&1&1\\
\end{bmatrix} \qquad
F_{18} = \begin{bmatrix} 1&1&1&1\\1&1&0&0\\0&0&1&1\\1&0&1&0\\0&1&0&1\\
\end{bmatrix} $$
$$F_{19} = \begin{bmatrix}0&0&0&0\\0&0&1&1\\1&1&0&0\\0&1&0&1\\1&0&1&0\\
\end{bmatrix} \qquad
F_{20}=\begin{bmatrix} 0&1&1&1\\1&1&0&0\\0&0&1&1\\1&0&1&0\\0&1&0&1\\
\end{bmatrix} \qquad
F_{21}=\begin{bmatrix} 1&0&0&0\\0&0&1&1\\1&1&0&0\\0&1&0&1\\1&0&1&0\\
\end{bmatrix} $$
$$ F_{22}=\begin{bmatrix} 0&1&1\\1&1&0\\0&1&1\\1&0&1\\0&0&0\\
\end{bmatrix} \qquad
F_{23} = \begin{bmatrix} 1&0&0\\0&0&1\\1&0&0\\0&1&0\\1&1&1\\
\end{bmatrix} \qquad
F_{24} = \begin{bmatrix} 0&0&1&1\\ 1&1&0&0\\1&0&1&0\\0&1&0&1\\0&0&1&1\\
\end{bmatrix} $$

\vskip 10pt
{\bf Maximal Cubics by Theorem~\ref{simple,k-2}}:
$$ F_{25} = \left[\begin{matrix}
1&0&1&1&1&1&0&\\
0&1&1&0&0&0&1&\\
0&0&0&1&0&0&1&\\
0&0&0&0&1&0&0&\\
0&0&0&0&0&1&0&\\
\end{matrix}
\begin{matrix}
0&1&1&1&1&1&0&1&1\\
1&1&1&1&0&0&1&1&1\\
0&1&0&0&1&1&1&1&1\\
1&0&1&0&1&0&1&1&0\\
0&0&0&1&0&1&0&0&1\\
\end{matrix} \right] $$

$$ F_{26} = \left[\begin{matrix}
1&0&1&1&1&1&0&\\
0&1&1&0&0&0&1&\\
0&0&0&1&0&0&1&\\
0&0&0&0&1&0&0&\\
0&0&0&0&0&1&0&\\
\end{matrix}
\begin{matrix}
0&1&1&1&1&1&1&1\\
1&1&1&1&0&0&1&1\\
0&1&0&0&1&0&1&0\\
1&0&1&0&0&1&0&1\\
0&0&0&1&1&1&1&1\\
\end{matrix} \right] $$

$$ F_{27} = \left[\begin{matrix}
0&1&0&0&0&0&1&\\
1&0&0&1&1&1&0&\\
1&1&1&0&1&1&0&\\
1&1&1&1&0&1&1&\\
1&1&1&1&1&0&1&\\
\end{matrix}
\begin{matrix}
1&0&0&0&0&0&0&0\\
0&0&0&0&1&1&0&0\\
1&0&1&1&0&1&0&1\\
0&1&0&1&1&0&1&0\\
1&1&1&0&0&0&0&0\\
\end{matrix} \right] $$

$$ F_{28} = \left[\begin{matrix}
1&0&1&1&1&1&0&\\
0&1&1&0&0&0&1&\\
0&0&0&1&0&0&1&\\
0&0&0&0&1&0&0&\\
0&0&0&0&0&1&0&\\
\end{matrix}
\begin{matrix}
0&1&1&1&1&1&0&1&1\\
1&1&1&0&0&0&1&1&0\\
0&1&0&1&1&0&1&1&1\\
1&0&1&1&0&1&1&1&1\\
0&0&0&0&1&1&0&0&1\\
\end{matrix} \right] $$

$$ F_{29} = \left[\begin{matrix}
1&0&1&1&0&0&\\
0&1&0&0&1&1&\\
0&0&1&0&1&0&\\
0&0&0&1&0&1&\\
0&0&0&0&0&0&\\
\end{matrix}
\begin{matrix}
1&1&0&0&1&0\\
0&0&1&1&0&1\\
1&1&1&1&1&1\\
1&0&1&0&1&1\\
0&1&0&1&1&1\\
\end{matrix} \right] $$

\vskip 10pt
{\bf Minimal quartics by Theorem~\ref{simple,k-2}}:
$$ F_{30} = \begin{bmatrix} 1\\1\\1\\1\\1\\ \end{bmatrix} \quad
F_{31} = \begin{bmatrix} 0\\0\\0\\0\\0\\ \end{bmatrix} $$
$$ F_{32} = \begin{bmatrix} 1&1&0\\1&0&1\\0&1&1\\1&1&1\\1&1&1\\
\end{bmatrix} \quad
F_{33} = \begin{bmatrix}0&0&1\\0&1&0\\1&0&0\\0&0&0\\0&0&0\\
\end{bmatrix} \quad
F_{34}=\begin{bmatrix}
0&1&1\\
0&1&1\\
1&1&0\\
1&0&1\\
1&1&1\\
\end{bmatrix} $$
$$ F_{35}=\begin{bmatrix}
1&0&0\\
1&0&0\\
0&0&1\\
0&1&0\\
0&0&0\\
\end{bmatrix} \quad
F_{36} = \begin{bmatrix}
1&0&0&1\\
0&1&0&1\\
0&0&1&1\\
1&1&1&0\\
1&1&1&1\\
\end{bmatrix} \quad
F_{37} = \begin{bmatrix}
0&1&1&0\\
1&0&1&0\\
1&1&0&0\\
0&0&0&1\\
0&0&0&0\\
\end{bmatrix} $$
$$F_{38}=\begin{bmatrix}
1&0&1\\
0&1&1\\
0&1&1\\
1&0&1\\
1&1&0\\
\end{bmatrix} \quad
F_{39}=\begin{bmatrix}
0&1&0\\
1&0&0\\
1&0&0\\
0&1&0\\
0&0&1\\
\end{bmatrix} \quad
F_{40} = \begin{bmatrix}
1&1&1&0&0&0\\
0&0&0&1&1&1\\
1&1&0&1&1&0\\
1&0&1&1&0&1\\
0&1&1&0&1&1\\
\end{bmatrix} $$
$$F_{41} = \begin{bmatrix}
0&0&0&1&1&1\\
1&1&1&0&0&0\\
0&0&1&0&0&1\\
0&1&0&0&1&0\\
1&0&0&1&0&0\\
\end{bmatrix} \quad
F_{42}=\begin{bmatrix}
1&1&1&0&0&0\\
1&0&0&1&1&0\\
0&1&0&1&0&1\\
0&0&1&0&1&1\\
1&1&1&1&1&1\\
\end{bmatrix} \quad
F_{43}=\begin{bmatrix}
0&0&0&1&1&1\\
0&1&1&0&0&1\\
1&0&1&0&1&0\\
1&1&0&1&0&0\\
0&0&0&0&0&0\\
\end{bmatrix} $$

$$ F_{44} = \begin{bmatrix}
1&1&1&0\\
1&0&0&1\\
0&1&0&1\\
0&0&1&1\\
1&1&1&0\\
\end{bmatrix} \quad
F_{45} = \begin{bmatrix}
0&0&0&1\\
0&1&1&0\\
1&0&1&0\\
1&1&0&0\\
0&0&0&1\\
\end{bmatrix} \quad
F_{46}=\begin{bmatrix}
1&1&1&0&0\\
1&0&0&1&1\\
0&1&0&1&1\\
0&1&1&1&0\\
1&0&1&0&1\\
\end{bmatrix} $$
$$F_{47}=\begin{bmatrix}
0&0&0&1&1\\
0&1&1&0&0\\
1&0&1&0&0\\
1&0&0&0&1\\
0&1&0&1&0\\
\end{bmatrix} \quad
F_{48} = \begin{bmatrix}
0&1&1\\
0&1&1\\
0&1&1\\
1&1&0\\
1&0&1\\
\end{bmatrix} \quad
F_{49} = \begin{bmatrix}
1&0&0\\
1&0&0\\
1&0&0\\
0&0&1\\
0&1&0\\
\end{bmatrix} $$
$$F_{50}=\begin{bmatrix}
0&1&0&1\\
0&0&1&1\\
0&1&1&1\\
1&0&0&1\\
1&1&1&0\\
\end{bmatrix} \quad
F_{51}=\begin{bmatrix}
1&0&1&0\\
1&1&0&0\\
1&0&0&0\\
0&1&1&0\\
0&0&0&1\\
\end{bmatrix} \quad
F_{52} = \begin{bmatrix}
0&1&1&0&0\\
0&1&0&1&1\\
0&0&1&1&1\\
1&0&1&1&0\\
1&1&0&0&1\\
\end{bmatrix} $$
$$F_{53} = \begin{bmatrix}
1&0&0&1&1\\
1&0&1&0&0\\
1&1&0&0&0\\
0&1&0&0&1\\
0&0&1&1&0\\
\end{bmatrix} \quad
F_{54}=\begin{bmatrix}
0&1&1&1&0&0\\
0&1&0&0&1&1\\
0&1&1&1&1&1\\
1&0&1&0&1&0\\
1&0&0&1&0&1\\
\end{bmatrix} \quad
F_{55}=\begin{bmatrix}
1&0&0&0&1&1\\
1&0&1&1&0&0\\
1&0&0&0&0&0\\
0&1&0&1&0&1\\
0&1&1&0&1&0\\
\end{bmatrix} $$

$$ F_{56} = \begin{bmatrix}
0&1&1&1&0\\
0&1&1&0&1\\
0&1&0&1&1\\
1&0&0&0&1\\
1&0&1&1&0\\
\end{bmatrix} \quad
F_{57} = \begin{bmatrix}
1&0&0&0&1\\
1&0&0&1&0\\
1&0&1&0&0\\
0&1&1&1&0\\
0&1&0&0&1\\
\end{bmatrix} \quad
F_{58}=\begin{bmatrix}
0&0&1&1\\
0&0&1&1\\
1&0&0&1\\
0&1&0&1\\
1&1&1&0\\
\end{bmatrix} $$
$$F_{59}=\begin{bmatrix}
1&1&0&0\\
1&1&0&0\\
0&1&1&0\\
1&0&1&0\\
0&0&0&1\\
\end{bmatrix} \quad
F_{60} = \begin{bmatrix}
0&0&1&1&0\\
0&0&1&0&1\\
1&0&0&1&1\\
0&1&0&1&1\\
1&1&1&0&0\\
\end{bmatrix} \quad
F_{61} = \begin{bmatrix}
1&1&0&0&1\\
1&1&0&1&0\\
0&1&1&0&0\\
1&0&1&0&0\\
0&0&0&1&1\\
\end{bmatrix} $$
$$F_{62}=\begin{bmatrix}
0&0&1&1&0&1\\
0&0&1&1&1&0\\
1&0&1&0&1&1\\
0&1&0&1&1&1\\
1&1&0&0&0&1\\
\end{bmatrix} \quad
F_{63}=\begin{bmatrix}
1&1&0&0&1&0\\
1&1&0&0&0&1\\
0&1&0&1&0&0\\
1&0&1&0&0&0\\
0&0&1&1&1&0\\
\end{bmatrix} \quad
F_{64} = \begin{bmatrix}
0&0&1&1&1&0\\
0&0&1&1&0&1\\
1&0&1&0&0&1\\
0&1&0&1&1&0\\
1&1&0&0&1&1\\
\end{bmatrix} $$
$$F_{65} = \begin{bmatrix}
1&1&0&0&0&1\\
1&1&0&0&1&0\\
0&1&0&1&1&0\\
1&0&1&0&0&1\\
0&0&1&1&0&0\\
\end{bmatrix} \quad
F_{66}=\begin{bmatrix}
0&0&1&1&1&0\\
0&0&1&1&0&1\\
1&0&1&0&1&1\\
0&1&0&1&1&1\\
1&1&0&0&0&0\\
\end{bmatrix} \quad
F_{67}=\begin{bmatrix}
1&1&0&0&0&1\\
1&1&0&0&1&0\\
0&1&0&1&0&0\\
1&0&1&0&0&0\\
0&0&1&1&1&1\\
\end{bmatrix} $$
$$F_{68} = \begin{bmatrix}
0&0&1&1&1&0\\
0&0&1&1&1&1\\
1&0&1&0&0&1\\
0&1&0&1&0&1\\
1&1&0&0&1&0\\
\end{bmatrix} \quad
F_{69} = \begin{bmatrix}
1&1&0&0&0&1\\
1&1&0&0&0&0\\
0&1&0&1&1&0\\
1&0&1&0&1&0\\
0&0&1&1&0&1\\
\end{bmatrix} \quad
F_{70}=\begin{bmatrix}
0&0&0&1&1&1\\
0&0&0&1&1&1\\
1&1&0&1&0&0\\
1&0&1&0&1&0\\
0&1&1&0&0&1\\
\end{bmatrix} $$
$$F_{71}=\begin{bmatrix}
0&0&0&1&1&1\\
1&0&0&1&0&0\\
0&1&0&0&1&1\\
0&0&1&1&1&0\\
1&1&1&0&0&1\\
\end{bmatrix} \quad
F_{72} = \begin{bmatrix}
1&1&1&0&0&0\\
0&1&1&0&1&1\\
1&0&1&1&0&0\\
1&1&0&0&0&1\\
0&0&0&1&1&0\\
\end{bmatrix} \quad
F_{73} = \begin{bmatrix}
0&0&0&1&1&1\\
1&0&0&1&1&0\\
0&1&0&1&0&1\\
0&0&1&0&1&1\\
1&1&1&0&0&0\\
\end{bmatrix} $$
$$F_{74}=\begin{bmatrix}
0&0&1&1\\
1&0&1&0\\
0&1&0&1\\
0&1&1&0\\
1&0&0&1\\
\end{bmatrix} \quad
F_{75}=\begin{bmatrix}
0&0&0&1&1&1\\
1&0&0&1&0&1\\
0&1&0&1&1&0\\
0&1&1&0&1&1\\
1&0&1&0&0&1\\
\end{bmatrix} \quad
F_{76} = \begin{bmatrix}
1&1&1&0&0&0\\
0&1&1&0&1&0\\
1&0&1&0&0&1\\
1&0&0&1&0&0\\
0&1&0&1&1&0\\
\end{bmatrix} $$
$$F_{77} = \begin{bmatrix}
0&0&0&1&1&1\\
1&0&0&1&1&0\\
0&1&0&1&0&1\\
0&1&1&0&0&1\\
1&0&1&0&1&0\\
\end{bmatrix} \quad
F_{78}=\begin{bmatrix}
1&0&0&0&1\\
0&1&0&0&1\\
0&0&1&0&1\\
0&0&0&1&1\\
1&1&1&1&0\\
\end{bmatrix} \quad
F_{79}=\begin{bmatrix}
0&1&1&1&0\\
1&0&1&1&0\\
1&1&0&1&0\\
1&1&1&0&0\\
0&0&0&0&1\\
\end{bmatrix} $$
$$F_{80} = \begin{bmatrix}
1&0&0&1&1\\
0&1&0&1&1\\
0&0&1&0&1\\
0&0&1&1&0\\
1&1&0&0&1\\
\end{bmatrix} \quad
F_{81} = \begin{bmatrix}
0&1&1&0&0\\
1&0&1&0&0\\
1&1&0&1&0\\
1&1&0&0&1\\
0&0&1&1&0\\
\end{bmatrix} \quad
F_{82}=\begin{bmatrix}
1&0&0&0&1&1\\
0&1&0&0&1&1\\
0&0&1&1&1&1\\
0&1&1&0&1&0\\
1&0&0&1&0&1\\
\end{bmatrix} $$
$$F_{83}=\begin{bmatrix}
0&1&1&1&0&0\\
1&0&1&1&0&0\\
1&1&0&0&0&0\\
1&0&0&1&0&1\\
0&1&1&0&1&0\\
\end{bmatrix} \quad
F_{84} = \begin{bmatrix}
1&0&0&0&1&1\\
0&1&0&0&1&1\\
0&0&1&1&0&1\\
0&1&1&0&0&1\\
1&0&0&1&1&0\\
\end{bmatrix} \quad
F_{85} = \begin{bmatrix}
0&1&1&1&0&0\\
1&0&1&1&0&0\\
1&1&0&0&1&0\\
1&0&0&1&1&0\\
0&1&1&0&0&1\\
\end{bmatrix} $$
$$F_{86}=\begin{bmatrix}
1&0&0&0&0&1\\
0&1&1&0&0&1\\
0&0&0&1&1&1\\
0&1&0&1&0&1\\
1&0&1&0&1&0\\
\end{bmatrix} \quad
F_{87}=\begin{bmatrix}
0&1&1&1&1&0\\
1&0&0&1&1&0\\
1&1&1&0&0&0\\
1&0&1&0&1&0\\
0&1&0&1&0&1\\
\end{bmatrix} \qed$$
We would need to prove quadratic bounds for the 9 matrices $F_3,F_4,\ldots ,F_{11}$ in order to complete the classification of the 5-rowed simple configurations. We have one result (it required a detailed inductive proof).

\begin{thm}\label{F7thm}\cite{F7} We have that $\forb(m,F_7)$ is $\Theta(m^2)$. \qed\end{thm}

Interestingly using \trf{F7thm} and a straightforward induction, we can establish the 6-rowed $F$ yielding quadratic bounds.

$$\hbox{Let }G_{6\times 3}=
\left[\begin{array}{ccc}
1&1&1\\
1&1&0\\
1&0&1\\
0&1&0\\
0&0&1\\
0&0&0\\
\end{array}\right].$$
\begin{thm} \label{G6x3}\cite{F7} We have that $\forb(m,G_{6\times 3})$ is $\Theta(m^2)$. Moreover for any column $\alpha$, then $\forb(m, [G_{6\times 3}|\alpha])$ is $\Omega(m^3)$. In fact if $F$ is not a configuration in $G_{6\times 3}$, then $\forb(m,F)$ is $\Omega(m^3)$. \qed\end{thm}

\section{Boundary between $\Omega(m^{k-1})$ and $O(m^{k-2})$}\label{generalboundary}

Conjecture~\ref{grand} predicts which $k$-rowed $F$ will have $\forb(m,F)$ being $\Theta(m^{k-2})$. For the case of simple matrices we may use Theorem~\ref{simple,k-2} directly and obtain the following 6 cases:

$$F_{1,k}=\begin{array}{c}
\left[\begin{array}{cccc}1&1&1&0\\ 1&0&0&1\\ 0&1&0&0\\ \end{array}\right]\\
\times \\
K_{k-3}\\ \end{array}
,\quad
F_{2,k}=\begin{array}{c}
 \left[\begin{array}{cc}1&0\\ 0&1\\ \end{array}\right]\\
\times \\
\left[\begin{array}{ccc}0&1&1\\ 0&0&1\\ \end{array}\right]\\
\times\\
K_{k-4}\\ \end{array},$$


$$F_{3,k}=\begin{array}{c}
\left[\begin{array}{cccccccc} 
0&0&0&0&1&0&0&1\\ 
0&0&0&1&0&1&1&0\\
0&1&1&0&0&1&1&1\\
1&0&1&1&1&0&1&1\\
\end{array}\right]\\
\times\\ 
K_{k-4}\\ \end{array},
\quad
F_{4,k}=\begin{array}{c}
\left[\begin{array}{ccccc} 
0&0&1&1&0\\        
0&0&0&0&1\\
0&1&0&1&1\\
\end{array}\right]\\
\times\\
\left[\begin{array}{ccc}
1&0&1\\  
0&1&1\\  
 \end{array}\right]\\
\times\\
K_{k-5}\\ \end{array} ,$$


$$F_{5,k}=\begin{array}{c}
\left[\begin{array}{ccccccccccccccc} 
1&1&1&0&0&0&0&0&0&1&1&1&1&1&1\\        
0&0&0&1&1&1&1&1&1&1&1&1&1&1&1\\
0&0&0&0&0&0&1&1&1&0&0&0&1&1&1\\
0&1&0&0&1&0&0&1&0&0&1&0&0&1&0\\
0&0&1&0&0&1&0&0&1&0&0&1&0&0&1\\
\end{array}\right]\\
\times\\
K_{k-5}\\ \end{array} 
,\quad
F_{6,k}= \begin{array}{c}
\left[\begin{array}{ccc}0&1&0\\ 0&0&1\\ \end{array}\right]\\
\times \\
\left[\begin{array}{ccc}1&0&1\\ 0&1&1\\ \end{array}\right]\\
\times \\ 
\left[\begin{array}{ccc}0&1&1\\ 0&0&1\\ \end{array}\right]\\
\times\\
K_{k-6}\\ \end{array}.$$

\begin{thm}\label{simple,k-2,matrices}Let $F$ be a simple $k$-rowed $F$ for which $\forb(m,F)$ is $O(m^{k-2})$. Then $F$ is a configuration in $\left[\begin{array}{c}1\\ 0\\ \end{array}\right]$,
$F_{1,k}$, $F_{2,k}$, $F_{3,k}$, $F_{4,k}$, $F_{5,k}$, or $F_{6,k}$. \qed\end{thm}

When we apply Conjecture~\ref{grand} to determine non-simple $k$-rowed matrices with $\forb(m,F)$ being $\Theta(m^{k-2})$ our first guess would be to allow any column with column sum $\in\{2,3,\ldots ,k-2\}$ to be repeated $t$ times. This works in most cases. For a $k$-rowed simple matrix $A$, Define $\rep(A,t)$ as the matrix obtained from $A$ by repeating columns of column sum $\in\{2,3,\ldots ,k-2\}$ $t$ times while leaving the remaining columns of sum $0,1,k-1,k$ unchanged. Applying \corf{grand}, we obtain the following:

\begin{conj}\label{k-2,matrices} Let $t\ge 1$ be given. Then 
$\forb(m,\rep(F_{2,k},t))$, 
$\forb(m,\rep(F_{3,k},t))$, 
$\forb(m,\rep(F_{4,k},t))$, 
$\forb(m,\rep(F_{5,k},t))$, 
$\forb(m,\rep(F_{6,k},t))$ are all $\Theta(m^{k-2})$.
Also $\forb(m,\rep(F_{1,k},t))$ is $\Theta(m^{k-1})$. 
\qed 
\end{conj}

\section{What is missing if a configuration $F$ is avoided?}\label{missing}

Let $F$ be a given $k\times \l$ (0,1)-matrix. Let $S$ be a subset of $[m]$, the rows of $A$. 
 We are interested in what conditions on $A{|_S}$ must be satisfied so that $A$ has no configuration $F$.  The problem of forbidden configurations does not reduce to these conditions since the conditions do not refer to the simplicity of $A$ but these conditions have been used successfully.  

We say an $|S|\times 1$ column $\alpha$ on a set of rows $S$ is in `short supply' in $A$ if $A{|_S}$ has at most some constant number of columns equal to $\alpha$.
In this circumstance row order is relevant. We are not considering  columns of $A{|_S}$ up to row permutations. 
It is convenient to list what is missing on $k$-sets but sometimes one also lists what is missing on smaller or larger sets of rows.

A careful consideration is required to see what is missing from  $A$
when a configuration $F$ is not a  configuration in $A$.  One can use the computer program of Miguel Raggi at \hfill\break
\hfil http://www.math.ubc.ca/$\sim$anstee/FConfThesisVersion.tar.gz \hfil\break
(to solve small cases (say 4 or 5 rows). The following is an example from cases with $k=3$.  Let $\{i,j,k\}$ be a triple of
rows of a matrix $A=(a_{rs})$. We say  that we have 
\begin{equation}\hbox{ no }
\begin{matrix}i\\ j\\ k\\\end{matrix}
\begin{bmatrix}d\\ e\\ f\\ \end{bmatrix}\label{coldef}\end{equation}
if in every column $q$ of $A$ we do not have $a_{iq}=d, a_{jq}=e$ and
$a_{kq}=f$ all occurring. As well, we say that there are
\begin{equation}\hbox{ at most }t-1\hbox{ of }
\begin{matrix}i\\ j\\ k\\\end{matrix}
\begin{bmatrix}d\\ e\\ f\\ \end{bmatrix}\label{coldeft-1}\end{equation}
if there are at most $t-1$ columns $q$ of $A$ in which $a_{iq}=d,
a_{jq}=e$ and $a_{kq}=f$ all occur.


Let $S_p$ denote the symmetric group on $p$ symbols.


\begin{prop}(Proposition 2.1\cite{AS05})\label{F6} Let $A$ be a (0,1)-matrix with no
configuration $F_6(t)$ of Section~\ref{k=3}. Let $a,b,c$ be a triple of rows of $A$. Then
we either have a permutation $\pi_1\in S_3$ with $\pi_1(a)=i$,
$\pi_1(b)=j$, $\pi_1(c)=k$ (note that $\{a,b,c\}$ and $\{i,j,k\}$ are
the same as sets) with
\begin{equation}\label{321} \hbox{ no }
\begin{matrix}i\\ j\\ k\\\end{matrix}
\begin{bmatrix}0\\ 0\\ 0\\ \end{bmatrix},\end{equation}
or if we do not have (\ref{321}), then  we have  a permutation
$\pi_2\in S_3$ with $\pi_2(a)=i$, $\pi_2(b)=j$, $\pi_2(c)=k$ with
\begin{equation}\label{322} \hbox{ at most }t-1\hbox{ of }
\begin{matrix}i\\ j\\ k\\\end{matrix}
\begin{bmatrix}0\\ 0\\ 1\\ \end{bmatrix},\end{equation}
or if we do not have (\ref{321}),(\ref{322}), then we have  a
permutation $\pi_3\in S_3$ with $\pi_3(a)=i$, $\pi_3(b)=j$,
$\pi_3(c)=k$ with
\begin{equation}\label{323} \hbox{ at most }t-1\hbox{ of  }
\begin{matrix}i\\ j\\ k\\\end{matrix}
\begin{bmatrix}1\\ 1\\ 0\\ \end{bmatrix},\quad
\hbox{ and at most }t-1\hbox{ of  }
\begin{matrix}i\\ j\\ k\\\end{matrix}
\begin{bmatrix}1\\ 0\\ 1\\ \end{bmatrix}.\end{equation}
\end{prop}

\proof (sample) If one of  (\ref{321}),(\ref{322}),(\ref{323}) is true we have
no $F_6(t)$. Give (\ref{321}) is false, we either have $t\cdot K_3^1$
in the triple of rows or not. If not, then
(\ref{322}) holds for some ordering. If we do have $t\cdot K_3^1$ in
the triple of rows,
then $t$ copies of two columns of two 1's (in the triple of rows)
will yield $F_6(t)$ and so at most one column of two 1's appears $t$
or more times. Thus (\ref{323}) holds. \qed
\vskip 5pt

\begin{prop}(Proposition 2.2\cite{AS05}) \label{F5} Let $A$ be a (0,1)-
matrix with no configuration $F_5(t)$ of Section ~\ref{k=3}. Let $a,b,c$ be a triple of
rows of $A$. Then we either have a permutation $\pi_1\in S_3$ with
$\pi_1(a)=i$, $\pi_1(b)=j$, $\pi_1(c)=k$  with
\begin{equation}\label{221} \hbox{ no }
\begin{matrix}i\\ j\\ k\\\end{matrix}
\begin{bmatrix}0\\ 0\\ 0\\ \end{bmatrix}
\hbox{ or no }
\begin{matrix}i\\ j\\ k\\\end{matrix}
\begin{bmatrix}0\\ 0\\ 1\\ \end{bmatrix}
\hbox{ or no }
\begin{matrix}i\\ j\\ k\\\end{matrix}
\begin{bmatrix}1\\ 1\\ 0\\ \end{bmatrix}
\hbox{ or no }
\begin{matrix}i\\ j\\ k\\\end{matrix}
\begin{bmatrix}1\\ 1\\ 1\\ \end{bmatrix}\end{equation}
or if we do not have (\ref{221}), then  we have  a permutation
$\pi_2\in S_3$ with $\pi_2(a)=i$, $\pi_2(b)=j$, $\pi_2(c)=k$ with
\begin{equation}\label{222} \hbox{ at most }t-1\hbox{ of  }
\begin{matrix}i\\ j\\ k\\\end{matrix}
\begin{bmatrix}0\\ 0\\ 1\\ \end{bmatrix},\quad
\hbox{ and at most }t-1\hbox{ of  }
\begin{matrix}i\\ j\\ k\\\end{matrix}
\begin{bmatrix}0\\ 1\\ 0\\ \end{bmatrix},\end{equation}
or if we do not have (\ref{221}),(\ref{222}), then we have  a
permutation $\pi_3\in S_3$ with $\pi_3(a)=i$, $\pi_3(b)=j$,
$\pi_3(c)=k$ with
\begin{equation}\label{223}\hbox{ at most }t-1\hbox{ of  }
\begin{matrix}i\\ j\\ k\\\end{matrix}
\begin{bmatrix}1\\ 1\\ 0\\ \end{bmatrix},\quad
\hbox{ and at most }t-1\hbox{ of  }
\begin{matrix}i\\ j\\ k\\\end{matrix}
\begin{bmatrix}1\\ 0\\ 1\\ \end{bmatrix},\end{equation}
or if we do not have (\ref{221}),(\ref{222}),(\ref{223}), then we
have  a permutation $\pi_4\in S_3$ with $\pi_4(a)=i$, $\pi_4(b)=j$,
$\pi_4(c)=k$ with
\begin{equation}\label{224} \hbox{ at most }t-1\hbox{ of  }
\begin{matrix}i\\ j\\ k\\\end{matrix}
\begin{bmatrix}0\\ 0\\ 1\\ \end{bmatrix},\quad
\hbox{ and at most }t-1\hbox{ of  }
\begin{matrix}i\\ j\\ k\\\end{matrix}
\begin{bmatrix}0\\ 1\\ 1\\ \end{bmatrix}.\qed\end{equation}\end{prop}


We can readily establish such results for various $F$ but it does take some careful thought.  We give below the specific result for $F(k)=[K_k^0\,|\,t\cdot D_{12}]$ when $k=4$  \cite{AFl10}. It was crucial in the proof of Theorem~\ref{boundary} that this notion for general $k$ is considered. It used the fact that if you consider what is missing on a given set of $k$ rows in a matrix $A$ avoiding  $F(k)$, then for any pair of rows rows $p,q$  chosen from the $k$ rows,  there is a column in {\it short supply} in the submatrix of $A$ formed by the $k$ rows (either absent of occurring some bounded number of times) which is either 0 on row $p$ or 0 on row $q$. 
\begin{prop}\label{F64rows}
Let A be a (0,1)-matrix with no configuration $4$-rowed configuration $F_6(t)
=[K_4^0\,|\,t\cdot D_{12}]$ from Theorem~\ref{boundary}. 
Let $a,b,c,d$ be four of rows of $A$. Then
we either have a permutation $\pi_1\in S_4$ with $\pi_1(a)=i$,
$\pi_1(b)=j$, $\pi_1(c)=k$, $\pi_1(d)=l$ (note that $\{a,b,c,d\}$ and $\{i,j,k,l\}$ are
the same as sets) with
\begin{equation}\label{41} \hbox{ no }
\begin{matrix}i\\ j\\ k\\ l\\ \end{matrix}
\begin{bmatrix}0\\ 0\\ 0\\ 0\\ \end{bmatrix},\end{equation}
or if we do not have (\ref{41}), then  we have  a permutation
$\pi_2\in S_4$ with $\pi_2(a)=i$,
$\pi_2(b)=j$, $\pi_2(c)=k$, $\pi_2(d)=l$  with
\begin{equation}\label{42} \hbox{ at most }t-1\hbox{ of }
\begin{matrix}i\\ j\\ k\\ l\\\end{matrix}
\begin{bmatrix}1\\ 0\\ 0\\ 0\\ \end{bmatrix},\end{equation}
or if we do not have (\ref{41}),(\ref{42}), then we have  a
permutation $\pi_3\in S_4$ with $\pi_3(a)=i$,
$\pi_3(b)=j$, $\pi_3(c)=k$, $\pi_3(d)=l$ with
\begin{equation}\label{43} \hbox{ at most }t-1\hbox{ of  }
\begin{matrix}i\\ j\\ k\\ l\\ \end{matrix}
\begin{bmatrix}1\\ 1\\ 0\\ 0\\ \end{bmatrix},\quad
\hbox{ and at most }t-1\hbox{ of  }
\begin{matrix}i\\ j\\ k\\ l\\ \end{matrix}
\begin{bmatrix}1\\ 0\\ 1\\ 0\\ \end{bmatrix}.\end{equation}
or if we do not have (\ref{41}),(\ref{42}),(\ref{43}), then we have  a
permutation $\pi_4\in S_4$ with $\pi_4(a)=i$,
$\pi_4(b)=j$, $\pi_4(c)=k$, $\pi_4(d)=l$ with
\begin{equation}\label{44} \hbox{ at most }t-1\hbox{ of  }
\begin{matrix}i\\ j\\ k\\ l\\ \end{matrix}
\begin{bmatrix}1\\ 1\\ 0\\ 0\\ \end{bmatrix},\quad
\hbox{ and at most }t-1\hbox{ of  }
\begin{matrix}i\\ j\\ k\\ l\\ \end{matrix}
\begin{bmatrix}0\\ 0\\ 1\\ 1\\ \end{bmatrix}.\end{equation}
or if we do not have (\ref{41}),(\ref{42}),(\ref{43}),(\ref{44}), then we have  a
permutation $\pi_5\in S_4$ with $\pi_5(a)=i$,
$\pi_5(b)=j$, $\pi_5(c)=k$, $\pi_5(d)=l$ with
\begin{equation}\label{45} \hbox{ at most }t-1\hbox{ of  }
\begin{matrix}i\\ j\\ k\\ l\\ \end{matrix}
\begin{bmatrix}1\\ 1\\ 1\\ 0\\ \end{bmatrix},\quad
\hbox{ and at most }t-1\hbox{ of  }
\begin{matrix}i\\ j\\ k\\ l\\ \end{matrix}
\begin{bmatrix}1\\ 1\\ 0\\ 1\\ \end{bmatrix}
\hbox{ at most }t-1\hbox{ of  }
\begin{matrix}i\\ j\\ k\\ l\\ \end{matrix}
\begin{bmatrix}0\\ 1\\ 1\\ 1\\ \end{bmatrix}.\end{equation}
or if we do not have (\ref{41}),(\ref{42}),(\ref{43}),(\ref{44}),(\ref{45}), then we have  a
permutation $\pi_6\in S_4$ with $\pi_6(a)=i$,
$\pi_6(b)=j$, $\pi_6(c)=k$, $\pi_6(d)=l$ with
\begin{equation}\label{46} \hbox{ at most }t-1\hbox{ of  }
\begin{matrix}i\\ j\\ k\\ l\\ \end{matrix}
\begin{bmatrix}1\\ 1\\ 0\\ 0\\ \end{bmatrix},\quad
\hbox{ and at most }t-1\hbox{ of  }
\begin{matrix}i\\ j\\ k\\ l\\ \end{matrix}
\begin{bmatrix}0\\ 1\\ 1\\ 1\\ \end{bmatrix}.\qed\end{equation}
\end{prop}



\section{Standard Induction}\label{induction}

There are easy standard inductions based on either deleting the first row or perhaps the first two rows. The most attractive application is the bound
Theorem~\ref{simple,k-2} but there are many other applications.

The {\it standard induction} \cite{AGS} proceeds as follows. Let $A$ be a simple
$m\times n$ matrix with no configuration $F$ or some such property. Then we can decompose $A$ as follows.
I have permuted the rows so row $r$ of $A$ appears at the top. When deleting row $r$ from $A$, there may be repeated columns and we have permuted the columns to obtain the following where $[B(r)C(r)D(r)]$ is simple.
\begin{E}A=\begin{array}{r}\hbox{row }r\rightarrow\\ \\ \end{array}
\left[\begin{array}{cccc}
00\cdots0& 00\cdots0& 11\cdots 1& 11\cdots 1\\ B(r)&C(r)&C(r)&D(r)
\end{array}\right]\label{standarddecomp}\end{E}
Now $[B(r)C(r)D(r)]$ is simple and has no configuration $F$.  Also \hfil. $\ncols{A}=\ncols{[B(r)C(r)D(r)]}+\ncols{C(r)}$. One can easily derive the upper bound of Theorem~\ref{sauer} this way by noting that if $K_k\not\prec A$ then $K_{k-1}\not\prec C(r)$. Then by induction  $\ncols{[B(r)C(r)D(r)]}\le\forb(m-1,K_k)$ and 
$\ncols{C(r)}\le\forb(m-1,K_{k-1})$. Thus $\forb(m,K_k)\le
\forb(m-1,K_k)+\forb(m-1,K_{k-1})$ and we obtain the desired bound.  It may work to just use row $r=1$ but in certain circumstances one should choose row $r$ so that $C(r)$ is in some way minimal.  A  version describing what $C(r)$ avoids assuming $A$ avoids $F$ is stated in \cite{AK}.  It also used for when forbidding families of configurations.

\begin{lemma}\label{onerow}\cite{AKarp} 
Let $k$ be given and
let $F$ be a $k$-rowed simple matrix. For each $s\in[k]$, decompose $F$ as
\begin{E}F=
\begin{matrix}
\hbox{row }s\rightarrow  \\
\\
\end{matrix}
\begin{bmatrix}
0\,0\cdots 0& 0\,0\cdots 0& 1\,1\cdots 1& 1\,1\cdots 1\\
B_s(F) & C_s(F) & C_s(F) & D_s(F) \\ 
\end{bmatrix},
\end{E}
where we have permuted the rows of $F$ so row $s$ is the first row and $C_s(F)$ consists  of the repeated columns after deleting that row from $F$. Then if $A$ is a simple matrix with no configuration $F$, then in the row decomposition  of $A$ of (\ref{standarddecomp}), we deduce that $C(r)$ has no configurations $F_s=[B_s(F)C_s(F)D_s(F)]$ for each $s\in[k]$. In particular if
$\forb(m,\{F_1,F_2,\ldots ,F_k\})$ is $O(m^t)$ then $\forb(m,F)$ is $O(m^{t+1})$.\qed
\end{lemma}


A slightly more careful argument is required if $F$ is not simple. We forbid from $C(r)$ any $(k\,$-$1)$-rowed  $F'$  that satisfies
$$F\prec \left[\begin{array}{cc}0\,0\,\cdots\,0&1\,1\,\cdots\,1\\ F'&F'\\ \end{array}\right].$$
While this may look quite general, there is more that can be said about $C(r)$ in some cases. For example if $F=2\cdot F'$, then $C(r)$ avoids $F'$.
This was used in \trf{twiceF0220}. Induction on the number of rows (elements) is a mainstay of studying set systems. Here is an application of a slight variant  of  standard argument. 
Recall that in an $m$-rowed matrix $A$, a set $S\subseteq [m]$ is \emph{shattered} if $K_{|S|}\prec A|_S$.
$$\hbox{Let }{\hbox{sh}(A)}=\{S\subseteq [m]\,:\,K_{|S|}\prec A|_S\}$$

\begin{thm}\cite{Pajor}\label{pajorshattered} Let $A$ be given. Then $\,|\hbox{sh}(A)|\ge \ncols{A}$.\end{thm}

\proof Decompose  $A$ as follows:
$$A=\left[\begin{array}{cc}0\,0\,\cdots\,0&1\,1\,\cdots\,1\\ A_0&A_1\\ \end{array}\right].$$

Then $\ncols{A}=\ncols{A_0}+\ncols{A_1}$. By induction $|\hbox{sh}(A_0)|\ge \ncols{A_0}$ and $|\hbox{sh}(A_1)|\ge \ncols{A_1}$.
Now $|\hbox{sh}(A_0)\cup \hbox{sh}(A_1)|=|\hbox{sh}(A_0)|+|\hbox{sh}(A_1)|-|\hbox{sh}(A_0)\cap \hbox{sh}(A_1)|$. If $S\in \hbox{sh}(A_0)\cap \hbox{sh}(A_1)$, then $1\cup S\in \hbox{sh}(A)$. Thus the number of sets in $\hbox{sh}(A)$ that are not in  $\hbox{sh}(A_0)\cup \hbox{sh}(A_1)$ is at least  $|\hbox{sh}(A_0)\cap \hbox{sh}(A_1)|$. We conclude
$|\hbox{sh}(A)|\ge |\hbox{sh}(A_0)|+ |\hbox{sh}(A_1)|$. 
Hence $|\hbox{sh}(A)|\ge \ncols{A}$. \qed
\vskip 5pt
 Note that this yields a proof of \trf{sauer}. In \cite{ARS}  we use this induction where we always choose row 1.




\begin{lemma}\label{tworow} Let $F'$ be a $k\times \l$ $(0,1)$-matrix  for which
$\forb(m,F')$ is $O(m^t)$. Then with
$$F=\left[\begin{array}{c}11\cdots 1\\ 00\cdots 0\\ F'\end{array}\right],$$
we have $\forb(m,F)$ being $O(m^{t+1})$.\qed\end{lemma}
\proof Let $A\in\Av(m,F)$. Ignoring the column of 0's and the column of 1's, we decompose the columns of $A$ into blocks $Z_i$ and $J_i$ where $Z_i$ consists of those columns of $A$ whose first $i+1$ rows are $\0_i\1_1$ and $J_i$ consists of those columns of $A$ whose first $i+1$ rows are $\1_i\0_1$. Now $F\not\prec Z_i$ implies that $\ncols{Z_i}\le\forb(m-i-1,F')$. Similarly  $\ncols{J_i}\le\forb(m-i-1,F')$. The result follows by summing the bounds.\qed

\vskip 5pt
An application of this induction is in Theorem~\ref{twocol}.  I would point out that we can extend these arguments (Lemma~\ref{onerow}, Lemma~\ref{tworow}) to families of forbidden configurations which may have relevance in the standard induction  in view of Lemma~\ref{onerow}. A two-rowed induction was used with success in \cite{AS97} in the case that the columns of matrix $A$ form an antichain as sets. Using that fact, we can deduce that $C$ is empty in the decomposition (\ref{standarddecomp}) above and so we may write
$$A=\left[\begin{array}{cccc}
00\cdots0& 00\cdots0& 11\cdots 1& 11\cdots 1\\
00\cdots0&  11\cdots 1&00\cdots0& 11\cdots 1\\
 C_1&C_2C_3&C_3C_4&C_5
\end{array}\right],$$
where $[C_1C_2C_3C_4C_5]$ is simple.

Induction, used cleverly, is the gift that keeps on giving. We used a new version of our standard induction where we consider the minimal set of rows in $C(r)$ for which the matrix of those rows is simple.  
This idea was used successfully in combination with the `what is missing' idea (\srf{missing}) to obtain structural results that led to proofs of 
\trf{I2xI2,I2xT2,T2xT2}\cite{IIcT} and \trf{F7thm}\cite{F7}.  

We have used repeated induction to obtain a number of results including
extensions of \trf{sauer} to \trf{simple,k-2} and also \trf{sauerextend}.  It turns out that consideration of base cases becomes difficult. Theorem 4.1 in
\cite{AKarp} considers the $k$-rowed configuration $F=[\1_k\,|\,2\cdot (\1_2\0_2)\times K_{k-4}]$ for which 
$\forb(k,F)>\forb(k,K_k)$ but we may verify $\forb(k+1,F)=\forb(k+1,K_k)$. 
\trf{sauerextend} \cite{AnsteeMeehan} also has $\forb(m,[K_k\,|\,(\1_2\0_2)\times K_{k-4}])>\forb(m,K_k)$ for $m=k$ and perhaps $m=k+1$ and perhaps  a  additional small values of $m$. We succeed establishing $\forb(k+1,[K_k\,|\,(\1_2\0_2)\times K_{k-4}])=\forb(k+1,K_k)$ for $k\le 15$ which establishes $\forb(m,[K_k\,|\,(\1_2\0_2)\times K_{k-4}])=\forb(m,K_k)$ for $m\ge k+1$. For larger $k$,  new arguments are needed.

\section{Shifting proofs}\label{shifting}

Peter Frankl popularized the use of shifting arguments in extremal set theory.
In this particular context there is a paper of Frankl \cite{Fr} and a paper of Alon \cite{Alon} using shifting techniques to generalize  Theorem~\ref{sauer}. I extended these
arguments and used them in \cite{A88}. Shifting is easily defined in set language. Let ${\mathcal F}\subseteq 2^{[m]}$. Let 
$$T_j(B)=\left\{\begin{array}{cc}B&\hbox{ if }j\notin B\hbox{ or if }B\backslash j\in{\mathcal F}\\ B\backslash j&\hbox{ if }j\in B\hbox{ and }B\backslash j\notin {\mathcal F}\\ \end{array}\right..$$
Then
$$T_j({\mathcal F})=\{ T_j(B)\,:\,B\in{\mathcal F}\}.$$
Note that $|T_j({\mathcal F})|=|{\mathcal F}|$. We can repeatedly apply $T_j$ for each $j=1,2,\ldots ,m$ to obtain the {\it shifted family} $T({\mathcal F})$ which has the property that
$$T_j(T({\mathcal F}))=T({\mathcal F})\hbox{ for }j=1,2,\ldots m.$$
Thus $|T({\mathcal F})|=|{\mathcal F}| $ and $T({\mathcal F})$ is a {\it downset} (namely for every $B\in T({\mathcal F})$ and every $C\subseteq B$, we have $C\in T({\mathcal F})$). Now let $S\subseteq [m]$ and let
$${\mathcal F}|_S=\{B\cap S\,:\,B\in{\mathcal F}\}$$

\begin{thm}\label{shiftingineq} Let $S\subseteq [m]$. Then
$$\bigl|{\mathcal F}|_{S}\bigr|\ge \bigl|T({\mathcal F})|_{S}\bigr|.\qed$$
\end{thm}
Using this one can prove Theorem~\ref{sauer} by noting that if ${\mathcal F}$ has no configuration
$K_k$ then for any $S\in\binom{ [m]}{k}$, we have $|{\mathcal F}|_{S}|\le 2^k-1$ and hence $|T({\mathcal F})|_{S}|\le 2^k-1$. Since $T({\mathcal F})$ is a downset, the column of $k$ 1's is absent. Thus we deduce
$|{\mathcal F}|=|T({\mathcal F})|\le \binom{m}{k-1}+\binom{m}{k-2}+\cdots +\binom{m}{0}$ and hence prove Theorem~\ref{sauer}.

Another application is for the forbidden matrix $F_3$ of Section~\ref{k=3}, for which we note that a simple matrix $A$ avoiding $F_3$ has at most 6 column types on any 3 rows. A consequence is the exact bound of Theorem~\ref{F_3}. Alon \cite{Alon} refers to such possible results.

The shifting argument was utilized in \cite{AA} to obtain a forbidden configuration theorem associated with any ideal (downset) in the lattice of divisors. This led to the notion of order shattered sets in \cite{ARS}. These lead to multiset versions of Theorem~\ref{shiftingineq}.

\section{Graph Theory}\label{graphtheory}

The use of Graph Theory is easiest to understand in considering a $2\times \l$ forbidden configuration $F$. In that case, it is natural to form a graph whose vertices are the rows of the matrix $A$. We consider what is missing if we forbid a  2-rowed $F$ as in Section~\ref{missing} and so columns in `short supply' or absent can be noted in the graph perhaps using edge labels or directed edges (there are only 4 possible columns on 2 rows!). Results in that direction are repeatedly used in \cite{AGS},\cite{AFS},\cite{AKa}.

Results about cliques, connectivity, chromatic number are used. The following specialized result was obtained (a generalization of R\'edei's Theorem that every tournament has a directed Hamiltonian path) in \cite{AFS} 
(some minor errors in published proof!) to obtain the exact bound \trf{1pp0}.

\begin{lemma}
\label{graph}
Let $D=(N,A)$ be a directed graph. There is an
ordering of the vertices $N$ as $1,2,\ldots m$
where $m=|N|$ and a subset $T\subseteq A$ consisting of a 
collection of vertex
disjoint indirected trees  with the following property.
Each arc $p\rightarrow q$ of $T$ has $p<q$ in the ordering.  
For each pair $i,j$, $1\le i<j\le m$ 
either there is a directed path in $T$ from $i$ to $j$
or there is a $k$ with $i\le k\le m$ so that there is
a directed path from $i$ to $k$ in $T$ and there is no edge in $D$
from $k$ to $j$.\qed
\end{lemma}


Graph Theory was successfully employed
for larger $F$ in \cite{AS05} where the vertex set corresponds to $\binom{[m]}{k}$. The standard decomposition of a directed graph into strongly connected components with an acyclic graph between the strongly connected components was an essential tool. We used that a linear number (linear in the number of vertices)  of directed edges is sufficient to assure strong connectivity. This idea was again employed in \cite{AFl10} along with indicator polynomials to establish Theorem~\ref{boundary}.



\section{Linear Algebra}\label{linalg}

Applications of linear algebra here include the proof of \trf{sauer}. Frankl and Pach obtained results for {\it null} $t$-{\it designs} \cite{FP83}.
One approach is the following. Given two columns $\beta,\gamma$, we say $\beta$ {\it covers} $\gamma$ if and only if $\beta\ge\gamma$. For an $m\times n$ simple matrix $A$ and an $m\times 1$ (0,1)-vector $\gamma$, we can define 
$A(\gamma)$ as the $1\times n$ (0,1)-row vector with a 1 in position $j$ if column $j$ of $A$ covers $\gamma$.

Now the vector space
$V=\hbox{span}\{A(\gamma)\,:\,\gamma\in {\bf R}^n\}$ is a vector space of dimension $n$ and moreover
$\{A(\gamma)\,:\,\gamma\hbox{ is a column of }A\}$ is a basis for $V$.
Now if we take 
$$\Gamma_{k-1}=\{\gamma\,:\,\hbox{ there exists an }s\hbox{ with }0\le s\le k-1\hbox{ and }\gamma\hbox{ is a column of }K_m^s\}$$
 we are able to verify the following.

\begin{thm}\cite{FP83}(\cite{R72},\cite{A85}). let $A$ be an $m\times n$ simple matrix with no configuration $K_k$. Then $n$ is the dimension of $V=\hbox{span}\{A(\gamma)\,:\,\gamma\in \Gamma_{k-1}\}$ for $\Gamma_{k-1}=\{\gamma\,:\,\hbox{ there exists an }s\hbox{ with }0\le s\le k-1\hbox{ and }\gamma\hbox{ is a column of }K_m^s\}$. Hence
$$n\le |\Gamma_{k-1}|=\binom{m}{k-1}+\binom{m}{k-2}+\cdots +\binom{m}{0}\qed$$\end{thm}


Another application of linear algebra is considering columns in short supply using \emph{indicator polynomials}: Given an $m\times 1$ (0,1)-column $\alpha$ we can create a multilinear polynomial $p(\x)$ of degree $m$ in variables $x_1,x_2,\ldots ,x_m$ that evaluates to 1 for column $\alpha$ ( where we take $x_i=\alpha_i$ for each $i=1,2,\ldots ,m$) and evaluates to 0 for all other (0,1)-columns.   

Let $A\in\Av(m,K_k)$. Then for each subset $S\subseteq [m]$ with $|S|=k$, we have that $A|_S$ has at least one missing column, say $\alpha(S)$, else $A$ has $K_k$.  Smolensky \cite{Smolensky} noted that the dimension of the space of real valued functions on the columns of $A$ is $\ncols{A}$. Any real valued function on the columns of $A$ can be given as a multilinear polynomial. Let $\x=(x_1,x_2,\ldots ,x_m)$.  In particular for a column $\alpha=(\alpha_1,\alpha_2,\ldots ,\alpha_m)^T$ we can form $\prod_{i=1}^m(x_i-1+\alpha_i)$ which will be non-zero only for column $\x=\alpha$ for all $\x\in\{0,1\}^n$. A suitable linear combination of such multilinear polynomials (one for each column $\alpha$ of $A$)  will yield any real valued function on columns of $A$. Smolensky showed that linear combinations of multilinear polynomials of degree at most $k-1$ suffice and so the dimension of that space is the bound of  \trf{sauer}. Thus we have the bound of \trf{sauer}  for $\ncols{A}$.    Assume $f(\x)$ contains an expression $x_1x_2\cdots x_k$ and let  $S=\{1,2,\ldots ,k\}$. Then  given the column $\alpha(S)=(\alpha_1,\alpha_2,\ldots ,\alpha_k)^T$, we can form a polynomial $f_S(\x)=\prod_{i=1}^k(x_i-1+\alpha_i)$ of degree $k$ with leading term $x_1x_2\cdots x_k$ so that for $\x\in\{0,1\}^n$, 
$f_S(\x)$ is 0 if $\x|_S\ne\alpha(S)$ for $\x\in\{0,1\}^n$.   We can now replace  $x_1x_2\cdots x_k$ by $x_1x_2\cdots x_k-f_S(\x)$. The new polynomial will evaluate to the same values on the columns of $A$ and we will have replaced $x_1x_2\cdots x_k$ by terms of degree at most $k-1$. Do this for all choices of $S$ and repeat until you obtain a polynomial of degree at most $k-1$.



 This idea of indicator polynomials was exploited in  \cite{AFFS} for cases where each $k$-set of rows has two missing columns  and further exploited in \cite{AFl10}. Different ways to achieve a reduction in degree occur.
 
L. Ronyai noted how some of the inductive proofs and the concept of \emph{order shattering} were suited to 
\emph{Gr\"obner bases} \cite{ARS} and some nice applications followed. There are cases where the  Gr\"obner basis can be computed in a general way \cite{HR}. There are application to Forbidden Configurations. 
\trf{pajorshattered} proved by Pajor states $|\hbox{sh}(A)|\ge \ncols{A}$.  R\'onyai and  M\'esz\'aros \cite{RM} use Gr\"obner bases to characterize  family of sets ${\cal F}$ with
$|\hbox{sh}({\cal F})|=|{\cal F}|$.

 
 
 
 




\section{Strong Stability}\label{strongstability}
The idea of strong stability is to show that a set system satisfying some property (in our case having a forbidden configuration $F$) and having a number of sets close to the optimal value (for us $\forb(m,F)$) that the system of sets has much of its structure already determined. This contrasts sharply with \trf{sauer} for which there are a multiplicity of matrices achieving the given bound (e.g. Theorem 1.1\cite{A83a}, Theorem 4.2\cite{A88}, Theorem 3.1\cite{AS97}).

The strong stability result used in proving Theorem~\ref{twocol} considers a $k$-uniform set system with no $F_{0,r+1,r+1,0}$ (the notation $F_{abcd}$ is defined in Section~\ref{l=2}) which is equivalent to having the set system be $k-r$-intersecting. As noted when introducing Theorem~\ref{one-way}, having no configuration $F_{0,r+1,r+1,0}$ is the same as having no submatrix $F_{0,r+1,0,0}$ for a $k$-uniform family.
Let numbers $k,r_1,r_2$ be given and suppose $G$ and $H$
are given disjoint sets with $|G|=k-r_1+r_2$. We define
$\mathcal{I}^k_{r_1,r_2}$ on the pair $(H,G)$ to
be the family consisting
of all sets of size $k$ in $G \cup H$ that intersect
$G$ in at least $k-r_1 = |G|-r_2$ points. Note
that any two sets in $\mathcal{I}^k_{r_1,r_2}$ have
at least $|G|-2r_2 = k - r_1 - r_2$ points in common,
i.e. $\mathcal{I}^k_{r_1,r_2}$ is $(k-r)$-intersecting,
where $r=r_1+r_2$. The Complete Intersection Theorem,
conjectured by Frankl, and proved by Ahlswede
and Khachatrian \cite{AhKh97a}, is that any $k$-uniform,
$(k-r)$-intersecting family of maximum size on
a given ground set is isomorphic to
$\mathcal{I}^k_{r-p,p}$, for some $0 \leq p \leq r$, which depends on
the size of the ground set. Note
that $|\mathcal{I}^k_{r_1,r_2}|$ is  $O(m^r)$ ($\Theta(m^r)$ for $|G|$ and $|H|$ being $\Theta(m)$).
The following was critical to prove \trf{twocol}.

\begin{thm}\label{strong}\cite{AK}
Suppose $\mathcal{A}$ is a $k$-uniform $(k-r)$-intersecting
set system on $[m]$ of size at least $(5r)^{5r} m^{r-1}$.
Then $\mathcal{A} \subseteq \mathcal{I}^k_{r-p,p}$ for
some $0 \leq p \leq r$.
\end{thm}

We are also interested in the related family of sets
$\mathcal{F}^k_{r_1,r_2}$ on the pair $(H,G)$ to
be the family consisting
of all sets of size $k$ in $G \cup H$ that intersect
$G$ in exactly $k-r_1 = |G|-r_2$ points. Note
that $|\mathcal{F}^k_{r_1,r_2}|$ is also $O(m^r)$ and that
$|\mathcal{I}^k_{r_1,r_2}\backslash\mathcal{F}^k_{r_1,r_2}|$ is $O(m^{r-2})$.
A proof of Theorem~\ref{strong} in the case $r=1$ (where there are no asymptotics) is used in
\cite{Aunpub}. 


\begin{prob}\label{exactbounds} Can you to use Theorem~\ref{strong} to prove some more exact bounds for $F$ being  the $2k\times 2$ matrix of $k$ copies of $I_2$ for which the bound is $O(m^k)$ by Theorem~\ref{one-way} \cite{FFP} (or Theorem~\ref{twocol})?  Corollary~\ref{4x2} is the case $k=2$.\end{prob}

\newcommand{\etalchar}[1]{$^{#1}$}
\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\providecommand{\MR}{\relax\ifhmode\unskip\space\fi MR }
% \MRhref is called by the amsart/book/proc definition of \MR.
\providecommand{\MRhref}[2]{%
  \href{http://www.ams.org/mathscinet-getitem?mr=#1}{#2}
}
\providecommand{\href}[2]{#2}
\begin{thebibliography}{ADF{\etalchar{+}}11}

\bibitem[AA95]{AA}
R.E.L. Aldred and R.P. Anstee, \emph{On the density of sets of divisors},
  Discrete Math. \textbf{137} (1995), 345--349.

\bibitem[AB]{AB}
R.P. Anstee and F.~Barekat, \emph{Design theory and some non-simple forbidden
  configurations}, submitted to J. Combinatorial Designs, 21pp.

\bibitem[ABS11]{ABS}
R.P. Anstee, F.~Barekat, and A.~Sali, \emph{Small forbidden configurations {V}:
  Exact bounds for $4\times 2$ cases}, Studia. Sci. Math. Hun. \textbf{48}
  (2011), 1--22.

\bibitem[AC13]{AnsteeChen}
R.P. Anstee and R.~Chen, \emph{Forbidden submatrices: New bounds and
  constructions}, Electronic Journal of Combinatorics \textbf{20} (2013), P5
  13pp.

\bibitem[AD]{AD}
R.P. Anstee and L.~Dunwoody, \emph{notes}.

\bibitem[ADF{\etalchar{+}}11]{ADFGW}
Ittai Abraham, Daniel Delling, Amos Fiat, Andrew~V. Goldberg, and Renato~F.
  Werneck, \emph{{VC}-dimension and shortest path algorithms}, Proc. ICALP 2011
  (2011).

\bibitem[AF84]{AFa84}
R.P. Anstee and M.~Farber, \emph{Characterizations of totally balanced
  matrices}, Journal of Algorithms \textbf{5} (1984), 215--230.

\bibitem[AF86]{AF}
R.P. Anstee and Z.~F{\"{u}}redi, \emph{Forbidden submatrices}, Discrete Math.
  62 (1986), 225--243.

\bibitem[AF10]{AFl10}
R.P. Anstee and B.~Fleming, \emph{Two refinements of the bound of {Sauer,
  Perles and Shelah and Vapnik and Chervonenkis}}, Discrete Mathematics
  \textbf{310} (2010), 3318--3323.

\bibitem[AF11]{AFllinalg}
\bysame, \emph{Linear algebra methods for forbidden configurations},
  Combinatorica \textbf{31} (2011), 1--19.

\bibitem[AFFS05]{AFFS}
R.P. Anstee, B.~Fleming, Z.~F{\"{u}}redi, and A.~Sali, \emph{Color critical
  hypergraphs and forbidden configurations}, Proceedings of EuroComb 2005
  (2005), 117--122.

\bibitem[AFS01]{AFS}
R.P. Anstee, R.~Ferguson, and A.~Sali, \emph{Small forbidden configurations
  {II}}, Electronic Journal of Combinatorics \textbf{8} (2001), R4 25pp.

\bibitem[AGS97]{AGS}
R.P. Anstee, J.R. Griggs, and A.~Sali, \emph{Small forbidden configurations},
  Graphs and Combinatorics \textbf{13} (1997), 97--118.

\bibitem[AK97a]{AhKh97a}
R.~Ahlswede and L.H. Khachatrian, \emph{The complete intersection theorem for
  systems of finite sets}, European Journal of Combinatorics \textbf{16}
  (1997), 125--136.

\bibitem[AK97b]{AhKh97b}
\bysame, \emph{Counterexample to the {Frankl-Pach} conjecture for uniform dense
  families}, Combinatorica \textbf{17} (1997), 299--301.

\bibitem[AK06]{AK}
R.P. Anstee and P.~Keevash, \emph{Pairwise intersections and forbidden
  configurations}, European Journal of Combinatorics \textbf{27} (2006),
  1235--1248.

\bibitem[AK07]{AKa}
R.P. Anstee and N.~Kamoosi, \emph{Small forbidden configurations {III}},
  Electronic Journal of Combinatorics \textbf{14} (2007), R79 34pp.

\bibitem[AK10]{AKarp}
R.P. Anstee and S.N. Karp, \emph{Forbidden configurations: Exact bounds
  determined by critical substructures}, Electronic Journal of Combinatorics
  \textbf{17} (2010), R50 28pp.

\bibitem[AKRS11]{IIcT}
R.P. Anstee, Christina Koch, Miguel Raggi, and Attila Sali, \emph{Forbidden
  configurations and product constructions}, submitted to Graphs and
  Combinatorics. (2011).

\bibitem[Alo83]{Alon}
N.~Alon, \emph{On the density of sets of vectors}, Discrete Math \textbf{46}
  (1983), 199--202.

\bibitem[AM85]{AM}
R.P. Anstee and U.S.R. Murty, \emph{Matrices with forbidden subconfigurations},
  Discrete Math \textbf{54} (1985), 113--116.

\bibitem[AM11]{AnsteeMeehan}
R.P. Anstee and C.G.W. Meehan, \emph{Forbidden configurations and repeated
  induction}, Discrete Math. \textbf{311} (2011), 2187--2197.

\bibitem[Ans80a]{A80a}
R.P. Anstee, \emph{Properties of (0,1)-matrices with forbidden configurations},
  Annals of Discrete Math \textbf{9} (1980), 177--179.

\bibitem[Ans80b]{A80}
\bysame, \emph{Properties of (0,1)-matrices with no triangles}, Journal of
  Combinatorial Theory Ser. A \textbf{29} (1980), 186--198.

\bibitem[Ans81]{A81}
\bysame, \emph{Properties of (0,1)-matrices without certain configurations},
  Journal of Combinatorial Theory Ser. A \textbf{31} (1981), 256--269.

\bibitem[Ans83a]{A83b}
\bysame, \emph{Extensions of the notion of conformality in hypergraphs},
  Congressus Numerantium \textbf{39} (1983), 82--88.

\bibitem[Ans83b]{A83a}
\bysame, \emph{Hypergraphs with no special cycles}, Combinatorica \textbf{3}
  (1983), 141--146.

\bibitem[Ans85]{A85}
\bysame, \emph{General forbidden configuration theorems}, Journal of
  Combinatorial Theory Ser. A \textbf{40} (1985), 108--124.

\bibitem[Ans88]{A88}
\bysame, \emph{A forbidden configuration theorem of {Alon}}, Journal of
  Combinatorial Theory Ser. A \textbf{47} (1988), 16--27.

\bibitem[Ans90a]{A90}
\bysame, \emph{Forbidden configurations, determinants and discrepancy},
  European Journal of Combinatorics \textbf{11} (1990), 15--19.

\bibitem[Ans90b]{Aunpub}
\bysame, \emph{Some problems concerning forbidden configurations}, preprint
  (1990).

\bibitem[Ans95]{A95}
\bysame, \emph{Forbidden configurations: Induction and linear algebra},
  European Journal Of Combinatorics \textbf{16} (1995), 427--438.

\bibitem[Ans00]{A00}
\bysame, \emph{On a conjecture concerning forbidden submatrices}, Journal of
  Combin. Math and Combin. Comp. \textbf{32} (2000), 185--192.

\bibitem[AR]{AR}
R.P. Anstee and C.~Ryan, \emph{notes}.

\bibitem[AR11]{genetic}
R.P. Anstee and Miguel Raggi, \emph{Genetic algorithms applied to problems of
  forbidden configurations}, Electronic Journal of Combinatorics \textbf{18}
  (2011), P230 23pp.

\bibitem[ARS02]{ARS}
R.P. Anstee, L.~Ronyai, and A.~Sali, \emph{Shattering news}, Graphs and
  Combinatorics \textbf{18} (2002), 59--73.

\bibitem[ARS11]{F7}
R.P. Anstee, Miguel Raggi, and Attila Sali, \emph{Forbidden configurations:
  Quadratic bounds}, submitted to European J. of Combin. (2011).

\bibitem[ARS12]{F8}
\bysame, \emph{Evidence for a forbidden configuration conjecture; one more case
  solved}, Discrete Math. \textbf{312} (2012), 2720--2729.

\bibitem[AS97]{AS97}
R.P. Anstee and A.~Sali, \emph{Sperner families of bounded {VC}-dimension},
  Discrete Math. \textbf{175} (1997), 13--21.

\bibitem[AS05]{AS05}
\bysame, \emph{Small forbidden configurations {IV}}, Combinatorica \textbf{25}
  (2005), 503--518.

\bibitem[Bal12]{Balachandran}
R.~Balachandran, \emph{Forbidden configurations and steiner designs}, Designs,
  Codes and Cryptography \textbf{65} (2012), 353--364.

\bibitem[BB05]{BB}
J.~Balogh and B.~Bollob{\'a}s, \emph{Unavoidable traces of set systems},
  Combinatorica \textbf{25} (2005), 633--643.

\bibitem[BC87]{BC}
R.E. Bixby and W.H. Cunningham, \emph{Short cocircuits in binary matroids},
  European J. Of Combin. \textbf{8} (1987), 213--225.

\bibitem[BG91]{BG}
D.~Bienstock and E.~Gy{\"o}ri, \emph{An extremal problem on sparse 0-1
  matrices}, SIAM J. Discrete Math \textbf{4} (1991), 17--27.

\bibitem[BKS05]{BKS}
J.~Balogh, P.~Keevash, and B.~Sudakov, \emph{Disjoint representability of sets
  and their complements}, Journal of Combinatorial Theory Ser. B \textbf{95}
  (2005), 12--28.

\bibitem[BP09]{BaloghPrince}
J.~Balogh and N.~Prince, \emph{Minimum difference representations of graphs},
  Graphs and Combinatorics \textbf{25} (2009), 647--655.

\bibitem[dCF00]{dCF}
Dominique de~Caen and Z.~F{\"{u}}redi, \emph{The maximum size of 3-uniform
  hypergraphs not containing a {F}ano plane}, Journal of Combinatorial Theory
  Ser. B \textbf{78} (2000), 274--276.

\bibitem[Duk10]{Dukes}
P.~Dukes, \emph{personal communication}, 2010.

\bibitem[EFF85]{EFF}
P.~Erd{\H{o}}s, P.~Frankl, and Z.~F{\"u}redi, \emph{Families of finite sets in
  which no set is covered by the union of $r$ others}, Israel J. Math.
  \textbf{51} (1985), 79--89.

\bibitem[ES46]{ES}
P.~Erd{\H{o}}s and A.H. Stone, \emph{On the structure of linear graphs},
  Bulletin of the American Mathematical Society \textbf{52} (1946), 1089--1091.

\bibitem[ES66]{Simon}
Paul Erd{\H{o}}s and Mikl\'os Simonovits, \emph{A limit theorem in graph
  theory.}, Studia Scientiarum Mathematicarum Hungarica \textbf{1} (1966),
  51--57.

\bibitem[FFP87]{FFP}
P.~Frankl, Z.~F{\"{u}}redi, and J.~Pach, \emph{Bounding one-way differences},
  Graphs and Combinatorics \textbf{3} (1987), 341--347.

\bibitem[FH92]{FH}
Z.~F{\"{u}}redi and P.~Hajnal, \emph{{Davenport-Schinzel} theory of matrices},
  Discrete Math \textbf{103} (1992), 233--251.

\bibitem[FP83]{FP83}
P.~Frankl and J.~Pach, \emph{On the number of sets in a null {$t$}-design},
  European J. Of Combin. \textbf{4} (1983), 21--23.

\bibitem[FP84]{FP84}
\bysame, \emph{On disjointly representable sets}, Combinatorica \textbf{4}
  (1984), 39--45.

\bibitem[FP94]{FP94}
Z.~F{\"{u}}redi and J.~Pach, \emph{Traces of finite sets: extremal problems and
  geometric applications}, vol.~3, Bolyai Society Mathematical Studies, 1994.

\bibitem[FQ83]{FQ}
Z.~F{\"{u}}redi and F.~Quinn, \emph{Traces of finite sets}, Ars Combin.
  \textbf{18} (1983), 195--200.

\bibitem[Fra83]{Fr}
P.~Frankl, \emph{On the trace of finite sets}, Journal of Combinatorial Theory
  Ser. A \textbf{34} (1983), 41--45.

\bibitem[FS05]{FS}
Z.~F{\"{u}}redi and M.~Simonovits, \emph{Triple systems not containing a {Fano}
  configuration}, Combinatorics, Computing and Probability \textbf{14} (2005),
  467--484.

\bibitem[FS12]{FurediSali}
Z.~F{\"{u}}redi and A.~Sali, \emph{Optimal multivalued shattering}, SIAM J.
  Discrete Math. \textbf{26} (2012), 737--744.

\bibitem[F{\"{u}}r83]{F}
Z.~F{\"{u}}redi, \emph{personal communication}, 1983.

\bibitem[F{\"{u}}r90]{F90}
Z.~F{\"{u}}redi, \emph{Maximum unit distances in a convex $n$-gon}, Journal of
  Combinatorial Theory Ser. A \textbf{55} (1990), 316--320.

\bibitem[F{\"{u}}r91]{F91}
\bysame, \emph{Tur\'an type problems}, Surveys in Combinatorics (Proc. of the
  13th British Combinatorial Conference), ed. A.D. Keedwell, Cambridge Univ.
  Press. London Math. Soc. Lecture Note Series \textbf{166} (1991), 253--300.

\bibitem[Gro80]{G}
H.O.F. Gronau, \emph{An extremal set problem}, Studia Sci.Math. Hungar
  \textbf{15} (1980), 29--30.

\bibitem[HKS86]{HKS}
A.J. Hoffman, A.W.J. Kolen, and M.~Sakarovitch, \emph{Totally-balanced and
  greedy matrices}, SIAM J. Algebraic Discrete Methods \textbf{7} (1986),
  348--357.

\bibitem[HR03]{HR}
G\'abor Heged{\"u}s and Lajos R\'onyai, \emph{Gr{\"o}bner bases for complete
  uniform families}, J. Algebraic Combinatorics \textbf{17} (2003), 171--180.

\bibitem[HW87]{HW}
D.~Haussler and E.~Welzl, \emph{Epsilon-nets and simplex range queries},
  Discrete Comput. Geom. \textbf{2} (1987), 127--151.

\bibitem[Kle66]{K}
D.J. Kleitman, \emph{On a combinatorial conjecture of {Erd{\H{o}}s}}, Journal
  of Combinatorial Theory \textbf{1} (1966), 209--214.

\bibitem[KM78]{KM}
M.G. Karpovsky and V.D. Milman, \emph{Coordinate density of sets of vectors},
  Discrete Math \textbf{24} (1978), 177--184.

\bibitem[KM10]{KM2010}
P.~Keevash and D.~Mubayi, \emph{Set systems without a simplex or cluster},
  Combinatorica \textbf{30} (2010), 175--200.

\bibitem[K{\"o}r95]{Korner}
J~K{\"o}rner, \emph{On the extremal combinatorics of the hamming space},
  Journal of Combinatorial Theory Ser. A \textbf{71} (1995), 112--126.

\bibitem[KS73]{KS}
D.J. Kleitman and J.~Spencer, \emph{Families of $k$-independent sets}, Discrete
  Math. \textbf{6} (1973), 255--262.

\bibitem[KST54]{KST}
K{\"o}vari, V.~S{\'o}s, and P.~Tur{\'a}n, \emph{On a problem of {K.
  Zarankiewicz}}, Colloq. Math. \textbf{3} (1954), 50--57.

\bibitem[LKL{\etalchar{+}}11]{LKLKF}
J.~Lawrence, R.~N. Kacker, Y.~Lei, D.R. Kuhn, and M.~Forbes, \emph{A survey of
  binary covering arrays}, Electronic Journal of Combinatorics \textbf{18}
  (2011), P84 30pp.

\bibitem[{\L}S10]{LT}
T.~{\L}uczak and Thomass\'e S., \emph{Coloring dense graphs via
  {VC}-dimension}, preprint (2010).

\bibitem[Mat02]{M}
J.~Matou\v{s}ek, \emph{Lectures in discrete geometry}, Springer, 2002.

\bibitem[MT04]{MT}
A.~Marcus and G.~Tardos, \emph{Excluded permutation matrices and the {Stanley
  Wilf Conjecture}}, Journal of Combinatorial Theory Ser. A \textbf{107}
  (2004), 153--160.

\bibitem[MZ07a]{MZ07}
D.~Mubayi and J.~Zhao, \emph{On the {VC}-dimension of uniform hypergraphs},
  Journal of Algebraic Combinatorics \textbf{25} (2007), 101--110.

\bibitem[MZ07b]{MubayiZhao}
Dhruv Mubayi and Y.~Zhao, \emph{Forbidding complete hypergraphs as traces},
  Graphs and Combinatorics \textbf{23} (2007), 667--679.

\bibitem[Paj85]{Pajor}
A.~Pajor, \emph{Sous-espaces $2_1^n$ des espaces de {Banach}, travaux en
  cours}, Hermann, Paris, 1985.

\bibitem[Pat09]{P}
B.~Patk{\'{o}}s, \emph{Traces of uniform families of sets}, Electronic Journal
  of Combinatorics \textbf{16} (2009), N8, 5pp.

\bibitem[Pik08]{Pikhurko08}
O.~Pikhurko, \emph{An exact bound for {Tur\'an} result for the generalized
  triangle}, Combinatorica \textbf{28} (2008), 187--208.

\bibitem[Rag11]{miguelthesis}
M.~Raggi, \emph{Forbidden configurations}, {Ph.D. Thesis}, University of
  British Columbia, 2011.

\bibitem[Rag12]{RNP}
\bysame, \emph{Forbidden configurations: Finding the number predicted by the
  {Anstee-Sali} conjecture is {NP}-complete}, preprint (2012).

\bibitem[RM11]{RM}
Lajos R\'onyai and Tam\'as M\'esz\'aros, \emph{Some combinatorial applications
  of gr{\"o}bner bases}, Proceedings of CAI 2011, LNCS 6742 (2011), 65--83.

\bibitem[RSZ12]{SSYZ}
B.~Yang R.~Samei, P.~Semukhin and S.~Zilles, \emph{Sauer's bound for a notion
  of teaching complexity}, {\it Algorithmic Learning Theory}, Proceedings, LNAI
  7568 (2012), 96--110.

\bibitem[Rys72]{R72}
H.J. Ryser, \emph{A fundamental matrix equation for finite sets}, Proc. Amer.
  Math. Soc. \textbf{34} (1972), 332--336.

\bibitem[Sau72]{Sauer}
N.~Sauer, \emph{On the density of families of sets}, Journal of Combinatorial
  Theory Ser. A \textbf{13} (1972), 145--147.

\bibitem[She72]{PS}
S.~Shelah, \emph{A combinatorial problem: Stability and order for models and
  theories in infinitary languages}, Pacific Journal of Mathematics \textbf{4}
  (1972), 247--261.

\bibitem[Smo97]{Smolensky}
R.~Smolensky, \emph{Well known bound for {VC}-dimension made easy},
  Computational Complexity. \textbf{6} (1997), 299--300.

\bibitem[Spi03]{Sp}
J.P. Spinrad, \emph{Efficient graph representations}, Fields Institute
  Monographs \textbf{9} (2003).

\bibitem[Ste78]{St}
Michael Steele, \emph{Existence of submatrices with all possible columns},
  Journal of Combinatorial Theory Ser. A \textbf{24} (1978), 84--88.

\bibitem[Tar05]{T05}
G.~Tardos, \emph{On 0-1 matrices and small excluded submatrices}, Journal of
  Combinatorial Theory Ser. A \textbf{111} (2005), 266--288.

\bibitem[VC71]{VC}
V.N. Vapnik and A.Ya. Chervonenkis, \emph{On the uniform convergence of
  relative frequencies of events to their probabilities}, Theory of Probability
  and Applications (1971), 264--280.

\end{thebibliography}


\end{document}



