\section{Introduction}

We are initiating an exploration of families of forbidden configurations in this paper as recommended in \cite{miguelthesis}. We need some notation.
We say a matrix is \emph{simple} if it is a (0,1)-matrix with no repeated columns. Such a matrix can be viewed as an element-set incidence matrix.
Given two (0,1)-matrices $F,A$, if there is a submatrix of $A$ which is a row and column permutation of $F$ then we say $A$ has $F$ as a \emph{configuration} and write $F\prec A$.
In set terminology we could use the notation \emph{trace}. For a subset of rows $S$, we define $A|_S$ as the submatrix of $A$ consisting of rows $S$ of $A$.  We define $[n]=\{1,2,\ldots ,n\}$. If $F$ has $k$ rows and $A$ has $m$ rows and $F\prec A$ then there is a $k$-subset $S\subseteq[m]$ such that $F\prec A|_S$. For two $m$-rowed matrices $A,B$ we use $[A\,|\,B]$ to denote the concatenation of $A,B$ yielding a larger $m$-rowed matrix. We define $t\cdot A$ as the matrix obtained from concatenating $t$ copies of $A$. These two operations need not yield simple matrices. Let $A^c$ denote the (0,1)-complement of $A$.

Define $\ncols{A}$ as the number of columns of $A$. For some set of matrices  ${\cal F}$, we define our extremal problem as follows:
$${\mathrm{Avoid}}(m,{\cal F})=\{A\,:\,A\hbox{ is $m$-rowed, simple,}F\not\prec A\hbox{ for all }F\in{\cal F}\},$$
$${\hbox{forb}}(m,{\cal F})=\max_A\{\ncols{A}\,:\,A\in{\mathrm{Avoid}}(m,{\cal F})\}.$$
When $|{\cal F}|=1$ and ${\cal F}=\{F\}$, we write ${\mathrm{Avoid}}(m,F)$ and ${\hbox{forb}}(m,F)$.
  A conjecture of Anstee and Sali \cite{AS05} for a single configuration sometimes makes the correct predictions for the asymptotic growth of ${\hbox{forb}}(m,{\cal F})$.  Let $I_k$ denote the $k\times k$ identity matrix and let $T_k$ denote the $k\times k$ triangular simple matrix  with a 1 in position $(i,j)$ if and only $i\le j$.
 For an $m_1\times n_1$ simple matrix $A$ and a $m_2\times n_2$ simple matrix $B$, we define the 2-fold product $A\times B$ as the $(m_1+m_2)\times n_1n_2$ simple matrix whose columns are obtained from placing a column of $A$ on top of a column of $B$ in all possible ways. This generalizes to $p$-fold products.
For a configuration $F$ we define $X(F)$ as the smallest value of $p$ such that
$F\prec A_1\times A_2\times\cdots\times A_p$ for  every $p$-fold product where $A_i\in\{I_{m/p},I_{m/p}^c,T_{m/p}\}$.

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

We think that the conjecture will help in guessing asymptotic  bounds for ${\hbox{forb}}(m,{\cal F})$.
We may define $X({\cal F})$ as the smallest value of $p$ such that for every every $p$-fold product
$A_1\times A_2\times\cdots\times A_p$  where $A_i\in\{I_{m/p},I_{m/p}^c,T_{m/p}\}$ we have some $F\in{\cal F}$ with $F\prec A_1\times A_2\times\cdots\times A_p$.

Two easy remarks are the following.

\begin{remark}We have that ${\hbox{forb}}(m,\{F_1,F_2,\ldots,F_t\})={\hbox{forb}}(m,\{F_1^c,F_2^c,\ldots,F_t^c\})$.\label{complement}\end{remark}

\begin{remark}\label{FsubsetG}Let ${\cal F}\subseteq{\cal G}$. Then ${\hbox{forb}}(m,{\cal G})\le {\hbox{forb}}(m,{\cal F})$.\end{remark}

