\documentclass[12pt]{article} \usepackage{e-jc} \specs{DS20}{20(1)}{2013} \usepackage{amsthm} \usepackage{amsmath} \usepackage{amssymb} %\def\emph{#1}\textbf{#1} \sloppy \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}$} \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}\\ \small Mathematics Department\\[-0.8ex] \small The University of British Columbia\\[-0.8ex] \small Vancouver, B.C. Canada V6T 1Z2\\ {\small\texttt{anstee@math.ubc.ca}} } \date{\dateline{May 24, 2012}{Jan 21, 2013}{Jan 29, 2013}} \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 $[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 \trf{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 \trf{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 \trf{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 \trf{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 \trf{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 \trf{boundary} was first proved for $k=3$ in \cite{AS05}. \trf{B} was proven for general $k$ in \cite{AFllinalg},\cite{AFFS} and \trf{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 \trf{B} and $F\not\prec [K_k^0\,|\,t\cdot D_{12}])$ for $D_{12}$ as in \trf{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 \trf{k-2,matrices}. \trf{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 \trf{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$ and $\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}$. 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 \trf{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 \trf{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 \trf{sauer} to multisets with $e_1=e_2=\cdots =e_m=e$ is in \cite{St} and the extension of \trf{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 \trf{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 \trf{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 \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 \trf{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 \trf{classifyk=2}, $k=3$ in \trf{classifyk=3}, $l=2$ in \trf{twocol}, $k=4$ and $F$ simple in \trf{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})$?\\ 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.\\ (Constant Cases) If $F=F_2(0,1,0,0)$, then $\forb(m,F)=\Theta(1)$.\\ (Linear Cases) If $F$ has at least one configuration from $K_2^0$, $K_2^1$, $K_2^2$, \\ $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)$.\\ (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)$.\\ 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 \trf{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 p0$, 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 \trf{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.\\ (Linear Cases) If $F$ has at least one column and if $F$ is a configuration in $F_2$ then $\forb(m,F)=\Theta(m)$.\\ (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)$.\\ (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)$.\\ 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 \trf{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 \trf{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}$} &\trf{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 \trf{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.\\ (Linear Cases) If $F$ has a configuration $F_1$ and if $F$ is a configuration in $F_2$ then $\forb(m,F)=\Theta(m)$.\\%imw (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)$.\\ (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)$.\\ 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}. \trf{twocol}, \trf{simple,k-2} and \trf{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.\\ (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)$.\\ (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)$.\\ (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)$.\\ (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)$.\\ 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 \trf{onecol} and \trf{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 \trf{B} and \trf{boundary}. The quartic bound of \trf{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 $\{S_1,S_2,\ldots \}$ of distinct subsets of $[m]$ such that $|S_i\backslash S_j|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}. \bigskip %\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 \trf{one-way} \cite{FFP}. We prove \trf{twocol} using the strong stability result \trf{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}. \trf{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. \\ (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)$. \\ (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)$. \\ (Quartic Cases)\ If $F$ has a configuration one of $F_{30}, F_{31}, \ldots, F_{87}$ then $\forb(m,F)$ is $\Theta(m^4)$. \\ 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 \trf{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 \trf{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 \trf{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 \\ \hfil http://www.math.ubc.ca/$\sim$anstee/FConfThesisVersion.tar.gz \\ (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 \trf{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 \trf{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 \trf{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}%imw Now $[B(r)C(r)D(r)]$ is simple and has no configuration $F$. Also $\ncols{A}=\ncols{[B(r)C(r)D(r)]}+\ncols{C(r)}$. One can easily derive the upper bound of \trf{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 \trf{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 \trf{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 \trf{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 \trf{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 \trf{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 \trf{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