Discrete Math Seminar: Richard Anstee

  • Date: 02/10/2015
  • Time: 16:00
Lecturer(s):
Richard Anstee , UBC
Location: 

University of British Columbia

Topic: 

Ramsey Theory and Forbidden Configurations

Description: 

We say that a matrix F is a configuration in a matrix A if there is a submatrix of A which is a row and column permutation of F. We consider the following extremal function. Let G be a finite set of (0,1)-matrices. Let forb(m,G) denote the maximum number of columns in an m-rowed (0,1)-matrix A that has no repeated columns and no configuration F in the set G. It was already shown by Balogh and Bollobas that for any given k that if G consists of the three matrices I_k (identity matrix of order k),I_k^c (0-1 complement of I_k) and T_k (upper triangular (0,1)-matrix) then forb(m,G) is a constant where the constant is at least 2^{ck} for some constant c and at most 2^{2^k}. These three are unavoidable configurations in much the same way that a clique of size k and an independent set of size k are unavoidable in a large complete graph, you always get one or the other. We obtain a new argument (using Ramsey Theory) that brings the bound on forb(m,G) to 2^{ck2}. This is joint work with Lincoln Lu.

Other Information: 

Location: ESB 4127