Almost (perhaps over) 20 years ago, the following question started to appear (in numerous forms) in the literature: given a fixed permutation pi of length k, how many permutations of length n avoid pi? By “avoid” we mean that there is no order preserving mapping f s.t. f(pi(i)) \leq f(pi(j)) whenever \pi(i) \leq pi(j) for all i,j in pi.
In the late 90’s, a rather bold conjecture surfaced, independently from Richard Stanley and Herb Wilf, that the correct answer is c^n for some c = c(pi).
Since then, a number of attempts had been made, and the conjecture was proved for certain subsets of permutations, but by the turn of the century, progress had stalled. Conferences began to be organized and books written in an attempt to focus efforts on this now notorious problem.
In this talk, I will give a proof of this conjecture, by way of the F"uredi-Hajnal conjecture, a question about pattern avoidance in {0,1}-matrices. 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 faculty there as well, as this will serve as a gentle reminder that hard problems don’t necessarily require hard solutions.