TY - JOUR

T1 - Excluded permutation matrices and the Stanley-Wilf conjecture

AU - Marcus, Adam

AU - Tardos, Gábor

N1 - Funding Information:
E-mail addresses: [email protected] (A. Marcus), [email protected] (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

SN - 0097-3165

VL - 107

SP - 153

EP - 160

JO - Journal of Combinatorial Theory. Series A

JF - Journal of Combinatorial Theory. Series A

IS - 1

ER -