IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Forbidden Submatrices

  • Jan. 31, 2013
  • 2 p.m.
  • LeConte 312


The problem considered is an ordered version of the typical forbidden configuration problem in extremal set theory. I find it convenient to use matrices to encode sets. A matrix is called simple if it is a $(0,1)$-matrix with no repeated columns. For an $m$-rowed simple matrix $A$, we can think of $A$ as an incidence matrix where the columns of $A$ encode subsets of $\{1,2,...,m\}$.

Let $F$ be a given $k$-rowed $(0,1)$-matrix. We define $Avoids(m,F)=\{m$-rowed simple matrix $A : A$ has no submatrix $F\}$. With this definition we have an extremal problem: $fs(m,F)$ is the maximum, over all $A$ in $Avoids(m,F)$, of the number of columns in $A$. It is conjectured by A, Frankl, Furedi and Pach that for a $k$-rowed $F$, $fs(m,F)$ is $m^k$. We indicate a few results (with Ronnie Chen and Ron Estrin) and some ideas from amortized complexity.

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