# Discrete Math Seminar: Ruiyuan Chen

## Topic

Forbidden Submatrices

## Details

Abstract:

We consider an extremal problem arising from forbidding a submatrix. Let F be a given (0,1)-matrix. Let avoid(m,F) denote the set of m-rowed (0,1)-matrices with no repeated columns and no submatrix F. Here we are concerned with row and column order. Let f(m,F) denote the maximum number of columns among all matrices in avoid(m,F). A conjecture of Anstee, Frankl, Furedi and Pach is that if F has k row, then there is a constant c(F) so that f(m,F)<c(F)m^k. We make progress in the case k=2 using an `amortized' analysis. This represents joint work with Richard Anstee and Attila Sali.

We consider an extremal problem arising from forbidding a submatrix. Let F be a given (0,1)-matrix. Let avoid(m,F) denote the set of m-rowed (0,1)-matrices with no repeated columns and no submatrix F. Here we are concerned with row and column order. Let f(m,F) denote the maximum number of columns among all matrices in avoid(m,F). A conjecture of Anstee, Frankl, Furedi and Pach is that if F has k row, then there is a constant c(F) so that f(m,F)<c(F)m^k. We make progress in the case k=2 using an `amortized' analysis. This represents joint work with Richard Anstee and Attila Sali.

## Additional Information

Location: MATX 1102

For more information please visit UBC mathematics department

Ruiyuan (Ronnie) Chen

This is a Past Event

Event Type

**Scientific, Seminar**

Date

**November 8, 2011**

Time

**-**

Location

University of British Columbia