\begin{remark}\label{minimal}Let ${\cal F}$ be given with $F\in{\cal F}$. Let $F'$ be given with $F\prec F'$, Then  $ {\hbox{forb}}(m,{\cal F}\cup\{F'\})={\hbox{forb}}(m,{\cal F})$.\end{remark}

In view of \remrf{minimal}, we define ${\cal F}$ to be \emph{minimal} if there are no pair $F,F'\in{\cal F}$ with $F\prec F'$.

Some examples are in order.
 Balanced and totally balanced matrices are classes of matrices which can each be defined using an infinite family of forbidden configurations.
Let $C_k$ denote the vertex-edge incidence matrix of the cyle of length $k$. Thus
$$\hbox{e.g. }\,\,C_3=\left[\begin{array}{@{}ccc@{}}
1&0&1\\
1&1&0\\
0&1&1\\   \end{array}\right], C_4=\left[\begin{array}{@{}cccc@{}}
1&0&0&1\\
1&1&0&0\\
0&1&1&0\\
0&0&1&1\\   \end{array}\right].$$
A  matrix $A$  is \emph{balanced} if has no configuration $C_k$ for $k$ odd and a matrix is \emph{totally balanced} if it has no configuration $C_k$ for all $k\ge 3$.
These are important classes of matrices. While the definitions do not require the matrices to be simple, it is still of interest how many different columns can there be in a balanced (resp. totally balanced) matrix on $m$ rows.  We obtain an upper bound using \remrf{FsubsetG} and the lower bound  follows from the result that any $m\times {\hbox{forb}}(m,C_3)$ matrix $A\in{\mathrm{Avoid}}(m,C_3)$ is necessarily  totally balanced.

\begin{thm} \cite{A80}
 We have that ${\hbox{forb}}(m,C_3)={\hbox{forb}}(m,\{C_3,C_4,C_5,C_6,\ldots\})=$\hfil\break ${\hbox{forb}}(m,\{C_3,C_5,C_7,C_9,\ldots\})$.\end{thm}

The result ${\hbox{forb}}(m,C_3)=\binom{m}{2}+\binom{m}{1}+\binom{m}{0}$ is due to Ryser \cite{ryser72}. We note that \hfil\break $X(\{C_3,C_4,C_5,C_6,\ldots\})=X(\{C_3,C_5,C_7,C_9,\ldots\})=3$ where the construction $T_{m/2}\times T_{m/2}$ avoids $C_k$ for all $k\ge 3$. From another point of view, the result suggests that the bound for   a forbidden family  might arise from the most restrictive configuration in the family (i.e. ${\hbox{forb}}(m,{\cal F})=\min_{F\in{\cal F}}{\hbox{forb}}(m,F)$ or its asymptotic equivalent)  but this is generally not true.  The following examples suggest that forbidden families can behave  quite differently.  We consider the fundamental extremal function ${\hbox{ex}}(m,H)$ which denotes the maximum number of edges in a (simple) graph on $m$ vertices that has no subgraph $H$.  Let ${\bf 1}_k$ denote the $k\times 1$ column of 1's. We can connect this to forbidden families as follows. We note that $A\in{\mathrm{Avoid}}(m,{\bf 1}_3)$ consists of at most $m+1$ the columns of column sum 0 or 1 and $A$ may have columns of sum 2. The columns of sum 2  can be interpreted as a vertex-edge incidence matrix  of a graph.  For a graph $H$, let ${\hbox{Inc}}(H)$ denote its vertex-edge incidence matrix. We deduce the following.

 \begin{lemma}We have that ${\hbox{forb}}(m,\{{\bf 1}_3,{\hbox{Inc}}(H)\})={\hbox{ex}}(m,H)+m+1$.\label{extendgraph}\end{lemma}

 Two sample results concerning ${\hbox{ex}}(m,H)$ yield the following where the vertex-edge incidence matrix of the cycle of length $k$ is $C_k$.

 \begin{thm}\cite{KST} We have that ${\hbox{forb}}(m,\{{\bf 1}_3,C_4\})$ is $\Theta(m^{3/2})$.\label{C4}\end{thm}

  \begin{thm}\cite{BS} We have that ${\hbox{forb}}(m,\{{\bf 1}_3,C_6\})$ is $\Theta(m^{4/3})$.\label{C6}\end{thm}

   Simonovits refers to an unpublished upper bound of Erd\H{o}s as the `Even Circuit Theorem' so the origins of the results are partly folklore.
   \corf{grand} is failing spectacularly on these examples ($X(\{{\bf 1}_3,C_4\})=X(\{{\bf 1}_3,C_6\})=2$) and also on the following example. You might note that $I_2\times I_2$ is the same as $C_4$ after a row and column permutation.

  \begin{thm}\cite{AKRS} We have that ${\hbox{forb}}(m,\{I_2\times I_2, T_2\times T_2\})$ is $\Theta(m^{3/2})$.\label{unusual}\end{thm}

Balogh and Bollob\'as proved the following useful bound which is consistent with \corf{grand}. For fixed $k$, we have $X(\{I_k,I_k^c,T_k\})=1$ since all 1-fold products contain some element of $\{I_k,I_k^c,T_k\}$.
.
\begin{thm} \cite{BB} Let $k$ be given. Then there is a constant {$c_k$} so that
${\hbox{forb}}(m,\{I_k,I_k^c,T_k\})={c_k}$.\label{constant}\end{thm}

 The following lemma is straightforward and  quite useful.

\begin{lemma} Let ${\cal F}=\{F_1,F_2,\ldots ,F_k\}$ and ${\cal G}=\{G_1,G_2,\ldots , G_{\ell}\}$. Assume  that for every $G_i$, there is some $F_j$ with $F_j\prec G_i$.
Then ${\hbox{forb}}(m,{\cal F})\le {\hbox{forb}}(m,{\cal G})$.
\label{FinG}\end{lemma}

\noindent{\bf Proof: } Assume $\ncols{A}>{\hbox{forb}}(m,{\cal G})$. Then for some $i\in [t]$, $G_i\prec A$. But by hypothesis there is some $F_j\in{\cal F}$ with $F_j\prec G_i$. But then
$F_i\prec A$, verifying that ${\hbox{forb}}(m,{\cal F})\le {\hbox{forb}}(m,{\cal G})$. \hskip 20pt{\vrule height7pt width6pt depth0pt}\hfil
\vskip 5pt
Now combining with \trf{constant}, we obtain a surprising  classification.

\begin{thm} Let ${\cal F}=\{F_1,F_2,\ldots ,F_t\}$ be given. There are two possibilities. Either ${\hbox{forb}}(m,{\cal F})$ is $\Omega(m)$ or there exist
$\ell,i,j,k$  with $F_i\prec I_{\ell}$,  with $F_j\prec I_{\ell}^c$ and  with $F_k\prec T_{\ell}$ in which case  there is a constant $c$ with ${\hbox{forb}}(m,{\cal F})= c$.\label{classify}\end{thm}

\noindent{\bf Proof: }  Let $F_i$ be $a_i\times {b}_i$ and let $\ell=\max_{i\in [t]}(a_i+{b}_i)$. Let ${\cal G}=\{I_{\ell},I_{\ell}^c,T_{\ell}\}$. Then $F_j\nprec I_{\ell}$ implies
$F_j\not\prec I_m$ for any $m\ge {\ell}$. Thus if $F_j\nprec I_{\ell}$ for $j=1,2,\ldots t$, then ${\hbox{forb}}(m,{\cal F})$ is $\Omega(m)$ using the construction  $I_m$. The same holds for $I^c$ and $T$.
 \hskip 20pt{\vrule height7pt width6pt depth0pt}\hfil

\vskip 10pt
This paper considers all pairs of forbidden configurations drawn from \tbrf{tab:minquad}. The listed nine configurations are  \emph{minimal quadratic} configurations, namely those $Q$ for which ${\hbox{forb}}(m,Q)$ is $\Theta(m^2)$ yet for any submatrix $Q'$ of $Q$, where $Q'\ne Q$, has ${\hbox{forb}}(m,Q')$ being $O(m)$.   The minimal quadratic configurations of \tbrf{tab:minquad} have the virtue of having few possible 2-fold constructions avoiding them and so avoiding the configurations in pairs (or larger families) results in interesting interactions. \tbrf{tab:minquad} lists all the product constructions that yield the quadratic lower bounds which you can use this to compute $X(\{Q_i,Q_j\})$ for pairs $Q_i,Q_j$ in the table. The asymptotic growth rates of ${\hbox{forb}}(m,\{Q_i,Q_j\})$ are collected together in \tbrf{tab:bounds} and the complete  analysis for any non-empty ${\cal F}\subset\{Q_1,Q_2,\ldots ,Q_9\}$ is in \trf{anysubset}. \srf{mainbds} handles those pairs with $X(\{Q_i,Q_j\})=3$ for which it is immediate that ${\hbox{forb}}(m,\{Q_i,Q_j\})$ is $\Theta(m^2)$. Also we consider those cases where \lrf{FinG} when applied with \trf{constant} yield that ${\hbox{forb}}(m,\{Q_i,Q_j\})$ is $O(1)$.
\srf{graphtheory} considers how to apply \lrf{extendgraph} more generally to help with ${\hbox{forb}}(m,\{Q_5,Q_j\})$. \srf{SI} provides a new standard induction introduced in \cite{AL} that is useful in this context and helps with ${\hbox{forb}}(m,\{Q_8,Q_j\})$ and  ${\hbox{forb}}(m,\{Q_3,Q_j\})$. \srf{structure} considers the structures that arise from forbidding $Q_9$ and then uses this to obtain results on
${\hbox{forb}}(m,\{Q_9,Q_j\})$.

\begin{table}
\begin{tabular}[c]{|c|c|c|p{3cm}|p{2cm}|}
  \hline
   & Configuration $Q_i$ &  ${\hbox{forb}}(m,Q_i)$ & Construction(s) & Reference \\ \hline
  $Q_1$ & $\left[
             \begin{array}{cc}
               0 & 0 \\
               0 & 0 \\
             \end{array}
           \right]
  $ &   $\binom{m}{2} + \binom{m}{1} + \binom{m}{0}$ & $I^c \times I^c$ & \cite{G} \\ \hline
  $Q_2$ & $\left[\begin{array}{cc}
                                             1 & 1 \\
                                             1 & 1
                                           \end{array}
  \right]$ &  $\binom{m}{2} + \binom{m}{1} + \binom{m}{0}$ & $I \times I$ & \cite{G} \\ \hline
  $Q_3$ & $\left[\begin{array}{cccccc}
                       0 & 0 & 0 & 1 & 1 & 1 \\
                       0 & 1 & 1 & 0 & 0 & 1
                     \end{array}
  \right]$ &  $\lfloor\frac{m^2}{4}\rfloor + m + 1$ & $I \times I^c$ & \cite{AFS01} \\ \hline
  $Q_4$ & $\left[ \begin{array}{c}
             0 \\
             0 \\
             0
           \end{array} \right]
  $ &  $\binom{m}{2} + \binom{m}{1} + \binom{m}{0}$ & $I^c \times I^c$ & \cite{Sauer, PS, VC} \\ \hline
  $Q_5$ & $\left[ \begin{array}{c} 1 \\ 1 \\ 1 \end{array}\right]$ &  $\binom{m}{2} + \binom{m}{1} + \binom{m}{0}$ & $I \times I$ & \cite{Sauer, PS, VC} \\ \hline
  $Q_6$ & $\left[\begin{array}{ccc}
           1 & 0 & 0 \\
           0 & 1 & 0 \\
           0 & 0 & 1
         \end{array}
 \right]$ & $\binom{m}{2} + \binom{m}{1} + \binom{m}{0}$ & $\begin{matrix}I^c \times I^c\\ I^c \times T\\ T \times T\\ \end{matrix}$ & \cite{ryser72} \\ \hline
  $Q_7$ & $\left[\begin{array}{ccc}
                        0 & 1 & 1 \\
                        1 & 0 & 1 \\
                        1 & 1 & 0
                      \end{array}
  \right]$ &  $\binom{m}{2} + \binom{m}{1} + \binom{m}{0}$ & $\begin{matrix}I \times I\\ I \times T\\ T \times T\\ \end{matrix}$ & \cite{ryser72} \\ \hline
  $Q_8$ & $\left[\begin{array}{cccc}
                        1 & 0 & 1 & 0 \\
                        0 & 1 & 0 & 1 \\
                        0 & 0 & 1 & 1
                      \end{array}
   \right]$ &  $\lfloor \frac{m^2}{4} \rfloor + m + 1$ & $T \times T$  & \cite{survey} \\ \hline
  $Q_9$ & $\left[\begin{array}{cc} 1 & 0 \\ 1& 0 \\ 0 & 1 \\ 0 & 1 \end{array} \right]$ &
   $\binom{m}{2} + 2m - 1$ & $I \times T$ \newline $I^c \times T$  & \cite{FFP87}  \\
  \hline
\end{tabular}
\caption{Minimal Quadratic Configurations}
\label{tab:minquad}
\end{table}

 \begin{table}
\begin{tabular}[c]{|c|c|c|c|c|c|c|c|c|}
\hline
&$Q_2$&$Q_3$&$Q_4$&$Q_5$&$Q_6$&$Q_7$&$Q_8$&$Q_9$\\
\hline
$Q_1$&$\begin{matrix}\Theta(1)\\ \hbox{Th}~\ref{constantbd}\\ \end{matrix}$&$\begin{matrix}\Theta(m)\\ \hbox{Cor~\ref{orderbd}}\\ \end{matrix}$
&$\begin{matrix}\Theta(m^2)\\ \hbox{Th}~\ref{IxI}\\ \end{matrix}$
&$\begin{matrix}\Theta(1)\\ \hbox{Th}~\ref{constantbd}\\ \end{matrix}$&$\begin{matrix}\Theta(m^2)\\ \hbox{Th~\ref{IxI}}\\ \end{matrix}$&
$\begin{matrix}\Theta(1)\\ \hbox{Th}~\ref{constantbd}\\ \end{matrix}$
&$\begin{matrix}\Theta(m)\\ \hbox{Cor~\ref{F1F8,F2F8}}\\ \end{matrix}$&$\begin{matrix}\Theta(m)\\ \hbox{Cor~\ref{Q9}}\\ \end{matrix}$\\
\hline
$Q_2$&&$\begin{matrix}\Theta(m)\\ \hbox{Cor~\ref{orderbd}}\\ \end{matrix}$&$\begin{matrix}\Theta(1)\\ \hbox{Th}~\ref{constantbd}\\ \end{matrix}$
&$\begin{matrix}\Theta(m^2)\\ \hbox{Th}~\ref{IxI}\\ \end{matrix}$
&$\begin{matrix}\Theta(1)\\ \hbox{Th}~\ref{constantbd}\\ \end{matrix}$&$\begin{matrix}\Theta(m^2)\\ \hbox{Th}~\ref{IxI}\\ \end{matrix}$
&$\begin{matrix}\Theta(m)\\ \hbox{Cor~\ref{F1F8,F2F8}}\\ \end{matrix}$&$\begin{matrix}\Theta(m)\\ \hbox{Cor~\ref{Q9}}\\ \end{matrix}$\\
\hline
$Q_3$&&&$\begin{matrix}\Theta(m)\\ \hbox{Th~\ref{graphbd}}\\ \end{matrix}$&$\begin{matrix}\Theta(m)\\ \hbox{Th~\ref{graphbd}}\\ \end{matrix}$
&$\begin{matrix}\Theta(m)\\ \hbox{Cor~\ref{orderbd}}\\ \end{matrix}$&$\begin{matrix}\Theta(m)\\ \hbox{Cor~\ref{orderbd}}\\ \end{matrix}$
&$\begin{matrix}\Theta(m)\\ \hbox{Cor~\ref{Q3Q8}}\\ \end{matrix}$&$\begin{matrix}\Theta(m)\\ \hbox{Cor~\ref{Q9}}\\ \end{matrix}$\\
\hline
$Q_4$&&&&$\begin{matrix}\Theta(1)\\ \hbox{Th}~\ref{constantbd}\\ \end{matrix}$&$\begin{matrix}\Theta(m^2)\\ \hbox{Th}~\ref{IxI}\\ \end{matrix}$
&$\begin{matrix}\Theta(1)\\ \hbox{Th}~\ref{constantbd}\\ \end{matrix}$&$\begin{matrix}\Theta(m)\\ \hbox{Th~\ref{graphbd}}\\ \end{matrix}$
&$\begin{matrix}\Theta(m)\\ \hbox{Th~\ref{graphbd}}\\ \end{matrix}$\\
\hline
$Q_5$&&&&&$\begin{matrix}\Theta(1)\\ \hbox{Th}~\ref{constantbd}\\ \end{matrix}$&$\begin{matrix}\Theta(m^2)\\ \hbox{Th}~\ref{IxI}\\ \end{matrix}$
&$\begin{matrix}\Theta(m)\\ \hbox{Th~\ref{graphbd}}\\ \end{matrix}$&$\begin{matrix}\Theta(m)\\ \hbox{Th~\ref{graphbd}}\\ \end{matrix}$\\
\hline
$Q_6$&&&&&&$\begin{matrix}\Theta(m^2)\\ \hbox{Th}~\ref{TxT}\\ \end{matrix}$&$\begin{matrix}\Theta(m^2)\\ \hbox{Th}~\ref{TxT}\\ \end{matrix}$
&$\begin{matrix}\Theta(m^2)\\ \hbox{Th}~\ref{IxT}\\ \end{matrix}$\\
\hline
$Q_7$&&&&&&&$\begin{matrix}\Theta(m^2)\\ \hbox{Th}~\ref{TxT}\\ \end{matrix}$&$\begin{matrix}\Theta(m^2)\\ \hbox{Th}~\ref{IxT}\\ \end{matrix}$\\
\hline
$Q_8$&&&&&&&&$\begin{matrix}\Theta(m)\\ \hbox{Th~\ref{Q8Q9}}\\ \end{matrix}$\\
\hline

\end{tabular}
\caption{Asymptotic growth rates of ${\hbox{forb}}(m,\{Q_i,Q_j\})$.}
\label{tab:bounds}
\end{table}

\section{Quadratic and Constant Bounds}\label{mainbds}

 First we are interested in pairs with $X(\{Q_i,Q_j\})=3$ for which it follows that
 \hfil\break${\hbox{forb}}(m,\{Q_i,Q_j\})$ is $\Theta(m^2)$ (the upper bound follows from \lrf{FsubsetG} using that
  \hfil\break${\hbox{forb}}(m,\{Q_i\})$ is $O(m^2)$ for all $i\in [9]$).

\begin{thm} We have that ${\hbox{forb}}(m,\{Q_1,Q_4,Q_6\})={\hbox{forb}}(m,\{Q_2,Q_5,Q_7\})$ is $\Theta(m^2)$.\label{IxI}\end{thm}
\noindent{\bf Proof: } We use the construction $I_{m/2}^c\times I_{m/2}^c\in{\mathrm{Avoid}}(m,\{Q_1,Q_4,Q_6\})$ to deduce that
$X(\{Q_1,Q_4,Q_6\})=3$ and $I_{m/2}\times I_{m/2}\in{\mathrm{Avoid}}(m,\{Q_2,Q_5,Q_7\})$
yields
$X(\{Q_2,Q_5,Q_7\})=3$. \hskip 20pt{\vrule height7pt width6pt depth0pt}\hfil

\begin{thm} We have that ${\hbox{forb}}(m,\{Q_6,Q_7,Q_8\})$ is $\Theta(m^2)$.\label{TxT}\end{thm}
\noindent{\bf Proof: } The construction $T_{m/2}\times T_{m/2}\in{\mathrm{Avoid}}(m,\{Q_6,Q_7,Q_8\})$ shows that \hfil\break
$X(\{Q_6,Q_7,Q_8\})=3$. \hskip 20pt{\vrule height7pt width6pt depth0pt}\hfil

\begin{thm} We have that ${\hbox{forb}}(m,\{Q_6,Q_9\})$ and ${\hbox{forb}}(m,\{Q_7,Q_9\})$ are $\Theta(m^2)$.\label{IxT}\end{thm}
\noindent{\bf Proof: } We use the construction $I_{m/2}^c\times T_{m/2}\in {\mathrm{Avoid}}(m,\{Q_6,Q_9\})$
to deduce that
$X(\{Q_6,Q_9\})=3$
and $I_{m/2}\times T_{m/2}\in {\mathrm{Avoid}}(m,\{Q_7,Q_9\})$ yields $X(\{Q_7,Q_9\})=3$. \hskip 20pt{\vrule height7pt width6pt depth0pt}\hfil

\vskip 10pt
Families ${\cal F}$ for which ${\hbox{forb}}(m,{\cal F})$ is $O(1)$ must arise from applying \lrf{FinG} and  \trf{constant} in view of \trf{classify}.
There are no 2-fold or 1-fold product constructions in common for $Q_1,Q_2$ so that $X(\{Q_1,Q_2\})=1$. We can use \trf{constant} and \lrf{FinG} to get a constant bound but perhaps recording a general result is in order. Let $0_{a,b}$ denote the $a\times b$ matrix of 0's and let $J_{a,b}$ denote the $a\times b$ matrix of 1's.

\begin{thm}  Let $k, \l, p, q$ be given.  Then there exists some constant $c_{k\l pq}$ such that for $m \geq c_{k\l pq}$, we have ${\hbox{forb}}(m, \{0_{k,\l}, J_{p,q}\}) = \l + q - 2$. \label{thm:constant}\end{thm}

\noindent{\bf Proof: } We let $d = \max\{k,\l,p,q\}$.  Then  $0_{k,\l} \prec T_{2d}, 0_{k,\l} \prec I_{2d}$ and $ J_{p,q} \prec I^c_{2d}$.  Thus by \trf{classify},
${\hbox{forb}}(m, \{0_{k,\l}, J_{p,q}\})$ is $O(1)$.
 We wish to show that ${\hbox{forb}}(m, \{0_{k,\l}, J_{p,q}\}) = \l + q - 2$.  Let $B\in{\mathrm{Avoid}}(m, \{0_{k,\l}, J_{p,q}\})$ with $n=\ncols{B}>\l+q-2$. We can delete columns if necessary to obtain a matrix $A\in{\mathrm{Avoid}}(m, \{0_{k,\l}, J_{p,q}\})$ with $n=\ncols{A}=\l+q-1$.
  From \lrf{lem:sum} we know that the right side of \rf{eqn:sum} is constant based on $n, k, \l, p$ and $q$. The right hand side of the inequality in \rf{eqn:sum} is at least $m$ since the summands of the left side will be at least 1 unless  $a_r < \l$ and $b_r < q$ which is impossible  because $a_r + b_r = \l+q-1$.   So for sufficiently large $m$, we have a contradiction. Hence there exists a constant $c_{k\ell pq}$ so that for $m \geq c_{k\l pq}$, we have ${\hbox{forb}}(m, \{0_{k,\l}, J_{p,q}\}) \le \l + q - 2$.

It remains to show we have a construction $A\in{\mathrm{Avoid}}(m,\{0_{k,\l}, J_{p,q}\})$ with $\ncols{A}=\ell+q-2$.   Assume $m=\binom{\ell+q-2}{q-1}+t$ for some $t\ge0$. Let the first $\binom{\ell+q-2}{q-1}$ rows of $A$ consist of all possible rows of $\ell+q-1$ entries with exactly $q-1$ 1's. For the remaining rows of $A$ simply repeat the row of $q-1$ 1's followed by $\ell-1$ 0's $m-\binom{\ell+q-2}{q-1}$ times. The matrix is seen to be simple and cannot have $0_{k,\ell}$ since each row has $\ell-1$ 0's and cannot have $J_{p,q}$ since each row has $q-1$ 1's. Thus  ${\hbox{forb}}(m, \{0_{k,\l}, J_{p,q}\}) \ge q + \l - 2$.  This yields the result.
 \hskip 20pt{\vrule height7pt width6pt depth0pt}\hfil

\begin{lemma} Let $k, \l, p, q$ be given.  Let $A \in {\mathrm{Avoid}}(m, \{0_{k,\l}, J_{p,q}\})$, with $\ncols{A} = n$.  Also let $a_r$ denote the number of 0's in row $r$ of $A$, and $b_r$ the number of 1's in row $r$ so that $a_r + b_r = n$.  Then:
\begin{equation}\sum_{r=1}^m \left(\binom{a_r}{\l}+\binom{b_r}{q}\right) \leq (k-1)\binom{n}{\l} + (p-1)\binom{n}{q}.  \label{eqn:sum}\end{equation}
\label{lem:sum}\end{lemma}

\noindent{\bf Proof: } We consider the columns of $A$.  We take all $\l$-subsets of the columns and call them $0$-buckets.  Similarly, we take all $q$-subsets of the columns as $1$-buckets.  We will have $\binom{n}{\l}$ $0$-buckets and $\binom{n}{q}$ $1$-buckets.  We then process the rows of $A$ one by one, considering all possible $\l$-subsets and $q$-subsets of columns on that row.  If one of these subsets contains all 0's or all 1's, it makes a contribution to the appropriate $0$-bucket or $1$-bucket.  Thus if there are $a$ 0's in a row, and $b$ 1's (where $a + b = n$), then the row will make contributions to $\binom{a}{\l}$ $0$-buckets and $\binom{b}{q}$ $1$-buckets.  The left side of \rf{eqn:sum} is thus the total number of contributions over the rows of $A$.  Each of our $\binom{n}{\l}$ $0$-buckets can have a maximum of $k-1$ contributions, and similarly, our $\binom{n}{q}$ $1$-buckets can have a maximum of $p-1$ contributions, which produces the right side of the inequality.
 \hskip 20pt{\vrule height7pt width6pt depth0pt}\hfil
\vskip 5pt

\begin{thm} We have that ${\hbox{forb}}(m,\{Q_1,Q_2\})$, ${\hbox{forb}}(m,\{Q_1,Q_5\})$, ${\hbox{forb}}(m,\{Q_1,Q_7\})$,\hfil\break ${\hbox{forb}}(m,\{Q_2,Q_4\})$, ${\hbox{forb}}(m,\{Q_2,Q_6\})$, ${\hbox{forb}}(m,\{Q_4,Q_5\})$, ${\hbox{forb}}(m,\{Q_4,Q_7\})$ and  \hfil\break ${\hbox{forb}}(m,\{Q_5,Q_6\})$
 are all bounded by $O(1)$.\label{constantbd}\end{thm}

\noindent{\bf Proof: }  We apply \lrf{FinG} with ${\cal G}=\{I_4,I_4^c,T_4\}$ and also \trf{constant}. Two examples are the following. For the family $\{Q_1,Q_5\}$ we note that $Q_1\prec I_4$, $Q_5\prec I_4^c$ and $Q_1\prec T_4$. For the family $\{Q_5,Q_6\}$ we note that $Q_6\prec I_4$, $Q_5\prec I_4^c$ and $Q_5\prec T_4$. \hskip 20pt{\vrule height7pt width6pt depth0pt}\hfil

\vskip 10pt
We record below the exact values for ${\hbox{forb}}(m,\{Q_1,Q_2\})$. The function ${\hbox{forb}}(m,\{Q_1,Q_2\})$  has a surprising non-monotonicity in $m$.
\begin{thm} \cite{thesis} We have
$$
{\hbox{forb}} \left(m, \left\{ \left[
              \begin{array}{cc}
                0 & 0 \\
                0 & 0 \\
              \end{array}
            \right], \left[
              \begin{array}{cc}
                1 & 1 \\
                1 & 1 \\
              \end{array}
            \right]
 \right\} \right) = \begin{cases}
  2 & \text{if } m=1 \hbox{ or } m\geq7 \\
  4  & \text{if } m = 2,5,6 \\
  6 & \text{if } m = 3,4
  \end{cases}.
$$
\label{thm:failedmono}\end{thm}

\section{Graph Theory}\label{graphtheory}

We consider a family ${\cal F}=\{{\bf 1}_3, F\}$ for some $F$. Note that $Q_5={\bf 1}_3$.  We have that ${\hbox{forb}}(m,\{{\bf 1}_3,F\})$ is $O(m^2)$ since ${\hbox{forb}}(m,{\bf 1}_3)$ is $O(m^2)$. In this section we consider those $F$ which are (0,1)-matrices with column sums 0,1 or 2.  If $F$ has a repeated column of sum 2 then $2\cdot {\bf 1}_2\prec F$ and then ${\hbox{forb}}(m,\{{\bf 1}_3,F\})$ is $\Theta(m^2)$ (the construction $I_{m/2}\times I_{m/2}$ yields the lower bound).  So we may assume $F$ has no repeated columns of sum 2 and so these columns can be viewed as the incidence matrix of some graph.   We will adapt \lrf{extendgraph} to those $F$ with columns having sum 0,1 or 2.  The following remark describes our construction.

\begin{remark} Let $F$ be a $k\times \ell$  (0,1)-matrix with column sums $\in \{0,1,2\}$. Assume $2\cdot {\bf 1}_2\not\prec F$. Let $a_i$ be the number of columns of $F$ of sum 1 with a 1 in row $i$, and let $b$ be the number of columns of $F$ of all 0's.  We can form a graph $G$ with $V(G)=[k+\sum_{i\in [k]}a_i+b+1]$ as follows. For $i,j\in [k]$ we have $i,j\in E(G)$ if and only if there is a column of $F$ with 1's in rows $i,j$. Also, for each $i\in [k]$, we add $a_i$ edges to $G$ joining $i\in [k]$ to $a_i$ vertices chosen from
$[k+\sum_{i\in [k]}a_i+b+1]\backslash [k]$ (each of which has degree 1). Finally on the remaining $b+1$ vertices we add $b$ edges in the form of a tree. Then $F\prec {\hbox{Inc}}(G)$. \label{adorn}\end{remark}
\noindent{\bf Proof: }  We find $F\prec {\hbox{Inc}}(G)|_{[k]}$.  \hskip 20pt{\vrule height7pt width6pt depth0pt}\hfil

\vskip 10pt
The remark demonstrates some of the differences between a `subgraph' and a `configuration'.

\begin{lemma} Let $T$ be a graph on $k$ vertices and assume $T$ has  no cycles (i.e. a forest). Then ${\hbox{ex}}(m,T)$ is $O(m)$. \label{treebd}\end{lemma}
\noindent{\bf Proof: }  Folklore  says if a graph $G$ on $m$ vertices has at least $km$ edges then $T$ is a subgraph of $G$.  Assume $G$ has at least $km$ edges. We first obtain a subgraph $G'$ of $G$ with minimum degree $k$ which we obtain by removing  vertices whose degree is at most $k-1$. Each vertex deleted removes at most $k-1$ edges. Thus the process must stop with a non-empty subgraph $G'$ of $G$ with minimum degree $k$.  Since $T$ has no cycles, we may order the vertices $v_1,v_2,\ldots, v_k$ of $T$ so that for each $v_i$ there is at most one $v_j$ with $j<i$ such that $(v_j,v_i)$ is an edge of $T$. Assume we have found in $G'$ a subgraph $T$, namely vertices $x_1,x_2,\ldots ,x_p\in V(G')$ such that  $(x_i,x_j)\in E(G')$  if $(v_i,v_j)\in E(T)$ where $1\le i<j\le p$. If $p=k$, we are done. If $p<k$, then consider $v_{p+1}$. If $v_{p+1}$ is not joined in $T$ to anything in $v_1,v_2,\ldots ,v_p$ then we can select $x_{p+1}$ as any  vertex in $G'$ (say adjacent to $x_p$) which has not already been selected.
 If $v_{p+1}$ is joined to $v_i$ with $i\le p$, then we choose $x_{p+1}$ as any vertex adjacent $x_i$ which has not already been selected. We use that minimum degree in $G'$ is at least $k>p$. Continue until $p=k$.  We deduce that ${\hbox{ex}}(m,T)<km$.  \hskip 20pt{\vrule height7pt width6pt depth0pt}\hfil

 \vskip 10pt
 We  extend this to configurations in \trf{graphlinear}.
 \begin{thm} Let $F$ be  a given $k\times \ell$ (0,1)-matrix such that every column has at most 2 1's. Assume that $2\cdot{\bf 1}_2\not\prec F$ and assume $C_t\not\prec F$ for any $t\ge 3$.
 Then ${\hbox{forb}}(m,\{{\bf 1}_3,F\})$ is $O(m)$.\label{graphlinear}\end{thm}

 \noindent{\bf Proof: } Use \remrf{adorn} to obtain a graph $G$ from $F$.  We check that $G$ has no cycles and hence by our above remarks, ${\hbox{ex}}(m,G)$ is $O(m)$.  We note that $F\prec {\hbox{Inc}} (G)$.  Now applying  \lrf{extendgraph} yields
 ${\hbox{forb}}(m,\{{\bf 1}_3,{\hbox{Inc}}(G)\})$ is $O(m)$ and so, by \lrf{FinG},   ${\hbox{forb}}(m,\{{\bf 1}_3,F\})$ is $O(m)$. \hskip 20pt{\vrule height7pt width6pt depth0pt}\hfil

 \vskip 10pt
The following is a weak version of the extremal graph results of Erd\H{o}s, Stone and Simonovits since we only consider asymptotic growth rates.

\begin{thm} Let $F$ be  a given $k\times \ell$ (0,1)-matrix such that every column has at most 2 1's. Let $t$ be given. Assume $2\cdot{\bf 1}_2\prec F$ or there is some $t\ge 1$ with $C_{2t+1}\prec F$.  Then
${\hbox{forb}}(m,\{{\bf 1}_3,F\})$ is $\Theta(m^2)$.\label{oddcycle}\end{thm}

\noindent{\bf Proof: } The upper bound $O(m^2)$ is easy. We may use the construction $I_{m/2}\times I_{m/2}$ to obtain the matching lower bound. \hskip 20pt{\vrule height7pt width6pt depth0pt}\hfil

\vskip 5pt
Let $H$ be a bipartite graph. Then ${\hbox{ex}}(m,H)$ is $o(m^2)$. We use the notation $o(m^2)$ to refer to a function $f(m)$ with
$\lim_{m\to\infty}f(m)/m^2=0$.  The following result extends this to configurations.

\begin{thm} Let $F$ be  a given $k\times \ell$ (0,1)-matrix such that every column has at most 2 1's.
Let $F$ be given with  and also with the property that  $2\cdot{\bf 1}_2\not\prec F$ and for all $t\ge 1$, we have $C_{2t+1}\not\prec F$.  Then
${\hbox{forb}}(m,\{{\bf 1}_3,F\})$ is $o(m^2)$.\end{thm}

\noindent{\bf Proof: } Form a graph $G$ as described in \remrf{adorn}. Since for all $t\ge 1$, we have $C_{2t+1}\not\prec F$, the resulting graph $G$ will be a bipartite graph.  Then for some $s,t$, $G$ is a subgraph of the complete bipartite graph $K_{s,t}$. We know that
${\hbox{ex}}(m,K_{s,t})$ is $o(m^2)$. Thus ${\hbox{ex}}(m,G)$ is  $o(m^2)$. Now $F\prec {\hbox{Inc}}(G)$ and so by \lrf{extendgraph} we have that  ${\hbox{forb}}(m,\{{\bf 1}_3,F\})$ is $o(m^2)$. \hskip 20pt{\vrule height7pt width6pt depth0pt}\hfil

\vskip 5pt
One could imagine trying to obtain similar results for ${\hbox{forb}}(m,\{{\bf 1}_k,F\})$ where $F$ has columns sums at most $k-1$. It is still very much an open problem to determine the exact asymptotic growth ${\hbox{ex}}(m,C_{2t})$ for various $t\ge 2$ with two results noted \trf{C4}, \trf{C6}.   \trf{graphlinear} combined with \remrf{complement}, yields the following.

\begin{thm} We have that ${\hbox{forb}}(m,\{Q_5,Q_3\})$,  ${\hbox{forb}}(m,\{Q_5,Q_8\})$,  ${\hbox{forb}}(m,\{Q_5,Q_9\})$,  \hfil\break
 ${\hbox{forb}}(m,\{Q_4,Q_3\})$, ${\hbox{forb}}(m,\{Q_4,Q_8\})$,
${\hbox{forb}}(m,\{Q_4,Q_9\})$ are all $O(m)$.\label{graphbd}\end{thm}

\trf{oddcycle} yields that ${\hbox{forb}}(m,\{Q_5,Q_7\})$ is $\Omega(m^2)$, a fact which has already been noted.

\section{New Standard Induction}\label{SI}
Our standard induction argument proceeds as follows. Let  $A\in{\mathrm{Avoid}}(m,{\cal F})$ with $\ncols{A}={\hbox{forb}}(m,{\cal F})$. We choose  $r\in [m]$ and delete row $r$ from $A$. The result may have repeated columns which we collect in a matrix $C_r$. After permuting rows and columns we have the following:
\begin{E}
A =
\begin{array}{r@{}}
    \hbox{row  }r \\  \\
\end{array}
\begin{bmatrix}
    0 \,0 \cdots  0 & 1\,1  \cdots  1\\
    B_r  \,\, C_r  & C_r  \,\, D_r \\
\end{bmatrix}.
\label{rdecomp}\end{E}
Both $[B_r\,C_r\,D_r]$ and $C_r$ are simple. We have $[B_r\,C_r\,D_r]\in {\mathrm{Avoid}}(m-1,{\cal F})$ suggesting an induction.
Now $[0\,1]\times C_r$ is in $A$. Thus define ${\cal G}$ as the \emph{minimal} set of configurations $F'$ such that $F\prec [0\,1]\times F'$ for some $F\in{\cal F}$ (we defined minimal after \remrf{minimal}). We deduce that $C_r\in{\mathrm{Avoid}}(m-1,{\cal G})$.
This yields the following induction formula
 \begin{E}{\hbox{forb}}(m,F,s)= \ncols{A}=\ncols{[B_rC_rD_r]}+\ncols{C_r}\leq {\hbox{forb}}(m-1,{\cal F})+ {\hbox{forb}}(m-1,{\cal G}).\label{recursion}\end{E}
This means any upper bound on $\ncols{C_r }$ (as a function of $m$) automatically yields an upper bound on $A$ by induction. Thus to show ${\hbox{forb}}(m,{\cal F})$ is $O(m)$ it suffices to show $\ncols{C_r}$ is bounded by a constant.
We have discovered a new standard induction \cite{AL} that, by extending the argument to matrices with multiple columns, yields a more powerful induction formula \rf{newrecursion}.
Let $A$ be an m-rowed (0,1)-matrix (not necessarily simple) and $\alpha$ be an $m\times 1$ column. Let $\mu(\alpha,A)$ denote the multiplicity of column $\alpha$ in $A$.
We say $A$ is $s$-\emph{simple} if every column $\alpha$ of $A$ has $\mu(\alpha,A)\le s$. Let ${\mathrm{Avoid}}(m,{\cal F},s)$ denote the $m$-rowed $s$-simple matrices with no
$F\in{\cal F}$. We define
$${\hbox{forb}}(m,{\cal F},s)=\min_A\{\ncols{A}\,:\,A\in{\mathrm{Avoid}}(m,{\cal F},s)\}.$$
We note that ${\hbox{forb}}(m,{\cal F})\le{\hbox{forb}}(m,{\cal F},s)\le s\cdot{\hbox{forb}}(m,{\cal F})$ and so the asymptotic growth rate of ${\hbox{forb}}(m,{\cal F})$ and ${\hbox{forb}}(m,{\cal F},s)$ are the same (for fixed $s$).  Associate with $A$ the simple matrix ${\hbox{supp}}(A)$ where $\mu(\alpha,{\hbox{supp}}(A))=1$ if and only if $\mu(\alpha,A)\ge 1$.
Given ${\cal F}$, let $t$ be the maximum multiplicity of a column in $F$ over all $F\in{\cal F}$, i.e. each $F\in{\cal F}$ is $t$-simple but some $F\in{\cal F}$ is not $(t-1)$-simple.  We assume for \rf{newrecursion} that some $F\in{\cal F}$ is not simple and so $t\ge 2$.  Define $s=t-1$.  Assume $A\in{\mathrm{Avoid}}(m,{\cal F},s)$. We first decompose $A$ using row $r$ as follows:
$$A =
\begin{array}{r@{}}
    \hbox{row  }r \\  \\
\end{array}
\begin{bmatrix}
    0 \, 0\cdots  0 & 1 \,1 \cdots  1\\
    G&H \\
\end{bmatrix}.
$$
We deduce that $\mu(\alpha,G)\le s$ and $\mu(\alpha,H)\le s$.  We can obtain the following decomposition of $A\in{\mathrm{Avoid}}(m,{\cal F},s)$ based on deleting row $r$ and rearranging by selecting certain columns for $C_r$ so that   if $\mu(\alpha,G)+\mu(\alpha,H)\ge s+1$, then  $\mu(\alpha,C_r)=\min \{\mu(\alpha,G),\mu(\alpha,H)\}$.  We again obtain \rf{rdecomp}.
We conclude that $[B_r\,C_r\, D_r]$ and $C_r$ are both $s$-simple. Thus $\ncols{[B_r\,C_r\, D_r]}\le{\hbox{forb}}(m,{\cal F},s)$.
 Since each column in $C_r$ appears at least $s+1$ times in $[B_rC_rC_rD_r]$, then $C_r$  has no configuration in ${\cal F}'=\{{\hbox{supp}}(F)\,:\,F\in{\cal F}\}$.
 In the case that each  $F\in{\cal F}$ is  simple then  ${\cal F}'={\cal F}$.
 We obtain the following useful inductive formula:
 \begin{E}{\hbox{forb}}(m,F,s)= \ncols{A}=\ncols{[B_rC_rD_r]}+\ncols{C_r}\leq s\cdot\left({\hbox{forb}}(m-1,{\cal F})+ {\hbox{forb}}(m-1,{\cal F}'\cup{\cal G})\right).\label{newrecursion}\end{E}
 The extra value here as compared with \rf{recursion} is in forbidding in $C_r$ the configurations ${\hbox{supp}}(F)$ for each $F\in {\cal F}$.

\begin{thm}\label{F8blockof0's}Let $k,\ell$ be given. Then ${\hbox{forb}}(m,\{Q_8,[0\,1]\times 0_{k,\ell}\})$ is $O(m)$.\end{thm}
\noindent{\bf Proof: } Let $A\in{\mathrm{Avoid}}(m,\{Q_8,[0\,1]\times 0_{k,\ell}\})$.  We apply the decomposition of \rf{rdecomp} and deduce that
$C_r\in{\mathrm{Avoid}}(m-1,\{I_2,0_{k,\ell}\})$. We note that $Q_8=[0\,1]\times I_2$ and deduce that ${\cal G}=\{I_2,0_{k,\ell}\}$. With $I_2\not\prec C_r$, we discover that
$C_r\prec [{\bf 0}_{m-1}|T_{m-1}]$ (i.e. $C_r$ is a selection of columns from the triangular matrix).  Then if $\ncols{C_r}\ge k+\ell$, we find  $0_{k,\ell}\prec C_r$. We deduce that $\ncols{C_r}\le k+\ell-1$ and  deduce by induction on $m$ (using \rf{recursion}) that
${\hbox{forb}}(m,\{Q_8,[0\,1]\times 0_{k,\ell}\})$ is $O(m)$. \hskip 20pt{\vrule height7pt width6pt depth0pt}\hfil

\begin{cor}We have that ${\hbox{forb}}(m,\{Q_1,Q_8\})$, ${\hbox{forb}}(m,\{Q_2,Q_8\})$, ${\hbox{forb}}(m,\{Q_4,Q_8\})$ and ${\hbox{forb}}(m,\{Q_5,Q_8\})$  are  $O(m)$.\label{F1F8,F2F8}\end{cor}

\noindent{\bf Proof: } We note that $Q_1\prec [0\,1]\times 0_{1,2}$ and $Q_4\prec [0\,1]\times 0_{2,1}$.  Also $Q_8^c$ is the same configuration as $Q_8$ and $Q_1^c=Q_2$, $Q_4^c=Q_5$ so we apply \remrf{complement}.   \hskip 20pt{\vrule height7pt width6pt depth0pt}\hfil

\begin{thm}Let $t\ge 2$ be given. Then ${\hbox{forb}}(m,\{Q_8, t\cdot([0\,1]\times [0\,1])\})$ is $O(m)$.\end{thm}
\noindent{\bf Proof: } Let $A\in{\mathrm{Avoid}}(m,\{Q_8,t\cdot([0\,1]\times [0\,1])\})$.  We apply the decomposition obtained as \rf{rdecomp} and deduce that
$C_r\in{\mathrm{Avoid}}(m-1,\{I_2,t\cdot [0\,1]\}$. We note that $Q_8=[0\,1]\times I_2$ and deduce that ${\cal G}=\{I_2,t\cdot [0\,1]\}$.   With $I_2\not\prec C_r$, we have that $C_r\prec [{\bf 0}_{m-1}|T_{m-1}]$.
For $\ncols{C_r}\ge 2t$, we deduce that $t\cdot [0\,1]\prec C_r$. This is a contradiction and so $\ncols{C_r}\le 2t-1$ and  deduce by induction on $m$ (using \rf{recursion}) that   ${\hbox{forb}}(m,\{Q_8, t\cdot([0\,1]\times [0\,1])\})$ is $O(m)$.
 \hskip 20pt{\vrule height7pt width6pt depth0pt}\hfil

\vskip 5pt
We note that $Q_3\prec 2\cdot([0\,1]\times [0\,1])$ and obtain the following.

\begin{cor}We have that ${\hbox{forb}}(m,\{Q_3,Q_8\})$ is $O(m)$.\label{Q3Q8}\end{cor}

We have that $Q_3\not\prec I\times I^c$ and $Q_3$ is a configuration in the other five 2-fold products.
We have that $Q_6\not\prec I^c\times I^c$, $Q_6\not\prec I^c\times T$ and $Q_6\not\prec T\times T$. Also $Q_6$ is a configuration in the other three 2-fold products. 	 We also note that either $T$, $I^c$ are 1-fold products avoiding $Q_3$ and $Q_6$.
Let
$$F_2(1,t,t,1)=\left[\begin{array}{c}0\\ 0\\ \end{array}\right.
\overbrace{
\begin{array}{c}1\,1\cdots 1\\ 0\,0\cdots 0\\ \end{array}
}^t
\overbrace{
\begin{array}{c}0\,0\cdots 0\\ 1\,1\cdots 1\\ \end{array}
}^t
\left.\begin{array}{c}1\\ 1\\ \end{array}\right].$$
We are using notation from \cite{survey}. Thus $Q_3=F_2(1,2,2,1)$. We have that $F_2(1,t,t,1)\not\prec I\times I^c$ and  $F_2(1,t,t,1)$ is a configuration in the other five 2-fold products.   Similarly to $Q_6=I_3$, the configuration $t\cdot I_k$ is not in the $(k-1)$-fold products consisting solely of the terms  $I^c$ and $T$ but is in every 2-fold product using $I$.
Thus we might guess (using \corf{grand})  that forbidding $F_2(1,t,t,1)$ and $t\cdot I_k$  results in a linear bound. This is true.
  The following  is proven using two lemmas.

  \begin{thm}\label{tIkF2(1,t,t,1)} Let $k,t\ge 2$ be given.
 We have that ${\hbox{forb}}(m,\{t\cdot I_k,F_2(1,t,t,1)\})$ is $\Theta(m)$. \end{thm}

 \noindent{\bf Proof: }  We will use induction on $m$. Let $A\in{\mathrm{Avoid}}(m,\{t\cdot I_k,F_2(1,t,t,1)\},t-1)$. We use $s=t-1$ and then for any row $r\in [m]$, obtain the decomposition \rf{rdecomp}.
 We wish to use \rf{newrecursion}.  With ${\cal F}=\{t\cdot I_k,F_2(1,t,t,1)\}$ and $s=t-1$, we have ${\cal F}'=\{I_k,F_2(1,1,1,1)\}$ (since $F_2(1,t,t,1)\prec t\cdot F_2(1,1,1,1)$) and ${\cal G}=\{t\cdot [1\,0], t\cdot [{\bf 0}_{k-1}\,|\,I_{k-1}]\}$ (since $F_2(1,t,t,1)\prec [0\,1]\times (t\cdot [0\,1])$).
 Then $C_r\in{\mathrm{Avoid}}(m,\{I_k,F_2(1,1,1,1),t\cdot [1\,0], t\cdot [{\bf 0}_{k-1}\,|\,I_{k-1}]\},t-1)$.   The second configuration ($F_2(1,1,1,1)$) and the fourth configuration $( t\cdot [{\bf 0}_{k-1}\,|\,I_{k-1}])$ do not get used in our proof.
 We form a digraph on $[m]$ by setting $r\rightarrow s$ if there are at most $t-1$ columns of $A$ with $\linelessfrac{r}{s}\left[\linelessfrac{1}{0}\right]$. If there is a row $s$ of $C_r$ with one 0 and at least $t$ 1's then, by considering the forbidden configuration $F_2(1,t,t,1)$,  we deduce that $r\rightarrow s$ (else $F_2(1,t,t,1)\prec A|_{\{r,s\}}$). Given a row $r$, assume no such row $s$ exists.
 Then all rows of $C_r$ have either at most $t-1$ 1's or is all 1's.

 Assume $\ncols{C_r}\ge tk$. Now remove from $C_r$ any rows of all 1's to obtain a simple matrix $C'$ and obtain a simple matrix $C$ from $C'$ by deleting a column of 0's if it exists. We deduce that each row of $C$ has  at most $t-1$ 1's and each column of $C$ has at least one 1. Also $\ncols{C}\ge tk-1\ge (t-1)k$.  By \lrf{findIk}, we deduce that $C_r$ has $I_k$, a contradiction.  So a row $s$ exists. Since for each row $r\in [m]$ there is some row $s\in [m]$ with
 $r\rightarrow s$, we deduce that there is a directed cycle and we may  apply \lrf{cycleoffalls}  to show that $\ncols{A}$ is $O(m)$. \hskip 20pt{\vrule height7pt width6pt depth0pt}\hfil

 \vskip 10pt
 We have used the following idea before.
\begin{lemma}\label{cycleoffalls} Let $A$ be a simple matrix for which there are $k$ rows $a_1,a_2,\ldots ,a_k$ for which there are at most $t$ columns containing
$\linelessfrac{a_i}{a_{i+1}} \bigl[\linelessfrac{1}{0}\bigr]$ for $i=1,2,\ldots ,k-1$ and also   there are at most $t$ columns containing
$\linelessfrac{a_k}{a_{1}} \bigl[\linelessfrac{1}{0}\bigr]$.
Then we may delete  up to $kt$ columns from $A$ (as described) and the $k-1$ rows $a_1,a_2,\ldots ,a_{k-1}$  and obtain a simple matrix. \end{lemma}

\noindent{\bf Proof: }
Consider the matrix $A'$ obtained from $A$ by deleting the special columns described of which there are at most  $kt$. Then we deduce that $A'|_{\{a_1,a_2,\ldots ,a_k\}}$ consists of columns of all 0's and columns of all 1's.  Now deleting from $A$ the special columns and the  $k-1$ rows  $a_1,a_2,\ldots ,a_{k-1}$ will result in a simple matrix.  \hskip 20pt{\vrule height7pt width6pt depth0pt}\hfil

\begin{lemma} Let $C$ be a matrix having row sums at most $t-1$. Assume each column sum is at least 1. Assume $\ncols{C}\ge (t-1)k$, Then $I_k\prec C$.
\label{findIk}\end{lemma}
\noindent{\bf Proof: } We could phrase this with sets corresponding to the rows.  For row $r$ we form a subset $S_r\subseteq \{1,2,\ldots ,\ncols{C}\}$ with $s\in S_r$ if and only if there is a 1 in row $r$ and column $s$. Our induction is on $k$ with the result being trivial for $k=1$.  We can greedily select sets  $S_1,S_2,\ldots S_p$ so that
$S_j\backslash \left(\cup_{i=1}^{j-1}S_i\right)\ne\emptyset$ for $j\in[p]$ and
so that $\cup_{i=1}^pS_i\ge (t-1)k$.   We begin by choosing an element $a_k\in S_p\backslash \left(\cup_{i=1}^{p-1}S_i\right)\ne\emptyset$. We delete, from our  $p$ sets, the
 elements of $S_p$ (there are at most $t-1$ such elements) and then delete any sets which are now $\emptyset$. We now have sets $S_1',S_2',\ldots S_q'$ so that $S_i'\backslash \cup_{i=1}^{j-1}S_i'\ne\emptyset$ and
so that $\cup_{i=1}^qS_i\ge (t-1)(k-1)$ and $|S_i|\le t-1$. If we form a set-element incidence matrix $C'$ from these $q$ sets, we find that each row sum of $C'$
 is at most $t-1$ ($|S_i'|\le |S_i|\le t-1$). Moreover
each column sum is at least 1 (we deleted columns corresponding to elements of $S_p$) and $\ncols{C}\ge (t-1)(k-1)$  (we only deleted the elements of $S_p$ and $|S_p|\le t-1$). By induction on $k$, $ I_{k-1}\prec C'$. Now the $p$th row of $C$ is 0's on columns not in $S_p$ and in column $a_k$ has 0's on all rows except row $p$ for which it is 1.  Now we find $I_k\prec C$.
 \hskip 20pt{\vrule height7pt width6pt depth0pt}\hfil
\vskip 10pt
\begin{cor}We have that ${\hbox{forb}}(m,\{Q_1,Q_3\})$, ${\hbox{forb}}(m,\{Q_2,Q_3\})$, ${\hbox{forb}}(m,\{Q_3,Q_6\})$ and ${\hbox{forb}}(m,\{Q_3,Q_7\})$ are $O(m)$.\label{orderbd}\end{cor}
\noindent{\bf Proof: } We use \lrf{FinG} with ${\cal G}=\{F(1,t,t,1),t\cdot I_k\}$. For example $Q_1\prec t\cdot I_k$ and $Q_3\prec F(1,t,t,1)$ and also
$Q_6\prec t\cdot I_k$.  We also use \remrf{complement} noting that $\{Q_1^c,Q_3^c\}$ and $\{Q_2,Q_3\}$ are the same as sets of configurations and
$\{Q_3^c,Q_6^c\}$ and $\{Q_3,Q_7\}$ are the same as sets of configurations.  \hskip 20pt{\vrule height7pt width6pt depth0pt}\hfil

\section{Structure that arises from forbidding $Q_9$}\label{structure}

The following result gives some of the structure of matrices $A\in{\mathrm{Avoid}}(m,Q_9)$.
Let $A_k$ denote the  columns of  $A$ of column sum $k$.  We discover that $A_k$ is of one of two types.
 We say $A_k$ is of \emph{type} 1 if there is a partition of the rows
$[m]=X_k\cup Y_k\cup Z_k$ such that all columns in $A_k$ are 1's on rows $X_k$, 0's on rows $Z_k$ and each column of $A_k$ has exactly one 1 in rows $Y_k$
Thus $A_k|_{Y_k}$ is $I_{|Y(k)|}$. In that case, by examining column sums, $|X_k|+1=k$. We say $A_k$ is of \emph{type} 2 if there is a partition of the rows
$[m]=X_k\cup Y_k\cup Z_k$ such that all columns in $A_k$ are 1's on rows $X_k$, 0's on rows $Z_k$ and each column of $A$ has exactly one 0 in rows $Y_k$
Thus $A_k|_{Y_k}$ is $I_{|Y(k)|}^c$. In that case, by examining column sums, $|X_k|+|Y_k|-1=k$.

\begin{lemma}\cite{FFP87} Let $A\in{\mathrm{Avoid}}(m,Q_9)$. Let $A_k$ denote the  columns of column sum $k$. Then $A_k$ is of type 1 or type 2.\label{types}\end{lemma}
\noindent{\bf Proof: }  This follows quite readily by considering the columns of $A_k$ one column at a time. For $\ncols{A_k}\le 2$, the type would not be unique.  \hskip 20pt{\vrule height7pt width6pt depth0pt}\hfil

\vskip 10pt
We consider the following $(t+1)\times (2t+2)$ matrix $F(t)$ whose first two rows coincide with $F_2(1,t,t,1)$:
$$F(t)=\left[\begin{array}{@{}c@{}}\\ \\ \\ \\ \end{array}\right.
\begin{array}{@{}c}0\{\bf 0}\\ \vdots\\ 0\\ \end{array}
\overbrace{\begin{array}{c}1\,1\cdots 1\{\bf 0}\,0\cdots 0\\ \vdots\\ 0\,0\cdots 0\\ \end{array}}^t
\overbrace{\begin{array}{c}0\,0\cdots 0\{\bf 1}\,1\cdots 1\\ \vdots\\ 1\,1\cdots 1\\ \end{array}}^t
\left.\begin{array}{c}1\{\bf 1}\\ \vdots\\ 1\\ \end{array}\right].$$

\begin{lemma} Let $t\ge 1$ be given. Then  ${\hbox{forb}}(m,\{Q_9,F(t)\})$ is $O(m)$.\label{F(t)}\end{lemma}
\noindent{\bf Proof: } Let $A\in{\mathrm{Avoid}}(m,\{Q_9,F(t)\})$. We will show that $\ncols{A}\le (7t+1)m$.
let $A_k$ denote the  columns of column sum $k$.  For $j=1,2$, let $W(j)=\{k\,:\,A_k\hbox{ is of type }j, \ncols{A_k}\ge t+2\}$ and let $V(j)$ be the concatenation of $A_{k}$ for $k\in W(j)$ so that $\ncols{V(j)}=\sum_{k\in W(j)}\ncols{A_k}$.

We first note that for $a<b$ that $|X_a\backslash X_b|\le 1$. This is because if $|X_a\backslash X_b|\ge 2$ and $r,s\in X_a\backslash X_b$ then any column $\alpha$ from $A_a$ has  1's on rows $r,s$. We can choose a column $\beta$ from $A_b$ with  0's  on rows $r,s$ using $r,s\in Y_b\cup Z_b$ and the fact that $\ncols{A_b}\ge t+2$.  But $\beta$ has more 1's than $\alpha$ and so we find $Q_9\prec [\alpha\,|\,\beta]$.

Assume $\ncols{V(1)}\ge 3tm+1$. Then there are $3t$ indices $\{s(1),s(2),\ldots ,s(3t)\}\subseteq W(1)$ where $s(1)<s(2)<\cdots <s(3t)$ so that we can find row $r$ with  $r\in\cap_{i=1}^{3t}Y_{s(i)}$.  We wish to find a set of rows $S$ with $|S|=t$ such that
$S\subseteq X_{s(3t)}\cap\left(\cup_{i=1}^t(Y_{s(i)}\cup Z_{s(i)})\right)$.  We have $|X_{s(3t)}\backslash X_{s(t)}| \ge 2t$.  Using $|X_{s(i)}\backslash X_{s(t)}|\le 1$, we have
$|X_{s(3t)}\backslash \left(\cup_{i=1}^tX_{s(i)}\right)| \ge t$ and so we can find $S$ as claimed.
Now we obtain $F(t)$ as follows. For each $i$ with $1\le i\le t$, we have $r\in Y_{s(i)}$ and $S\subseteq Y_{s(i)}\cup Z_{s(i)}$. We choose one column from $A_{s(1)}$ with a 0 on row $r$ where we choose the column so it also has 0's on rows $S$ (which is possible for  $\ncols{A_{s(i)}}\ge t+2$ (else with $r\cup S=Y_{s(i)}$ we would have difficulty finding the column). We choose one column from each $A_{s(i)}$ for $i\in[t]$, with a 1 on row $r$ and necessarily 0's on rows $S$ and one    All columns from $A_{s(3t)}$ are 1's on rows $S\subseteq X_{s(3t)}$. With $\ncols{A_{s(i)}}\ge t+2$, we can find $t+1$ columns in $A_{s(3t)}$ of which $t$ are 0 on row $r$ and one is 1 on row $r$.   This completes $F(t)$. We conclude that $\ncols{V(1)}\le 3tm$
 Noting that $Q_9^c,F(t)^c$ are the same as $Q_9,F(t)$ when considered as configurations, we deduce that  $\ncols{V(2)}\le 3tm$.
Now $A$ consists of $V(1)$ and $V(2)$ plus at most $(t+1)m$ columns (to account for $\ncols{A_k}$ where $\ncols{A_k}\le t+1$) and so $\ncols{A}\le  (7t+1)m$.  \hskip 20pt{\vrule height7pt width6pt depth0pt}\hfil

\begin{cor}We have that ${\hbox{forb}}(m,\{Q_1,Q_9\})$,  ${\hbox{forb}}(m,\{Q_2,Q_9\})$, ${\hbox{forb}}(m,\{Q_3,Q_9\})$,\break ${\hbox{forb}}(m,\{Q_4,Q_9\})$ and ${\hbox{forb}}(m,\{Q_5,Q_9\})$ are $O(m)$.\label{Q9}\end{cor}
\noindent{\bf Proof: }  We note that $Q_1, Q_2, Q_3, Q_4, Q_5$ are all configurations in $F(2)$.
 \hskip 20pt{\vrule height7pt width6pt depth0pt}\hfil

\begin{thm}We have that ${\hbox{forb}}(m,\{Q_8,Q_9\})$ is $O(m)$.\label{Q8Q9}\end{thm}
\noindent{\bf Proof: }  Let $A\in{\mathrm{Avoid}}(m,\{Q_8,Q_9\})$ and let $A_k$ denote the  columns of column sum $k$. Assume $\ncols{A_k}\ge 3$ for all $k$.
For $j=1,2$, let $W(j,{\hbox{even}})=\{k\,:\,A_k\hbox{ is of type }j, \ncols{A_k}\ge 3, j\hbox{ is }{\hbox{even}}\}$ and let $V(j, {\hbox{even}})$ be the concatenation of $A_{k}$ for $k\in W(j,{\hbox{even}})$.
We similarly define $W(j,{\hbox{odd}})$ and $V(j,{\hbox{odd}})$. This more complicated definition ensures that for $a,b\in W(j,{\hbox{even}})$ (or $a,b\in W(j,{\hbox{odd}})$) with $a<b$  that $a<a+1<b$ (column sums differ by at least 2).

We wish to show $|V(1,{\hbox{even}})|\le 2m$. We establish a number of properties before using an interesting induction.
  We may assume that for $i<j$ and $i,j\in W(1,{\hbox{even}})$, that $|X_i\backslash X_j|\le 1$ else we have a copy of $Q_9$ in $[A_i\,|\,A_j]$ as described in proof of \lrf{F(t)}.

We may assume $|Y_i\cap Y_j|\le 1$ for all pairs $i,j\in W(1,{\hbox{even}})$.  Otherwise assume $|Y_i\cap Y_j|\ge 2$ for some pair $i<j$ with $i,j\in W(1,{\hbox{even}})$. Let $r,s\in Y_i\cap Y_j$. Now $|X_i|<|X_j|$ and so we can choose a third row $p\in X_j\backslash X_i$.
We now find a copy of $Q_8$ in $[A_i\,|\,A_j]$ in rows $p,r,s$, a contradiction

Now assume $|Y_i\cap Y_j|= 1$ for some pair $i<j$.   We claim $X_i\subset X_j$. Otherwise, choose $r\in X_i\backslash X_j$ and $p=Y_i\cap Y_j$. We can find
$\left[\linelessfrac{1}{1}\right]$ in rows $p,r$ of some column of $A_i$ and  $\left[\linelessfrac{0}{0}\right]$ in rows $p,r$ of some column of $A_j$. Give $i<j$ we now have a copy of $Q_9$ in $[A_i\,|\,A_j]$, a contradiction.

Finally assume we have indices
$a,b,c\in W(1)$ with $a<b<c$ and $Y_a\cap Y_c=\{r\}$ and $Y_b\cap Y_c=\{s\}$. Then we conclude $r=s$. If not,
 recall that $X_a\subset X_c$ and $X_b\subset X_c$ and $a<a+1<b<b+1<c$. Now $|X_c\backslash X_b|\ge 2$ and  $|X_{a}\backslash X_b|\le 1$ so we are able choose $p\in X_{c}\backslash (X_{b}\cup X_a)$. Then we find $Q_8$ in rows $p,r,s$ of  $[A_a\,|\,A_b\,|\,A_c]$ by taking two columns of $A_c$ with $I_2$ on rows $r,s$ and 1's on row $p$ and then  one column of $A_b$ with 1 on row $r$ and so 0's on rows $s,p$ and one column of $A_a$ with a 1 on row $s$ and so 0's on rows $r,p$.

   We wish to assert that  $\ncols{V(1,{{\hbox{even}}})}=\sum_{i\in W(1,{\footnotesize {\hbox{even}}}) }|Y_i|\le 2m$. We consider the set system ${\cal Y}$ with sets $Y_i$ for $i\in W(1,{\hbox{even}})$. We set $I=W(1,{\hbox{even}})$ and appeal to \lrf{inductionforY} below to obtain $\sum_{i\in W(1,{\footnotesize {\hbox{even}}})}|Y_i|\le 2m$.

Thus we have shown $|V(1,{\hbox{even}})|\le 2m$. The same will hold for $V(1,{\hbox{odd}})$ since we never use the parity in our argument other than to ensure for $a,b\in W(j,{\hbox{odd}})$ that $|a-b|\ge 2$. Also the same holds for $V(2,{\hbox{even}})$, $V(2,{\hbox{odd}})$ by taking (0,1)-complements. Thus $|V(1,{\hbox{odd}})|\le 2m$, $|V(2,{\hbox{even}})|\le 2m$ and  $|V(2,{\hbox{odd}})|\le 2m$.  Now this has included all columns of $A$ with the exception of $A_k$ for which $|A_k|\le 2$ and hence for at most 2m columns. We now conclude that $A$ has at most $10m$ columns.  \hskip 20pt{\vrule height7pt width6pt depth0pt}\hfil

\begin{lemma}\label{inductionforY} Let $I$ be an ordered set. Let ${\cal Y}=\{Y_i\,:\,i\in I\}$ be a system of distinct sets $Y_i\subseteq [m]$ for $i\in I$. Assume   $|Y_i\cap Y_j|\le 1$ for $i,j\in I$. Assume for all  triples $a,b,c\in I$ with $a<b<c$ with the property that $Y_c\cap Y_b=r$ and $Y_ c\cap Y_a=s$, must have $r=s$.  Then $\sum_{i\in I}|Y_i|\le 2m$.\end{lemma}

\noindent{\bf Proof: } We use induction on $m$ with the result being easy for $m=1$. Let $d$ be the maximum index in $I$.

 Our first case is that $Y_d\cap Y_i=\emptyset$ for $i\in I\backslash d$. We form a new set family ${\cal Y}'={\cal Y}\backslash Y_d$, whose sets are indexed by $I'=I\backslash d$, and whose sets are contained in $[m]\backslash Y_d$. Thus $\sum_{i\in I\backslash d}|Y_i|\le 2(m-|Y_d|)$  (the case $Y_d=\emptyset$ also works this way) and so $\sum_{i\in I}|Y_i|\le 2(m-|Y_d|)+|Y_d|\le 2m$.

 Our second case assumes $Y_d\cap Y_j=\{q\}$ for some $j\in I\backslash d$.
Our properties yield $Y_d\cap Y_i=\emptyset$ or $Y_d\cap Y_i=\{q\}$ for all $i\in I\backslash d$.  Then form a new set family ${\cal Y}'={\cal Y}\backslash Y_d$, whose sets are indexed by $I'=I\backslash d$, and whose sets are contained in $[m]\backslash (Y_d\backslash q)$.  We verify that ${\cal Y}'$ has the desired properties on $m-|Y_d|+1$. We use  that $(Y_d\backslash q)\cap Y_i=\emptyset$ for $i\in I\backslash d$.  By induction  $\sum_{i\in I\backslash d}|Y_i|\le 2(m-|Y_d|+1)$ and so $\sum_{i\in I}|Y_i|\le 2(m-|Y_d|+1)+|Y_d|\le 2m$.
 \hskip 20pt{\vrule height7pt width6pt depth0pt}\hfil

\vskip 10pt
The following result is needed to complete our knowledge of ${\hbox{forb}}(m,{\cal F})$ for ${\cal F}\subset\{Q_1,Q_2,\ldots ,Q_9\}$.

\begin{thm}We have that ${\hbox{forb}}(m,\{Q_6,Q_7,Q_9\})$ is $O(m)$.\label{lasttriple}\end{thm}
\noindent{\bf Proof: } Let $A\in{\mathrm{Avoid}}(m,\{Q_6,Q_7,Q_9\})$. We proceed as above letting  $A_k$ be the columns of sum $k$ and apply \lrf{types}. We deduce that if $A_k$ is of type 1 then $\ncols{A_k}\le 2$ else $Q_6\prec A_k$. Similarly if $A_k$ is of type 2 then $\ncols{A_k}\le 2$ else $Q_7\prec A_k$. Thus $\ncols{A}\le 2m-2$.  \hskip 20pt{\vrule height7pt width6pt depth0pt}\hfil

\begin{thm} Let ${\cal F}\subset\{Q_1,Q_2,\ldots ,Q_9\}$ with ${\cal F}\ne\emptyset$. If ${\cal F}\subseteq \{Q_1,Q_4,Q_6\}$ or if ${\cal F}\subseteq \{Q_2,Q_5,Q_7\}$ or if ${\cal F}\subseteq \{Q_6,Q_7,Q_8\}$
or if ${\cal F}\subseteq\{Q_6,Q_9\}$ or if ${\cal F}\subseteq\{Q_7,Q_9\}$ or if ${\cal F}=Q_3$ then ${\hbox{forb}}(m,{\cal F})$ is $\Theta(m^2)$. In all other cases, ${\hbox{forb}}(m,{\cal F})$ is $O(m)$. In those cases  ${\hbox{forb}}(m,{\cal F})$ is $\Theta(m)$ or $\Theta(1)$ and \trf{classify} will determine the asymptotic growth rate of ${\hbox{forb}}(m,{\cal F})$ as either $\Theta(m)$ or $\Theta(1)$ in those cases where ${\hbox{forb}}(m,{\cal F})$  is $O(m)$.\label{anysubset}\end{thm}

\noindent{\bf Proof: } Given that ${\hbox{forb}}(m,Q_i)$ is $\Theta(m^2)$ for $i\in [9]$, we need only demonstrate that ${\hbox{forb}}(m,{\cal F})$ is $O(m)$ in the other cases.  We can use the results listed in \tbrf{tab:bounds} to identify all pairs $Q_i,Q_j$ with ${\hbox{forb}}(m,\{Q_i,Q_j\})$ being $O(m)$. Consider this as yielding a graph on a vertex set $[9]$. Any subset $S\subset [9]$ which contains one of these pairs has ${\hbox{forb}}(m,\cup_{i\in S}Q_i)$ being $O(m)$ by \remrf{FsubsetG}. For example, any superset of $\{Q_1,Q_4,Q_6\}$ contains a pair $Q_i,Q_j$ with ${\hbox{forb}}(m,\{Q_i,Q_j\})$ being $O(m)$. In particular ${\hbox{forb}}(m,\{Q_1,Q_2\})$, ${\hbox{forb}}(m,\{Q_1,Q_3\})$, ${\hbox{forb}}(m,\{Q_1,Q_5\})$, ${\hbox{forb}}(m,\{Q_1,Q_7\})$, \break ${\hbox{forb}}(m,\{Q_1,Q_8\})$, and ${\hbox{forb}}(m,\{Q_1,Q_9\})$ are all $O(m)$. For example, any superset of  $\{Q_6,Q_9\}$ contains either contains a pair $Q_i,Q_j$ with ${\hbox{forb}}(m,\{Q_i,Q_j\})$ being $O(m)$ or is a triple ${\hbox{forb}}(m,\{Q_i,Q_j,Q_k\})$ with ${\hbox{forb}}(m,\{Q_i,Q_j,Q_k\})$ being $O(m)$.   We have ${\hbox{forb}}(m,\{Q_1,Q_9\})$, ${\hbox{forb}}(m,\{Q_2,Q_6\})$,
${\hbox{forb}}(m,\{Q_3,Q_6\})$, ${\hbox{forb}}(m,\{Q_4,Q_9\})$, \break${\hbox{forb}}(m,\{Q_5,Q_6\})$, and ${\hbox{forb}}(m,\{Q_8,Q_9\})$ are all $O(m)$. We have two exceptional pairs $\{Q_6,Q_7\}$ and $\{Q_7,Q_9\}$ but we have the  triple $\{Q_6,Q_7,Q_9\}$ for which \hfil\break${\hbox{forb}}(m,\{Q_6,Q_7,Q_9\})$ is $O(m)$ by \trf{lasttriple}.
 \hskip 20pt{\vrule height7pt width6pt depth0pt}\hfil

\vskip 10pt
We may summarize our investigations by saying the \corf{grand} when applied to a forbidden family predicts the correct asymptotic growth for a number of elementary cases. Perhaps the cases where \corf{grand} doesn't correctly predict the   asymptotic growth, such as  \trf{unusual}, are rare. It is premature to conjecture an analog of \corf{grand} for forbidden families.


\section{Introduction and overview of main results}

In many cases, Coulomb interactions in many-electron systems can
be accounted for by perturbation theory~\cite{giu05}. This is usually
possible at sufficiently high densities where the single-particle
(kinetic-energy or band-dispersion) contribution to the ground-state
energy dominates. In lowest order, interactions give rise to the Hartree
and exchange-interaction terms. The Hartree term embodies the purely
electrostatic Coulomb potential energy of the electrons. In a uniform
system, the Hartree contribution is cancelled by the neutralizing
background of ionic charges in the solid. What remains is the exchange
term, which we focus on in this work.

Since their experimental realization, quantum-confined systems have
become attractive laboratories for the study of interacting
electrons because interaction effects are enhanced in low spatial
dimensions~\cite{giu05}. Examples include the exchange enhancement
of parameters such as spin susceptibility and effective mass in
quasi-two-dimensional (quasi-2D) conduction-band electron
systems~\cite{smi72, tan89, att02}. Curiously, experiments on
similarly confined \emph{valence-band} (hole) states seem to
indicate the absence of exchange-related renormalizations of
electronic parameters~\cite{pin86, win05a, chi11}. Here we reveal a
possible origin of this suppression of interaction effects in
quasi-2D hole systems: the high effective spin associated with
valence-band states. Peculiar Coulombic effects arising from the
spin-3/2 character of holes have previously been noted for bulk
semiconductors. \cite{com72, sch06, sch11, kyr11} More recent
theoretical studies have focused also on quasi-2D hole gases.
\cite{sch94, che01, ker10, ker13, sch13} Our results provide new
insight into the effect of valence-band mixing on physical
properties of confined holes, and the formalism developed here can
also form the basis for further detailed studies of interaction
phenomena in experimentally realized quasi-2D hole systems.

The multi-band envelope function approach to electron states in
crystalline solids implies that eigenstates are (in principle,
infinite-dimensional) spinors~\cite{yu10} which affect the matrix
elements describing physical processes in important ways. For an
$n$-fold degenerate band, we may often restrict ourselves to $n$
spinors. The states in the lowest conduction band are usually
non-degenerate, except for spin, so that the spinor structure may
often be ignored. A nontrivial example are hole states in the
topmost valence band of common semiconductors such as Si, Ge, GaAs,
InAs, and CdTe. The \emph{bulk} valence band in these materials is
four-fold degenerate at the band edge, corresponding to an effective
spin 3/2. Away from the band edge, the dispersion splits into the
doubly degenerate heavy-hole (HH) and light-hole (LH) bands. In
quasi-2D systems, the quantum-well confinement results in an energy
splitting between HH and LH bands such that the subbands are
only two-fold degenerate, even at the subband edge with in-plane
wave vector $|\kk|\equiv k=0$. Nevertheless, states in these
subbands need to be described by four-spinors and, except at $k=0$,
these are never pure HHs or LHs. Figure~\ref{fig:Dispersions} shows
the subbands obtained for a hard-wall confinement of holes within
the axial approximation for three semiconductor materials. The
nontrivial physics arises due to the fact that the degeneracy of the
subbands at any fixed value of energy and wave vector $\kk$ is lower
than the number of spinors needed to describe the dynamics of the
Bloch waves. Similar physics applies also to, e.g., 2D electron
systems with Rashba spin-orbit (SO) coupling.~\cite{ras60, byc84,
win03} However, it was found that the exchange energy of such
systems deviates only marginally from that of a simple 2D electron
gas~\cite{che07, che11a}, while the properties of collective excitations
can be more strongly affected by SO coupling~\cite{aga11}.

\begin{figure*}
\includegraphics[width=0.31 \textwidth]{Fig1a}\hfill
\includegraphics[width=0.31 \textwidth]{Fig1b}\hfill
\includegraphics[width=0.31 \textwidth]{Fig1c}
\caption{\label{fig:Dispersions} Lowest (doubly degenerate) subbands
of 2D hole systems realized by a hard-wall confinement of width $d$,
for (a) GaAs, (b) InAs, and (c) CdTe. $E_0 =\pi^2\hbar^2/ (2m_0d^2)$
is the appropriate size-quantization energy scale. Gray lines
delimit the range of energies and wave vectors for which only the
lowest subband is occupied, which is the regime we focus on in this
work.}
\end{figure*}

\begin{figure}[b]
\includegraphics[width=0.8 \columnwidth]{Fig2}
\caption{\label{fig:Reduction2} Exchange energy per particle
$E_\mathrm{X}/N$ for a hard-wall-confined quasi-2D hole system in
GaAs (solid red curve), InAs (dash-dotted red curve), and CdTe
(dotted red curve). $C \equiv e^2/(4\pi\epsilon\epsilon_0)$ is the
Coulomb-interaction constant, $k_\rho$ denotes the Fermi wave
vector, and $d$ is the quantum-well width. The blue dashed curve
shows the result (\ref{eq:Xfinwidth}) based on the EMA. The orange
dashed curve is $E_\mathrm{X}/N$ for a spin-3/2 hole system
described by a multi-spinor wave function with equal amplitudes for
the heavy-hole and light-hole components.}
\end{figure}

As a reference for our discussion below, we briefly review the
textbook problem~\cite{giu05} of the exchange energy per particle
for a 2D electron gas with zero thickness perpendicular to the
2D plane, giving~\cite{cha71, ste73, giu05}
\begin{equation}\label{eq:Xideal}
\frac{E_\mathrm{X}^{(0)}}{N} = - \frac{4 C}{3\pi}\, k_\rho \equiv
- \frac{4}{3}\, \sqrt{\frac{2}{\pi}} \; C\,  \sqrt{\rho} =:
\varepsilon_\mathrm{X} \quad .
\end{equation}
Here $N$ is the number of electrons, $C \equiv e^2/(4\pi\epsilon
\epsilon_0)$ is the Coulomb-interaction constant, $\rho$ is the
electron sheet density, and $k_\rho=\sqrt{2\pi\rho}$ denotes the
Fermi wave vector. This result is based on the following
assumptions. (i) The in-plane orbital motion is fully characterized
by plane waves. (ii) We have a two-fold spin degeneracy of the
energy eigenstates, implying that all energy eigenstates can
simultaneously be chosen as eigenstates of spin projection on a
fixed axis. The latter manifests itself in the fact that only
interactions between particles with the same spin projections
contribute to the exchange energy. We emphasize these well-known
points because we find below that these assumptions are not
applicable for quasi-2D hole systems.

Using the same assumptions (i) and (ii) above, one can evaluate the
exchange energy for a \emph{quasi}-2D electron gas in the lowest subband
of a quantum well with hard-wall confinement. Here, $E_\mathrm{X}$
depends also on the well width $d$ and can be written as~\cite{bet94, bet96}
\begin{equation}\label{eq:Xfinwidth}
  \frac{E_\mathrm{X}^{(\mathrm{EMA})}}{N}
  = \varepsilon_\mathrm{X}\,
  \Lambda^{\mathrm{(\mathrm{EMA})}} ( k_\rho d ) \quad .
\end{equation}
The universal function $\Lambda^\mathrm{(\mathrm{EMA})}
(k_\rho d)$ was expressed in Ref.~\onlinecite{bet96} in terms
of a Taylor expansion in its argument. In the following, we will
refer to Eq.\ (\ref{eq:Xfinwidth}) as the effective-mass
approximation (EMA) to the exchange energy. We note that the
exchange energy in quasi-2D systems is generally reduced with
increasing quantum-well width $d$.

Frequently the exchange energy is expressed in terms of the
dimensionless density parameter $r_s$, which in 2D is the ratio
between the Coulomb energy $C\sqrt{\pi\rho}$ and the kinetic energy
$\pi\rho \, \hbar^2/m^\ast$, assuming a \emph{parabolic} dispersion
$E_\kk = \hbar^2k^2/(2m^\ast)$ with effective mass $m^\ast$. In the
current work, we avoid using the parameter $r_s = m^\ast C /
(\hbar^2\sqrt{\pi\rho})$, the reason being that the systems we study
here do not have a simple parabolic energy dispersion.

\begin{figure}[b]
\includegraphics[width= 0.8 \columnwidth]{Fig3}
\caption{\label{fig:HHcont}
Heavy-hole (HH) character of states at the Fermi energy in the
lowest subband, as measured by $C_\mathrm{HH}$, which is the
combined integrated probability density of the HH entries in the
confined-hole spinor wave function. (See text for details.)}
\end{figure}

Using the numerically calculated multi-spinor envelope functions for
quasi-2D hole systems, we evaluate their exchange energy and find it
to deviate from the EMA expression (\ref{eq:Xfinwidth}). As
Fig.~\ref{fig:Reduction2} shows, the EMA behavior is exhibited in
the low-density, small-width limit where the system's states are
essentially HH-like~\cite{win03}. However, at larger densities, even
with still only the lowest quasi-2D subband occupied, the character
of the wave functions becomes mixed, with eventually the HH and LH
components having almost equal weight (see Fig.~\ref{fig:HHcont} and
Ref.~\onlinecite{win03}). The exchange energy turns out to be
suppressed compared to the EMA value as soon as the contributions
from LH components become significant. This can be seen from
Fig.~\ref{fig:HHcont} in conjunction with Fig.~\ref{fig:Reduction2}.
We obtain good agreement between the asymptotic behavior of
$E_\mathrm{X}$ at large densities and an analytical expression
obtained within a simplified model with equally distributed HH and
LH amplitudes. This supports our hypothesis that the suppression of
exchange effects in quasi-2D hole systems arises as a consequence of
valence-band mixing.

In the remainder of this paper, we provide details of the
calculations and further information to illustrate our conclusions. The
basic formalism for calculating the exchange energy of quasi-2D
systems is described in Sec.~\ref{sec:formalism}. In
Sec.~\ref{sec:2Delectrons}, we review known results for quasi-2D
spin-1/2 electron systems that provide a benchmark for comparison
with analogous hole systems. The formalism for calculating the
exchange energy of spin-3/2 quasi-2D hole systems and a discussion
of the obtained results are given in Sec.~\ref{sec:2Dholes}. The
conclusions of our work are summarized in the final Sec.~\ref{sec:conc}.

\section{Exchange energy of quasi-2D systems}
\label{sec:formalism}

\subsection{General formalism}

In its most general form, the many-body Hamiltonian of interacting
band electrons reads
\begin{eqnarray}
  \mathcal{H}& = &\sum_{n, \kk} E_{n\kk}~\hat{c}_{n\kk}^\dagger \hat{c}_{n\kk}
  + \frac{1}{2 A} \sum_{n_i, \kk, \kk', \qq\ne 0} \hspace{-0.5em}
  V^{n_1 n_2}_{n_3 n_4}(\kk, \kk', \qq)
  \nonumber \\ && \hspace{2cm} {} \times
  \hat{c}_{n_1\kk+\qq}^\dagger \hat{c}_{n_2\kk'-\qq}^\dagger
  \hat{c}_{n_3\kk'} \hat{c}_{n_4\kk}\quad ,
\end{eqnarray}
where $A$ is the system volume (i.e., area in the 2D case), and the
operators $\hat{c}_{n\kk}$ ($\hat{c}_{n\kk}^\dagger$) annihilate (create)
an electron with wave vector $\kk$. Note that in the presence of
SO interaction the spin quantum number is, by itself, not a
good quantum number. Thus $n$ is a common index for the orbital
motion in a (sub)band and the spin degree of freedom. \cite{win03}
In the following, we focus on the case of a quantum-well-confined
system, hence the indices $n_i$ are labeling quasi-2D subbands and
$\kk \equiv (k_x, k_y)$ is a 2D vector. We use the jellium model and
therefore the $\mathbf{q} =\mathbf{0}$ component of the interaction
is not present, as it cancels with the external potential due to the
homogeneous positive-charge background that ensures charge
neutrality. Treating the interaction part of the Hamiltonian in
first-order perturbation theory gives the following correction to
the expectation value of the energy of the system:
\begin{equation}
  \label{eq:ex-1}
  \begin{array}[b]{@{}>{\displaystyle}r@{}}
    E_\mathrm{X} = -\frac{1}{2 A}
    \sum_{n_i, \kk, \kk', \qq\ne 0} \hspace{-0.6em}
    V^{n_1 n_2}_{n_3 n_4}(\kk, \kk', \qq)
    \; \langle \hat{c}_{n_1\kk+\qq}^\dagger \hat{c}_{n_3\kk'}\rangle_0
    \\ {} \times
    \langle \hat{c}_{n_2\kk'- \qq}^\dagger \hat{c}_{n_4\kk}\rangle_0\, ,
  \end{array}
\end{equation}
where $\langle \dots\rangle_0$ indicates the expectation value with
respect to the equilibrium density matrix of the non-interacting
system. The correction~(\ref{eq:ex-1}) is the exchange contribution
to the energy. We now notice that
\begin{equation}
  \langle \hat{c}_{n_1 \kk_1}^\dagger \hat{c}_{n_2 \kk_2}\rangle_0
  = \delta_{n_1, n_2}\delta_{\kk_1, \kk_2}\, n_{F}(E_{n_1 \kk_1}),
\end{equation}
where $n_F(E)$ is the Fermi function. Transforming the sums over
wave vectors into integrals and using the relation above, the
exchange energy reads
\begin{eqnarray}
  \label{eq:ex}
  E_\mathrm{X} &=& -\frac{A}{2} \sum_{n, n'}
  \int \! \frac{d^2k}{(2\pi)^2} \int \! \frac{d^2 k'}{(2\pi)^2}
  \; V^{(nn')}_{\kk \kk'}
  \nonumber \\ && \hspace{3cm} \times\,
  n_{F}(E_{n' \kk'}) \; n_{F}(E_{n \kk}) \quad ,
\end{eqnarray}
where we have introduced the abbreviation $V^{(nn')}_{\kk \kk'}
\equiv V^{n' n}_{n' n}(\kk, \kk', \kk'-\kk)$. As a side remark we
can define the Fock self-energy as
\begin{equation}
  \label{eq:selfenergy}
  \Sigma_{n} (\kk) = \sum_{n'}
  \int \!\frac{d^2 k'}{(2\pi)^2}
  \; V^{(nn')}_{\kk \kk'} \; n_{F}(E_{n' \kk'}).
\end{equation}

The exchange energy, Eq.~(\ref{eq:ex}), is an an extensive quantity.
It is customary to present the exchange energy per particle as a
related intensive quantity ($\rho \equiv N/A$),
\begin{subequations}
\begin{align}\label{eq:xchangepp}
  \frac{E_\mathrm{X}}{N} = &-\frac{1}{2\rho}
  \sum_{n, n'} \int \!\frac{d^2 k}{(2\pi)^2} \int \!\frac{d^2 k'}{(2\pi)^2}
  \; V^{(nn')}_{\kk \kk'}
  \nonumber \\ &\hspace{3cm} \times\,
   n_{F}(E_{n' \kk'}) \; n_{F}(E_{n \kk}) \,\, , \\
  \equiv & -\frac{1}{2\rho}
  \sum_{n} \int \!\frac{d^2 k}{(2\pi)^2} \; \Sigma_n(\kk) \; n_{F}(E_{n \kk})
  \quad .\label{eq:xchangepp1}
\end{align}
\end{subequations}
Finally we notice that, in the zero-temperature limit considered here,
the Fermi function becomes $n_{F}(E) =\Theta(E_F - E)$, where
$\Theta(E)$ is the Heavyside step function and $E_F$ the Fermi
energy. Calculation of the quantities given in
Eqs.~(\ref{eq:selfenergy})--(\ref{eq:xchangepp1}) requires explicit
knowledge of the interaction matrix elements. We now discuss their
most general form for a quasi-2D system.

The eigenfunctions of the multi-band envelope-function Hamiltonian
describing a quasi-2D system take the generic form~\cite{win03}
\begin{equation}\label{eq:EFAgen}
  \psi_{n\kk}(\rr, z) =
  \frac{\ee^{i\kk\cdot\rr}}{2\pi}\, \sum_{\nu}
  \xi_{n \kk}^{(\nu)} (z)\: u_\nu (\rr,z) \quad ,
\end{equation}
where $\rr = (x, y)$ is the coordinate in the 2D plane, $\kk$ the
in-plane wave vector, and $\xi_{n \kk}^{(\nu)} (z)$ denotes the
$\nu$th spinor component of the envelope function for the $n$th
subband in the basis of bulk band-edge Bloch functions $u_\nu
(\rr,z)$. Using the general expression (\ref{eq:EFAgen}) for the
electron states, the Coulomb matrix elements are given by
\begin{equation}\label{eq:CoulombGen}
V^{n_1n_2}_{n_3n_4}(\kk, \kk', \qq)
= \frac{2\pi C}{q} \sum_{\nu, \nu'}
F^{n_1n_2}_{n_3 n_4}(\nu, \nu', \kk, \kk', \qq) \quad ,
\end{equation}
with form factors
\begin{widetext}
\begin{equation}\label{eq:genFF}
  F^{n_1n_2}_{n_3 n_4}(\nu, \nu', \kk, \kk', \qq)
  = \int dz \int dz'  \;\ee^{-q |z-z'|}
  \: \xi^{(\nu)*}_{n_1\kk+\qq}(z)
  \, \xi^{(\nu')*}_{n_2\kk'-\qq}(z')
  \, \xi^{(\nu')}_{n_3 \kk'}(z')
  \, \xi^{(\nu)}_{n_4 \kk}(z)
\end{equation}
that take into account the finite quantum-well width as well as the
spinor structure of quasi-2D states. More specifically, we obtain
for the exchange matrix elements
\begin{subequations}
\label{eq:xgen_me}
\begin{equation}\label{eq:xGen}
  V^{(nn')}_{\kk \kk'} = \frac{2\pi C}{|\kk - \kk'|}
  \sum_{\nu, \nu'} F^{(nn')}_{\kk \kk', \nu\nu'} \quad ,
\end{equation}
with form factors
\begin{equation}\label{eq:xgenFF}
  F^{(nn')}_{\kk \kk', \nu\nu'}
  = \int dz \int dz'  \;\ee^{-|\kk - \kk'| |z-z'|}
  \: \xi^{(\nu)*}_{n' \kk'}(z)
  \, \xi^{(\nu')*}_{n \kk}(z')
  \, \xi^{(\nu')}_{n' \kk'}(z')
  \, \xi^{(\nu)}_{n \kk}(z)\quad .
\end{equation}
\end{subequations}
\end{widetext}
Equation (\ref{eq:xchangepp}) combined with Eqs.\ (\ref{eq:xGen})
and (\ref{eq:xgenFF}) provides the most general expression for the
exchange energy of a quasi-2D many-particle system in a multiband
envelope-function formulation. We would like to make the following
remarks concerning Eq.\ (\ref{eq:xgen_me}). (i) The $z$ ($z'$)
integration probes the overlap between spinor components for the
same spinor index $\nu$ ($\nu'$); in the end we sum over $\nu$ and
$\nu'$. In contrast to the usual textbook case, terms with $\nu$
different from $\nu'$ generally contribute to the exchange energy.
(ii) The exchange matrix elements for quasi-2D systems are
reduced as compared with the corresponding quantities for a
strictly-2D system because $\ee^{-|\kk - \kk'| |z-z'|} < 1$. (iii)
We note the symmetries
\begin{equation}
  \label{eq:form-sym}
  F^{(nn') \, \ast}_{\kk \kk', \nu'\nu} =
  F^{(nn')}_{\kk \kk', \nu\nu'} =
  F^{(n'n)}_{\kk' \kk, \nu'\nu} \quad,
\end{equation}
which have been pointed out in a related context before [see Eq.~(13)
in Ref.~\onlinecite{bet96a}]. The first relation in Eq.\
(\ref{eq:form-sym}) implies that the exchange matrix elements
(\ref{eq:xGen}) are real
\begin{equation}
  V^{(nn')}_{\kk \kk'} = \frac{2\pi C}{|\kk - \kk'|}
  \sum_{\nu, \nu'} \Re F^{(nn')}_{\kk \kk', \nu\nu'} \quad .
\end{equation}
The second relation in Eq.\ (\ref{eq:form-sym}) implies the symmetry
$V^{(nn')}_{\kk \kk'} = V^{(n'n)}_{\kk' \kk}$, which can be useful
to aid efficient numerical computation of Eq.~(\ref{eq:xchangepp}).
(iv) Finally, we point out that the generalized exchange matrix
elements (\ref{eq:xgen_me}) can give interesting physics for a
nontrivial orbital dynamics that can be expressed in spinor form (as
is the case for, e.g., graphene), for a nontrivial $\kk$ dependent
spin texture (as is the case for, e.g., systems with Rashba SO
coupling), as well as for the most general case of coupled multiband
dynamics with SO coupling, where spin and orbital motion are not
separable (as is the case for, e.g., quasi-2D hole systems).

\subsection{Axial Approximation}

In the following, we employ the \emph{axial aproximation\/}, where
the spinor components $\xi_{n \kk}^{(\nu)}(z)$ satisfy
\begin{equation}\label{eq:axWF}
\xi_{n \kk}^{(\nu)}(z) =
\ee^{-i m_\nu \theta} \: \tilde{\xi}_{n k}^{(\nu)}(z) \quad .
\end{equation}
Here we have expressed the 2D wave vector $\kk$ in polar
coordinates, $\kk = (k, \theta)$, and $m_\nu$ is the $z$ projection
of total angular momentum associated with the band edge Bloch
function $u_\nu$. The axial approximation reflects the fact that it
is often possible to group the basis spinors $u_\nu \dot{{}={}} (0,
\dots, 0, 1, 0, \dots, 0)$ into degenerate multiplets associated
with a total angular momentum $j_\nu$ and $z$ projections $m_\nu$.
Within the axial approximation, we find
\begin{equation}\label{eq:xchMat}
  V^{(nn')}_{\kk\kk'} = \frac{2\pi C}{|\kk - \kk'|}
  \sum_{\nu, \nu'} \ee^{i (m_\nu - m_{\nu'})
  (\theta' - \theta)}
  \mathcal{A}^{(\nu, \nu')}_{n' k', n k} (\theta' - \theta) \: ,
\end{equation}
with radial form factors
\begin{widetext}
\begin{equation}\label{eq:overLP}
  \mathcal{A}^{(\nu, \nu')}_{n' k', n k}
  \left(\theta' - \theta\right)
  = \int dz \int dz'  \;\ee^{-|\kk - \kk'| |z-z'|}
   \: \tilde{\xi}^{(\nu)*}_{n' k'}(z)
   \: \tilde{\xi}^{(\nu')*}_{n k}(z')
   \: \tilde{\xi}^{(\nu')}_{n' k'}(z')
   \: \tilde{\xi}^{(\nu)}_{n k}(z) \: . \quad
\end{equation}
Separating out the most important effect of the angular
dependencies, we rewrite Eq.~(\ref{eq:xchMat}) as follows:
\begin{equation} \label{eq:exchange}
  V^{(nn')}_{\kk\kk'}  =  \frac{2\pi C}{|\kk' - \kk|}
  \left\{ \sum_{\nu, \nu'}
    \mathcal{A}^{(\nu, \nu')}_{n' k', n k}
    \left( \theta' - \theta \right)
    - \sum_{\nu, \nu'}
    \left[ 1 - \ee^{i (m_\nu - m_{\nu'})
      (\theta' - \theta)}\right]
    \mathcal{A}^{(\nu, \nu')}_{n' k', n k}
    \left(\theta' - \theta\right)\right\} \quad .
\end{equation}
From the expression (\ref{eq:exchange}) for the Coulomb-interaction
exchange matrix elements, the effect of a nontrivial spinor
structure of the quasi-2D wave function becomes apparent. The first
term on the r.h.s.\ of Eq.~(\ref{eq:exchange}) represents the usual
form-factor renormalization of the exchange energy in a 2D
system~\cite{and82}. The second term only contributes for spinor
wave functions with more than a single nonvanishing component.

Inserting (\ref{eq:exchange}) into the expressions for
the self-energy correction due to exchange eventually yields
\begin{subequations}
\begin{equation}\label{eq:2Dxchange}
  \frac{E_\mathrm{X}}{N} = -\frac{C}{4 \pi^2 \rho}
  \sum_{n n'} \int_0^{k_{\mathrm{F}n}} k \, dk \:
  \int_0^{k_{\mathrm{F}n'}} k' \,  dk'
  \: \int_{0}^{\pi} d\varphi \: \frac{f_{n n'}(k, k', \varphi)}
  {\sqrt{k^2 + k'^2 - 2kk' \cos\varphi}} \quad ,
\end{equation}
where $k_{\mathrm{F}n}$ is the Fermi wave vector of subband $n$,
and the form factors become
\begin{equation}\label{eq:formF}
  f_{n n'}(k, k', \varphi) =
  \sum_{\nu, \nu'}\Re\mathcal{A}^{(\nu, \nu')}_{n' k', n k} (\varphi)
  - 4 \sum_{\nu, \nu' \atop \nu>\nu'}
  \sin^2 \left(\frac{m_\nu - m_{\nu'}}{2} \varphi \right) \:
  \Re \mathcal{A}^{(\nu, \nu')}_{n' k', n k} (\varphi) \quad .
\end{equation}
\end{subequations}
Assuming we have $\aleph$ spin-resolved subbands occupied,
this can be rephrased in the ``dimensionless'' form
\begin{equation}
  \frac{E_\mathrm{X}}{N} = - C \sqrt{\frac{4 \rho}{\pi\aleph^3}}
  \sum_{n=1}^\aleph \, \sum_{n' = 1}^\aleph \,
  \int_0^{\frac{k_{\mathrm{F}n}}{k_\rho}} d\kappa\, \kappa \:
  \int_0^{\frac{k_{\mathrm{F}n'}}{k_\rho}} d\kappa'\, \kappa'
  \: \int_{0}^{\pi} d\varphi \: \frac{f_{n n'}(\kappa k_\rho, \kappa' k_\rho,
  \varphi)}{\sqrt{\kappa^2 + \kappa'^2 - 2\kappa\kappa' \cos\varphi}} \quad ,
\end{equation}
where $k_\rho = \sqrt{\sum_n k_{\mathrm{F}n}^2 / \aleph}\equiv
\sqrt{4\pi\rho/\aleph}$ is a density-related wave vector that
coincides with the Fermi wave vector of a 2D electron system with
$\aleph$-fold (spin-)degenerate eigenenergies.

\subsection{Subband $\kk \cdot \pp$ method}
\label{sec:subkdotp}

To calculate the form factors $\mathcal{A}^{(\nu, \nu')}_{n'
k', n k}$, the explicit form of the spinor functions
$\tilde{\xi}^{(\nu)}_{n k}(z)$ is needed. The subband $\kk \cdot
\pp$ method~\cite{bro85, bro85a} yields these as superpositions
of subband-edge states,
\begin{equation}\label{eq:kdotpExp}
  \tilde{\xi}^{(\nu)}_{n k}(z)
  = \sum_m a^{(\nu, m)}_{n k} \, \tilde{\xi}^{(\nu)}_{m 0}(z)
  \quad ,
\end{equation}
with expansion coefficients $a^{(\nu, m)}_{n k}$. The radial form factors
are then given by
\begin{equation}\label{eq:kdotpFF}
  \mathcal{A}^{(\nu, \nu')}_{n' k', n k}
  \left(\theta' - \theta\right) =
  \sum_{m_i}
  \bar{\mathcal{A}}^{(\nu, \nu')}_{n' k', n k}
  \: \Phi^{m_1 m_2}_{m_3 m_4}(\nu, \nu', |\kk' - \kk|) \: ,
\end{equation}
with
\begin{equation}
  \bar{\mathcal{A}}^{(\nu, \nu')}_{n' k', n k}
  = a^{(\nu, m_1)\, \ast}_{n' k'} a^{(\nu', m_2)\, \ast}_{n k}
  a^{(\nu', m_3)}_{n' k'} a^{(\nu, m_4)}_{n k}
\end{equation}
and
\begin{equation}
  \label{eq:2ndFF}

    \: \Phi^{m_1 m_2}_{m_3 m_4}(\nu, \nu', q) =
    \int \! dz \int \! dz' \;\ee^{-q |z-z'|} \;

    \tilde{\xi}^{(\nu)*}_{m_1 0}(z) \,
    \tilde{\xi}^{(\nu')*}_{m_2 0}(z') \,
    \tilde \xi^{(\nu')}_{m_3 0}(z') \,
    \tilde \xi^{(\nu)}_{m_4 0}(z) \: .

\end{equation}
For a hard-wall confinement of width $d$, one has
\begin{equation}
  \tilde{\xi}^{(\nu)}_{m 0}(z)
  = \sqrt{2/d} \, \sin (m \pi \, z /d) \quad ,
\end{equation}
with $m =1, 2, \dots$, independent of the spinor index $\nu$. In
this case, the form factors (\ref{eq:2ndFF}) can be evaluated
explicitly, \cite{bet96} giving (with $s \equiv qd = |\kk - \kk'| \,
d$)
\begin{eqnarray}
  \label{eq:hw_FF}
  \Phi_{m_3 m_4}^{m_1m_2} (s)
  & = & \frac{16 \, m_1 m_2 m_3 m_4 \, \pi^4s^2
  \left\{[(-1)^{m_1+m_4} + (-1)^{m_2+m_3}] \ee^{-s}
    - 1 - (-1)^{m_1+m_2+m_3+m_4}\right\}}
  {[(m_2-m_3)^2 \pi^2+s^2] [(m_2+m_3)^2 \pi^2+s^2]
   [(m_1-m_4)^2 \pi^2+s^2] [(m_1+m_4)^2 \pi^2+s^2]}
   \nonumber\\[1ex]
   && {} + \frac{s}{(m_2-m_3)^2\pi^2+s^2}
   \left(\delta_{m_1-m_2+m_3-m_4,0} + \delta_{m_1+m_2-m_3-m_4,0}
     - \delta_{m_1-m_2+m_3+m_4,0} - \delta_{m_1+m_2-m_3+m_4,0} \right)
   \nonumber\\[1ex]
   && {} + \frac{s}{(m_2+m_3)^2\pi^2+s^2}
   \left(\delta_{m_1-m_2-m_3+m_4,0} - \delta_{m_1+m_2+m_3-m_4,0}
     - \delta_{m_1-m_2-m_3-m_4,0}\right)~,
 \end{eqnarray}
\end{widetext}
where $\delta_{m,m'}$ denotes the Kronecker symbol. Note that Eq.\
(\ref{eq:hw_FF}) implies that $\Phi_{m_3 m_4}^{m_1m_2}$ vanishes if
$m_1 + m_2 + m_3 + m_4$ is odd.

\section{Results for spin-1/2 2D systems
\label{sec:2Delectrons}}

\subsection{Zero-width 2D systems}

To make connections with previous results, we apply the general
formalism described in the previous Section to a 2D electron system
whose transverse density profile is a delta function in $z$. In this case,
only $\Phi^{11}_{11}(s \rightarrow 0) = 1$ from Eq.~(\ref{eq:hw_FF})
is relevant. The form factor (\ref{eq:formF}) is then only a function of
$\varphi$, and its explicit expression depends on the particular
type of electron system. For example, in a $\aleph$-component system
modeled within the EMA, we can use the component-related quantum
number as the band label. Hence, $\bar{\mathcal{A}}^{(\nu,
\nu')}_{n', n} = \delta_{n \nu} \delta_{n' \nu'} \delta_{\nu \nu'}$
independent of $k$ and $k'$, yielding $f_{n n'}(k, k',\varphi)
\equiv\delta_{n n'}$ and the result
\begin{equation}\label{eq:EMAgen}
\frac{E_{\text{X}}}{N} = - \frac{4}{3}
\sqrt{\frac{4}{\pi\aleph}} \; C \, \rho^{\frac{1}{2}} \quad .
\end{equation}
which specializes to the expression (\ref{eq:Xideal}) for a spin-1/2
system where $\aleph=2$.

In contrast, if the 2D electrons are subject to Rashba SO
coupling~\cite{ras60, byc84, win03}
\begin{equation}
H_\mathrm{R} = \frac{\hbar^2 k_\mathrm{so}}{m}\, \left(\sigma_x
\, k_y - \sigma_y\, k_x\right) \quad ,
\end{equation}
where $k_\mathrm{so}$ measures the strength of the Rashba SO
coupling, the Fermi surface splits into two circles with radii
$k_{\mathrm{F}\pm} = k_\rho\, \sqrt{1 \pm\chi}$, where $\chi
=(\rho_+ - \rho_-)/\rho$ is the density imbalance between the two
Fermi seas. We find
\begin{subequations}
  \begin{eqnarray}
    \bar{\mathcal{A}}^{(\nu, \nu')}_{\pm\pm}
    & = & \bar{\mathcal{A}}^{(\nu, \nu)}_{\pm\mp}
    = 1/4 \quad, \\
    \bar{\mathcal{A}}^{(1/2, -1/2)}_{\pm\mp}
    & = & \bar{\mathcal{A}}^{(-1/2, 1/2)}_{\pm\mp} = -1/4 \quad,
  \end{eqnarray}
  thus
  \begin{eqnarray}
    f_{\pm\pm}(k, k',\varphi) & = & \cos^2 (\varphi/2)  \quad,\\
    f_{\pm\mp}(k, k',\varphi) & = & \sin^2(\varphi/2) \quad.
  \end{eqnarray}
\end{subequations}
The exchange energy is then the sum of intra-band and inter-band
contributions
\begin{equation}
  \label{eq:rash_ex}
  \frac{E_\mathrm{X}^{(\mathrm{R})}}{N} = \varepsilon_\mathrm{X} \left[
    \Lambda_\mathrm{intra}^{(\mathrm{R})}(\chi) +
    \Lambda_\mathrm{inter}^{(\mathrm{R})}(\chi)\right] \quad ,
\end{equation}
with
\begin{subequations}
\begin{equation}
  \Lambda_\mathrm{intra}^{(\mathrm{R})}(\chi) =
    \left(\frac{1+\chi}{2}\right)^{3/2}
    + \left(\frac{1-\chi}{2} \right)^{3/2}
\end{equation}
and
\begin{widetext}
\begin{equation}
  \Lambda_\mathrm{inter}^{(\mathrm{R})}(\chi)  = \frac{3}{8}
  \int_0^{\sqrt{1+\chi}} \!\!\! d\kappa \int_0^{\sqrt{1-\chi}}
  \!\!\! d\kappa' (\kappa+\kappa') \left[ E\left(\frac{4\kappa
      \kappa'}{(\kappa+\kappa')^2}\right) - \frac{(\kappa -
    \kappa')^2}{(\kappa +\kappa')^2}
    K\left(\frac{4\kappa\kappa'}{(\kappa+\kappa')^2}\right) \right]
  \quad .
\end{equation}
\end{widetext}
\end{subequations}
Here $K(\cdot)$ and $E(\cdot)$ denote complete elliptic integrals of
the first and second kind, respectively, as defined in
Ref.~\onlinecite{abr72}. The term in square brackets in Eq.\
(\ref{eq:rash_ex}) expresses the correction caused by Rashba SO
coupling to the simple exchange energy $\varepsilon_\mathrm{X}$ of a
2D electron gas with zero width. Explicit calculation shows that
\begin{equation}\label{eq:ExchRashba}
1 \le \Lambda_\mathrm{intra}^{(\mathrm{R})}(\chi) +
\Lambda_\mathrm{inter}^{(\mathrm{R})}(\chi) < 1.002
\end{equation}
for any value of $\chi$, i.e., the presence of Rashba SO coupling
very slightly enhances (the magnitude of) the exchange energy of the
2D electron gas.~\cite{che07} (See Fig.~3 of
Ref.~\onlinecite{che11a} for a clear illustration.)
Note that the inequality in Eq.~(\ref{eq:ExchRashba}) holds for
parabolic bands with any values of the effective mass and Rashba
SO-coupling strength. The rather small magnitude of this effect is due
to a subtle interplay between the intra-band and inter-band contributions
for the special case of Rashba SO coupling and does not hold for arbitrary
types of SO coupling.~\cite{che07}

\subsection{Quasi-2D systems: Effect of finite width}
 \label{sec:fullumix}

When a quasi-2D spin-1/2 system without SO coupling is confined by a
hard-wall potential of width $d$, the form factors
$\mathcal{A}^{(\nu, \nu')}_{n' k', n k}(\varphi)$ are given by Eq.\
(\ref{eq:kdotpFF}) with
\begin{equation}\label{eq:phi_rel}
\Phi^{1 1}_{1 1}(s) = \frac{3 s^5+20 \pi^2 s^3+32 \pi^4
\left(e^{-s}-1+s\right)}{(s^3+4\pi^2 s)^2}
\, . \quad
\end{equation}
In the EMA case appropriate for electron systems, using again the
spin projection as band label, we have $f_{n n'}(k, k',\varphi) =
\Phi^{1 1}_{1 1}(s) \,\delta_{n n'}$. This yields the result
(\ref{eq:Xfinwidth}), shown as the blue dashed curve in
Fig.~\ref{fig:Reduction2}. The width-dependent function
$\Lambda^{(\mathrm{EMA})}(x)$ can be expressed as a Taylor series
\begin{subequations}
\label{eq:ema-expand}
\begin{equation}
\Lambda^{(\mathrm{EMA})}(x)
= \sum_{n=0}^\infty \lambda^{(\mathrm{EMA})}_n \, x^n \quad ,
\end{equation}
with coefficients
\begin{widetext}
\begin{equation}
\lambda^{(\mathrm{EMA})}_n
=\frac{3}{4 n!}\,\,\left.\frac{d^{n} \, \Phi^{1 1}_{1 1}(s) }{d s^n}
\right|_{s=0}
\;\int_0^1 d\kappa \,\, \kappa \int_0^1 d\kappa' \: \kappa'
\int_{0}^{\pi} d\varphi
\left(\kappa^2+\kappa'^2-2 \kappa\kappa'\cos\varphi \right)^{(n-1)/2}
\quad .
\end{equation}
\end{widetext}
\end{subequations}
This Taylor expansion is quickly convergent. For an error of less
than $10$\%, going up to $n=4$ is sufficient to describe quasi-2D
systems within the density range $k_\rho d < \sqrt{3} \pi$, where
only the lowest subband is occupied.

\section{Exchange energy of spin-3/2 2D~hole systems}
\label{sec:2Dholes}

\subsection{Theoretical description of 2D hole systems}

We have calculated the exchange contribution to the ground state
energy of quasi-2D hole systems, assuming the common case that the
density is such that only the lowest HH-like band is
occupied.~\footnote{Within our model where a hard-wall confinement
has been assumed, this condition implies $\rho < 10^{12}$~cm${}^{-2}$
for a 15-nm-wide quantum well. Density estimates for real samples will
have to be based on a more accurate, self-consistent modelling of
the confining potential.}
The quantum-well growth direction is assumed to be parallel to the [001]
crystallographic axis, and we considered three different host
materials: GaAs, InAs, and CdTe.

We adopt the 4$\times$4 Luttinger model~\cite{lut56}, including a
potential $V(z)$ that models the confinement in $z$-direction. To be
specific, we assume infinitely high barriers at $z =0$ and $z =d$,
with $d$ the width of the quantum well. Using the eigenstates for
spin projection perpendicular to the 2D plane as basis states such
that $u_{3/2}=(1,0,0,0)$, $u_{1/2}=(0,1,0,0)$, $\dots$, the
Luttinger Hamiltonian for $z\parallel [001]$ is given in matrix
representation by
\begin{equation}
\mathcal{H}_\mathrm{L} =\left(
\begin{array}{cccc}
P+Q& L & M & 0 \\
L^* & P-Q& 0& M \\
M^* & 0 & P-Q& -L \\
0 & M^* & -L^*& P+Q
\end{array}
\right),
\label{eq:LuttHam}
\end{equation}
where
\begin{subequations}
\begin{eqnarray}
P& =&\frac{\hbar^2}{2m_0}\gamma_1 (\kk^2+k_z^2) + V(z)~,\\
Q& =&\frac{\hbar^2}{2m_0}\gamma_2 (\kk^2-2k_z^2)~,\\
L& =&-\frac{\hbar^2}{2m_0}2\sqrt{3}\gamma_3~ k_- \, k_z~,\\
M& =&-\frac{\hbar^2}{2m_0} \frac{\sqrt{3}}{2}
\left[(\gamma_2+\gamma_3) \, k_-^2 + (\gamma_2-\gamma_3) \,k_+^2 \right].
\label{eq:Maxial}
\end{eqnarray}
\end{subequations}
Here $k_\pm = k_x\pm i k_y$ in terms of the components of the
in-plane wave vector $\kk = (k_x,k_y)$, $k_z =-i\partial/\partial
z$, and $\gamma_{1, 2, 3}$ are the ma\-te\-rial-dependent Luttinger
band-structure parameters. Their values for the three semiconductor
materials considered here are given in Table \ref{tab:Lutpara}.

\begin{table}[b]
\caption{\label{tab:Lutpara} Luttinger parameters used in the calculations.}
\tabcolsep 2ex
\begin{tabular}{cccc}
\hline\hline
& $\gamma_1$ & $\gamma_2$ & $\gamma_3$ \\ \hline
GaAs (Ref.~\onlinecite{vur01}) & 6.98  & 2.06  & 2.93\\
InAs (Ref.~\onlinecite{vur01}) &  20. & 8.5 & 9.2 \\
CdTe (Ref.~\onlinecite{die01}) & 4.14  & 1.09 & 1.62 \\  \hline  \hline
\end{tabular}
\end{table}

As the second term in Eq.\ (\ref{eq:Maxial}) [the one proportional
to $(\gamma_2-\gamma_3)$] is generally small, it is often neglected
in the matrix element $M$ of the Hamiltonian (\ref{eq:LuttHam}).
This constitutes the axial approximation~\cite{suz74, tre79, win03}
that we also adopt here. As can be seen from Eq.\ (\ref{eq:LuttHam}),
$\mathcal{H}_\mathrm{L}$ is diagonal for $\kk=0$, which implies that the
corresponding eigenstates are of purely HH or LH character. We
utilize the subband $\kk\cdot\pp$ theory~\cite{bro85, bro85a}, described
in Sec.~\ref{sec:subkdotp} above, to numerically solve the multi-band
Schr\"odinger equation for the confined valence-band states. Using this
method, the subband dispersions $E_{nk}$ and the coefficients
$a^{(\nu,m)}_{n k}$ from Eq.~(\ref{eq:kdotpExp}) are obtained. We
include as many basis functions as are necessary to ensure accuracy
of the lowest few subband dispersions. Fig.~\ref{fig:Dispersions} shows
the quasi-2D subbands obtained for CdTe, GaAs, and InAs.

The eigenspinors corresponding to states in the lowest doubly
degenerate quasi-2D hole subband are used to determine the radial
form factors from Eq.~(\ref{eq:kdotpFF}), with analytical
expressions for the bound-state form factors (\ref{eq:2ndFF}) given
in Eq.~(\ref{eq:hw_FF}). Using the result as input for
Eqs.~(\ref{eq:2Dxchange}) and (\ref{eq:formF}), the exchange energy
of the quasi-2D hole system can be calculated. A modified quadrature
method \cite{bak77, dun77} was applied to treat the singularity in
the integrand of Eq.~(\ref{eq:2Dxchange}).

\subsection{Zero-width limit}

In the zero-width limit, only a single pair of degenerate 2D hole subbands
exist with eigenstates that are of purely HH character, i.e., only the spinor
entries related to the $\pm 3/2$ spin projection quantum numbers are
nonzero. This situation is analogous to the EMA-based description of a
spin-1/2 2D electron system. For example, using the representation where
the two bands are related to eigenstates $(1, 0, 0, 0)$ and $(0, 0, 0, 1)$,
we have no inter-band contribution to the exchange energy, and the
intra-band contribution yields Eq.~(\ref{eq:Xideal}).

\subsection{Fully HH-LH-mixed limit}

In real quasi-2D hole systems, the states at finite in-plane
momentum are not anymore eigenstates of spin projection
perpendicular to the 2D plane~\cite{win03}. In fact, in the limit of
large kinetic energy of the in-plane motion, the spinors have
approximately equal admixture of HH and LH components. This is
illustrated in Fig.~\ref{fig:HHcont}. In this limit, we can
approximate the true spin-3/2 spinor wave functions from the two
degenerate lowest subbands by assuming them to be of the
form~\footnote{Our \textit{Ansatz\/} is compatible with the basic
symmetries exhibited by hole quantum-well states [L.~C.\ Andreani,
A.~Pasquarello, and F.~Bassani, Phys.\ Rev.\ B~\textbf{36}, 5887
(1987)] and satisfactorily approximates the numerically found
spinor patterns.} $(1, 0, 1, 0) [\sin(\pi z/d)]/\sqrt{d}$ and
$(0, 1, 0, 1) [\sin(\pi z/d)]/\sqrt{d}$. Then we can use the
formalism based on Eqs.~(\ref{eq:2Dxchange}) and (\ref{eq:formF}) to
estimate the exchange energy in such a system. We find for this
fully HH-LH-mixed case
\begin{subequations}
\begin{eqnarray}
f_{\pm\pm}(k, k',\varphi) &=&  \Phi^{1 1}_{1 1}(s)\, \cos^2 \varphi \quad , \\
f_{\pm\mp}(k, k',\varphi) &=&  0 \quad  ,
\label{eq:fpm}
\end{eqnarray}
\end{subequations}
with $\Phi^{11}_{11}$ given in Eq.~(\ref{eq:phi_rel}). The resulting
width dependence of the exchange energy is shown as the orange
dashed curve in Fig.~\ref{fig:Reduction2}. Similar to Eq.\
(\ref{eq:ema-expand}) we can perform the Taylor expansion
\begin{equation}\label{eq:fullMix}
\frac{E_\mathrm{X}^{(\mathrm{mix})}}{N}
= \varepsilon_\mathrm{X}\, \Lambda^{(\mathrm{mix})}
(k_\rho d) \equiv \varepsilon_\mathrm{X}\, \sum_{n=0}^{\infty}
\lambda^{(\mathrm{mix})}_n \left(k_\rho d\right)^n,
\end{equation}
with expansion coefficients
\begin{widetext}
\begin{align}
\lambda^{(\mathrm{mix})}_n
= \frac{3}{8 n!} \left.\frac{d^{n} \, \Phi^{1 1}_{1 1}(s)}{d s^n} \right|_{s=0}
\int_0^1 d\kappa \, \kappa \int_0^1 d\kappa' \, \kappa'
\int_{-\pi}^{\pi} d\varphi \; \cos^2(\varphi)
\left(\kappa^2+\kappa'^2-2 \kappa \kappa'\cos\varphi\right)^{(n-1)/2} \quad .
\end{align}
\end{widetext}
To describe quasi-2D hole systems within the density range, where
only the lowest subband is occupied, and with an error of less than
10\%, it is sufficient to go up to $n=6$.

\subsection{Numerical results for the general case}

The variation of the exchange energy as a function of Fermi wave
vector and quantum-well width is shown in Fig.~\ref{fig:Reduction2}.
In the low-density, small-width limit, the curve coincides with the
plot of the expression (\ref{eq:Xfinwidth}) obtained for the EMA
quasi-2D system. In contrast, the fully mixed case (\ref{eq:fullMix})
provides a very good description in the limit of large densities. The
small deviation that persists in the asymptotic limit arises due to
our assumption of a single sine-wave contribution to the hole bound
state in the full-mixing model considered above.

To further bolster our argument that HH-LH mixing is the origin of
exchange-energy suppression in quasi-2D hole systems, we have
calculated the HH character $C_\mathrm{HH}$ of the states at the
Fermi energy by integrating the combined probability densities for
the $\pm 3/2$ spin projection entries in the corresponding
four-spinor wave function. In terms of the latter's expression as a
superposition of states at $\kk=0$ [see Eq.~(\ref{eq:kdotpExp})], we
find
\begin{equation}
C_\mathrm{HH}\equiv\sum_m\sum_{\nu=\pm 3/2}
\left| a^{(\nu,m)}_{1 k_\rho} \right|^2 \quad .
\end{equation}
The results for GaAs, InAs, and CdTe are shown in
Fig.~\ref{fig:HHcont}. Comparison
with Fig.~\ref{fig:Reduction2} shows that the deviation from the
behavior expected for a simple quasi-2D spin-1/2 electron system
occurs when the hole states at the Fermi energy are no longer of
purely HH character.~\footnote{Even though states deep inside the
Fermi sea are still pure HHs, their pairwise contribution to the
exchange energy gets overwhelmed by that of the much more numerous
fully mixed states.}

\section{Conclusions and Outlook}
\label{sec:conc}

We have calculated the exchange-energy contribution to the total
energy of hard-wall-confined quasi-2D hole systems when only the
lowest subband is occupied. Even though there is only a double
degeneracy of states in this band, the wave functions are
four-spinors associated with the intrinsic spin-3/2 degree of
freedom for valence-band states. At sufficiently low densities
and/or small quantum-well widths when the quasi-2D hole states are
almost purely heavy-hole-like, the behavior resembles that of
ordinary (spin-1/2) quasi-2D electron systems. However, as soon as
the light-hole admixture in the spinors becomes appreciable, the
exchange energy turns out to be suppressed.

Performing calculations for the specific case of a hard-wall
confinement enabled us to obtain analytical expressions for relevant
limiting cases and compare these with the numerically calculated
results for the exchange energy of quasi-2D hole systems.
However, the general formalism to calculate the exchange energy in
confined multi-band systems that is developed in this work can be
readily adapted to more accurate descriptions~\cite{win03} of hole
quantum wells. Our results provide strong evidence that the
suppression of exchange effects will be a general feature of any
situation where HH-LH mixing is substantial, and we therefore
propose this mechanism as the basic explanation of an experimentally
observed absence of exchange renormalizations in quasi-2D hole
systems~\cite{pin86, win05a, chi11}. Depending on sample details,
this behavior may occur in different parameter regimes, e.g., while
HH-LH mixing is strong for larger densities for a hard-wall
confinement, the fully mixed regime occurs at \emph{low\/} densities
for a density-dependent triangular potential realized in single
heterojunctions. Further studies are needed to provide a basis for
accurate comparisons with experimental data, as the actual shape of
the confinement potential and the (here neglected) anisotropy of the
dispersion may influence the exact functional dependence of the
exchange energy on characteristic system parameters such as the
2D-hole sheet density.

\begin{acknowledgments}
  Work at Argonne was supported by DOE BES under Contract No.\
  DE-AC02-06CH11357.
\end{acknowledgments}