Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information
Date and Time: Thursday, October 21, 2010, 12:15 pm
Duration: This information is not available in the database
Location: OAT S15/S16/S17
Speaker: Gabriel Nivasch
"Generalized Davenport-Schinzel sequences" are sequences of symbols that avoid some fixed subsequence (or "forbidden pattern"). The problem is to make the sequence as long as possible, given a bound n on its alphabet size.
A similar problem exists for 0/1-matrices: Given a forbidden 0/1-submatrix A and an integer n, we want to build an nxn 0/1-matrix M with as many 1's as possible, avoiding A as a submatrix. (For M to contain A as a submatrix, the 1's of A must match to 1's of M, but the 0's of A can match to either 0's or 1's of M).
We survey recent results on these two problems and the connection between them.
Automatic MiSe System Software Version 1.4803M | admin login