Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, February 12, 2004, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Yoshio Okamoto
How many 1's can there be in an n by n 0/1-matrix which avoids a
certain fixed 0/1-matrix? Such a problem is related to Zarankiewicz
problem in Extremal graph theory, and to Davenport-Schinzel theory
which plays a great role in discrete and computational geometry.
Furedi & Hajnal ('92) conjectured if a given 0/1-matrix is a permutation matrix then the number of 1's is linear in n. Recently, Marcus & Tardos proved the conjecture affirmative in a quite simple way. In this talk, we are going to look at their proof, some consequences, and open problems.
Automatic MiSe System Software Version 1.4803M | admin login