Abstract:

We show that the Stanley-Wilf enumerative conjecture on permutations follows easily from the F"uredi-Hajnal extremal conjecture on 0-1 matrices. We apply the method, discovered by Alon and Friedgut, that derives an (almost) exponential bound on the number of some objects from a (almost) linear bound on their sizes. They proved by it a weaker form of the Stanley-Wilf conjecture. Using bipartite graphs, we give a simpler proof of their result.