## Forbidden Families of Configurations

- Feb. 21, 2013
- 2 p.m.
- LeConte 312

## Abstract

We consider the problem of forbidden configurations. Define a matrix to be simple if it is a
$(0,1)$-matrix with no repeated columns. For a given $(0,1)$-matrix $F$, we say a matrix $A$
has no configuration $F$ if there is no submatrix of $A$ which is a row and column permutation
of $F$. Given $m$ and a family of forbidden configurations, we seek a bound on the number
of columns in an $m$-rowed simple matrix which has no configuration in the family.

There is an attractive, unresolved conjecture of Anstee and Sali which predicts the asymptotics
of the bound when forbidding a single configuration $F$. We consider some interesting cases
involving forbidding a (finite) family of forbidden configurations. Some cases have bounds
predicted by the conjecture and some do not. This is joint work with Christina Koch,
Miguel Raggi and Attila Sali.