Discrete Math Seminar: Quadratic Forbidden Configurations

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

University of British Columbia

Description: 

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.

Schedule: 

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

Sponsor: