Discrete Math Seminar: Quadratic Forbidden Configurations

  • Date: 01/26/2010
Miguel Raggi (UBC)

University of British Columbia


We wish to understand the boundary between forbidden configurations on 4 rows that yield a quadratic bound and those that have cubic constructions. The result is joint with my supervisor and Attila Sali. The bounds we are concerned with are the following: For a (0,1)-matrix F, we define forb(m,F) to be the maximum number of columns in an m-rowed (0,1)-matrix which has no repeated columns and has no submatrix which is a row and column permutation of F. The asymptotics of forb(m,F) for arbitrary F have been conjectured by Anstee and Sali.


4:00pm - 5:00pm, WMAX 216