Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, January 12, 2006, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Samuel Zürcher
We consider 0/1 matrices and say that an n*n matrix A contains a k*l matrix P (the pattern) if and only if we can find a submatrix B of A (that is obtained by deleting rows and columns of A) so that (P)i,j = 1 implies (B)i,j = 1. Otherwise, we say that A avoids P. For a given pattern P, we are interested in the maximum number of 1 entries that an n*n matrix can have avoiding the pattern P; written as ex(n, P). This extremal function is known for all patterns with at most four 1 entries and each one of those patterns is member in one of five classes; we'll show examples for each of those classes and sketch some of the proofs for the bounds on ex(n, P). In a second part of the talk, we'll show reductions that can be used to determine ex(n, P') for a pattern P' with previously unknown complexity, based on the knowledge of the complexity of a somehow related pattern P.
This talk is mainly based on work by Tardos, Marcus, Füredi, Hajnal, and Keszegh.
Automatic MiSe System Software Version 1.4803M | admin login