IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Forbidden Families of Configurations

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


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.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster