Fyrirlesari: Gabor Tardos frá Renyi stofnuninni Búdapest
Titill: Extremal theory of 0-1 matrices
Staðsetning og tími: Askja, N-128, kl. 10:00 mánudaginn 26. ágúst 2024
Ágrip: We say that a a 0-1 matrix A contains another such matrix (pattern) P if P can be obtained from a submatrix of A by possibly changing a few 1 entries to 0. The main question of this theory is to estimate the maximal number of 1 entries in an n by n 0-1 matrix NOT containing a given pattern P. This question has very close connections to Turan type extremal graph theory and also to the Devenport-Schinzel theory of sequences. Results in the extremal theory of 0-1 matrices proved useful in attacking problems in far away fields as combinatorial geometry and the analysis of algorithms.