Excluded permutation matrices and the Stanley-Wilf conjecture

Adam Marcus, Gábor Tardos

Research output: Contribution to journalArticlepeer-review

203 Scopus citations


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 languageAmerican English
Pages (from-to)153-160
Number of pages8
JournalJournal of Combinatorial Theory. Series A
Issue number1
StatePublished - Jul 2004

ASJC Scopus subject areas

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


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


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

Cite this