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 language | English (US) |
|---|---|
| Pages (from-to) | 153-160 |
| Number of pages | 8 |
| Journal | Journal of Combinatorial Theory. Series A |
| Volume | 107 |
| Issue number | 1 |
| DOIs | |
| State | Published - 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
Marcus, A., & Tardos, G. (2004). Excluded permutation matrices and the Stanley-Wilf conjecture. Journal of Combinatorial Theory. Series A, 107(1), 153-160. https://doi.org/10.1016/j.jcta.2004.04.002