Excluded permutation matrices and the Stanley-Wilf conjecture

Adam Marcus; Gábor Tardos

doi:10.1016/j.jcta.2004.04.002

Excluded permutation matrices and the Stanley-Wilf conjecture

Adam Marcus, Gábor Tardos

Mathematics

Research output: Contribution to journal › Article › peer-review

193 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 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	https://doi.org/10.1016/j.jcta.2004.04.002
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

Access to Document

10.1016/j.jcta.2004.04.002

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

Cite this

@article{62260ecdfa8c4e54a1a81fde944e9387,

title = "Excluded permutation matrices and the Stanley-Wilf conjecture",

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{\'a}n F{\"u}redi and P{\'e}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).",

keywords = "Extremal problems, Forbidden submatrices, Pattern avoidance, Stanley-Wilf conjecture",

author = "Adam Marcus and G{\'a}bor Tardos",

year = "2004",

month = jul,

day = "1",

doi = "10.1016/j.jcta.2004.04.002",

language = "English (US)",

volume = "107",

pages = "153--160",

journal = "Journal of Combinatorial Theory - Series A",

issn = "0097-3165",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - Excluded permutation matrices and the Stanley-Wilf conjecture

AU - Marcus, Adam

AU - Tardos, Gábor

PY - 2004/7/1

Y1 - 2004/7/1

N2 - 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).

AB - 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).

KW - Extremal problems

KW - Forbidden submatrices

KW - Pattern avoidance

KW - Stanley-Wilf conjecture

UR - http://www.scopus.com/inward/record.url?scp=3242734182&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=3242734182&partnerID=8YFLogxK

U2 - 10.1016/j.jcta.2004.04.002

DO - 10.1016/j.jcta.2004.04.002

M3 - Article

AN - SCOPUS:3242734182

VL - 107

SP - 153

EP - 160

JO - Journal of Combinatorial Theory - Series A

JF - Journal of Combinatorial Theory - Series A

SN - 0097-3165

IS - 1

ER -