Excluded permutation matrices and the Stanley-Wilf conjecture

Adam Marcus, Gábor Tardos

Research output: Contribution to journalArticle

187 Scopus citations

Abstract

This paper examines the extremal problem of how many 1-entries an n×n 0-1 matrix can have that avoids a certain fixed submatrix P. For any permutation matrix P we prove a linear bound, settling a conjecture of Zoltán Füredi and Péter Hajnal (Discrete Math. 103(1992) 233). Due to the work of Martin Klazar (D. Krob, A.A. Mikhalev, A.V. Mikhalev (Eds.), Formal Power Series and Algebraics Combinatorics, Springer, Berlin, 2000, pp. 250-255), this also settles the conjecture of Stanley and Wilf on the number of n-permutations avoiding a fixed permutation and a related conjecture of Alon and Friedgut (J. Combin Theory Ser A 89(2000) 133).

Original languageEnglish (US)
Pages (from-to)153-160
Number of pages8
JournalJournal of Combinatorial Theory. Series A
Volume107
Issue number1
DOIs
StatePublished - Jul 1 2004

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Keywords

  • Extremal problems
  • Forbidden submatrices
  • Pattern avoidance
  • Stanley-Wilf conjecture

Fingerprint Dive into the research topics of 'Excluded permutation matrices and the Stanley-Wilf conjecture'. Together they form a unique fingerprint.

  • Cite this