کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4654947 1632841 2006 19 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Hereditary properties of partitions, ordered graphs and ordered hypergraphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Hereditary properties of partitions, ordered graphs and ordered hypergraphs
چکیده انگلیسی

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 PP has super-exponential speed, then, for every kk-permutation ππ, PP contains the partition of [2k][2k] with parts {{i,π(i)+k}:i∈[k]}{{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 nn-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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 27, Issue 8, November 2006, Pages 1263–1281
نویسندگان
, , ,