Discrete Math Seminar - Forbidden Configurations: Critical Substructures

  • Date: 09/29/2009
Lecturer(s):
Richard Anstee (UBC)
Location: 

University of British Columbia

Topic: 

Forbidden Configurations: Critical Substructures

Description: 

Let F be a kxl (0,1)-matrix. We say that a (0,1)-matrix A has F as a
`configuration' if some row and column permutation of F is a
submatrix of A.

 

We are interested in `simple' matrices, namely (0,1)-matrices with no
repeated columns. If A is a simple matrix and has no configuration F then
what can we deduce about A? Our extremal problem is given m,F to
determine the maximum number of columns forb(m,F) in an m-rowed simple matrix A
which has no configuration F.

 

A `critical substructure' of F is a configuration F’ which is
contained in F and such that forb(m,F’)=forb(m,F). We give some examples to
demonstrate how this idea often helps in determining forb(m,F).

This represents joint work with Steven Karp and also Miguel Raggi.

Schedule: 

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

Sponsor: 

pims