# Discrete Math Seminar - Forbidden Configurations: Critical Substructures

## Topic

Forbidden Configurations: Critical Substructures

## Details

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.

This is a Past Event

Event Type

**Scientific, Seminar**

Date

**September 29, 2009**

Time

**-**

Location

University of British Columbia