TY - JOUR
T1 - Hereditary properties of partitions, ordered graphs and ordered hypergraphs
AU - Balogh, József
AU - Bollobás, Béla
AU - Morris, Robert
N1 - Funding Information:
The first author was supported during this research by OTKA grant T049398 and US National Science Foundation (NSF) grant DMS-0302804, the second by NSF grant ITR 0225610, and the third by a Van Vleet Memorial Doctoral Fellowship.
PY - 2006/11
Y1 - 2006/11
N2 - In this paper we use the Klazar-Marcus-Tardos method (see [A. Marcus, G. Tardos, Excluded permutation matrices and the Stanley-Wilf conjecture. J. Combin. Theory Ser. A 107 (2004) 153-160]) to prove that, if a hereditary property of partitions P has super-exponential speed, then, for every k-permutation π, P contains the partition of [2 k] with parts {{i, π (i) + k} : i ∈ [k]}. We also prove a similar jump, from exponential to factorial, in the possible speeds of monotone properties of ordered graphs, and of hereditary properties of ordered graphs not containing large complete, or complete bipartite ordered graphs. Our results generalize the Stanley-Wilf conjecture on the number of n-permutations avoiding a fixed permutation, which was recently proved by the combined results of Klazar [M. Klazar, The Füredi-Hajnal conjecture implies the Stanley-Wilf conjecture, in: D. Krob, A.A. Mikhalev, A.V. Mikhalev (Eds.), Formal Power Series and Algebraic Combinatorics, Springer, Berlin, 2000, pp. 250-255] and Marcus and Tardos [A. Marcus, G. Tardos, Excluded permutation matrices and the Stanley-Wilf conjecture, J. Combin. Theory Ser. A 107 (2004) 153-160]. Our main results follow from a generalization to ordered hypergraphs of the theorem of Marcus and Tardos.
AB - In this paper we use the Klazar-Marcus-Tardos method (see [A. Marcus, G. Tardos, Excluded permutation matrices and the Stanley-Wilf conjecture. J. Combin. Theory Ser. A 107 (2004) 153-160]) to prove that, if a hereditary property of partitions P has super-exponential speed, then, for every k-permutation π, P contains the partition of [2 k] with parts {{i, π (i) + k} : i ∈ [k]}. We also prove a similar jump, from exponential to factorial, in the possible speeds of monotone properties of ordered graphs, and of hereditary properties of ordered graphs not containing large complete, or complete bipartite ordered graphs. Our results generalize the Stanley-Wilf conjecture on the number of n-permutations avoiding a fixed permutation, which was recently proved by the combined results of Klazar [M. Klazar, The Füredi-Hajnal conjecture implies the Stanley-Wilf conjecture, in: D. Krob, A.A. Mikhalev, A.V. Mikhalev (Eds.), Formal Power Series and Algebraic Combinatorics, Springer, Berlin, 2000, pp. 250-255] and Marcus and Tardos [A. Marcus, G. Tardos, Excluded permutation matrices and the Stanley-Wilf conjecture, J. Combin. Theory Ser. A 107 (2004) 153-160]. Our main results follow from a generalization to ordered hypergraphs of the theorem of Marcus and Tardos.
UR - http://www.scopus.com/inward/record.url?scp=33748538660&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33748538660&partnerID=8YFLogxK
U2 - 10.1016/j.ejc.2006.05.004
DO - 10.1016/j.ejc.2006.05.004
M3 - Article
AN - SCOPUS:33748538660
SN - 0195-6698
VL - 27
SP - 1263
EP - 1281
JO - European Journal of Combinatorics
JF - European Journal of Combinatorics
IS - 8 SPEC. ISS.
ER -