Hereditary properties of partitions, ordered graphs and ordered hypergraphs

József Balogh, Béla Bollobás, Robert Morris

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1263-1281
Number of pages19
JournalEuropean Journal of Combinatorics
Volume27
Issue number8 SPEC. ISS.
DOIs
StatePublished - Nov 2006

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Hereditary properties of partitions, ordered graphs and ordered hypergraphs'. Together they form a unique fingerprint.

Cite this