The Füredi-Hajnal Conjecture Implies the Stanley-Wilf Conjecture

Martin Klazar ()
Additional contact information
Martin Klazar: Charles University, Department of Applied Mathematics

A chapter in Formal Power Series and Algebraic Combinatorics, 2000, pp 250-255 from Springer

Abstract: Abstract We show that the Stanley-Wilf enumerative conjecture on permutations follows easily from the Füredi-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.

Keywords: Bipartite Graph; Formal Power Series; Permutation Matrix; Pigeonhole Principle; Equality Pattern (search for similar items in EconPapers)
Date: 2000
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-662-04166-6_22

Ordering information: This item can be ordered from
http://www.springer.com/9783662041666

DOI: 10.1007/978-3-662-04166-6_22

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().