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

237 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 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

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",

note = "Funding Information: E-mail addresses: adam@math.gatech.edu (A. Marcus), tardos@renyi.hu (G. Tardos). 1Visiting Researcher, Alfr{\'e}d R{\'e}nyi Institute, 1364 Budapest, Pf.127, Hungary, on leave from the Department of Mathematics (ACO), Georgia Institute of Technology, Atlanta, GA 30332-0160. This research was made possible due to funding by the Fulbright Program in Hungary. 2Partially supported by the Hungarian National Research Fund OTKA T029255 and T046234.",

year = "2004",

month = jul,

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

N1 - Funding Information: E-mail addresses: adam@math.gatech.edu (A. Marcus), tardos@renyi.hu (G. Tardos). 1Visiting Researcher, Alfréd Rényi Institute, 1364 Budapest, Pf.127, Hungary, on leave from the Department of Mathematics (ACO), Georgia Institute of Technology, Atlanta, GA 30332-0160. This research was made possible due to funding by the Fulbright Program in Hungary. 2Partially supported by the Hungarian National Research Fund OTKA T029255 and T046234.

PY - 2004/7

Y1 - 2004/7

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 -

Excluded permutation matrices and the Stanley-Wilf conjecture

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this