Events
The Furedi-Hajnal and Stanley-Wilf Conjectures
00:00 29-11-2006
Almost 15 years ago, Furedi and Hajnal began a systematic investigation of extremal problems on {0,1}-matrices. In particular, they asked, if one was to fix their favorite {0,1}-matrix K, how many 1-entries could they then cram into an n x n {0,1}-matrix A while avoiding the matrix K (by "avoiding" we mean that there is no order preserving mapping f from K into A s.t. f(K(i,j)) = 1 whenever K(i,j) = 1). In particular, how does ex(K,n), the maximum number of 1-entries that are crammable, grow as a function of n?
Apart from a number of interesting results (including growth rates that include logs, a phenomenon unseen in the analogous unordered graph problem), a number of interesting conjectures arose. The most well-known of these, which has since been named the Furedi-Hajnal Conjecture, predicted that ex(K,n) = O(n) whenever the chosen K is a permutation matrix (all rows and columns each have a single 1-entry). In this talk, I will show that the conjectured growth is correct, and then show how it implies the solution to the (much more well-known) Stanley-Wilf Conjecture, which asks how many permutations of length n avoid a fixed smaller permutation.
As a side note, the proofs are surprisingly (or perhaps "refreshingly", depending on who you ask) simple - they use nothing more than basic counting, pigeonhole, and induction. The talk will be accessible to anyone (including undergraduates and even advanced high-schoolers) with even a basic knowledge of combinatorics. For this reason, I would like to extend a special invitation to anyone who is interested in the field of combinatorics (or mathematics in general) but who wouldn't normally attend a research seminar for fear that the material would be too advanced. On the other hand, I hope to see advanced students and researchers there as well, as this will serve as a gentle reminder that hard problems don't necessarily require hard solutions.
