Hereditary properties of partitions, ordered graphs and ordered hypergraphs (Q850077)

This paper presents some of a cluster of results regarding the speed of a monotone property of matrices, graphs, or hypergraphs: given a property \(\mathcal P\), and given that \(\mathcal P_n\) is the set of all \(n\)-hypergraphs of property \(\mathcal P\), its speed is the function \(n \mapsto \mathcal | P_n| \). Call a property of hypergraphs strongly monotone if, for any \(\mathcal H = \langle V, \{ e_1, \dots, e_m \} \rangle\) and \(\mathcal K = \langle V', \{ f_1, \dots, f_m \} \rangle\) such that \(V \subseteq V'\) and \(e_i \subseteq f_i\) for each \(i\) (and \(| e_i| \geq 2\) for each \(i\)), \(\mathcal K\) satisfies \(\mathcal P\), then so does \(\mathcal H\). And a hypergraph is ordered if we include a linear order. The main result, which was conjectured by \textit{M. Klazar} [Electron. J. Comb. 7, Research paper R34, 25 p. (2000); printed version J. Comb. 7 (2000; Zbl 0944.05002)] and proven independently in [\textit{M. Klazar} and \textit{A. Marcus}, Extensions of the linear bound in the Füredi-Hajnal conjecture, posted at Arxiv. Math.], is that if a strongly monotone property of ordered hypergraphs has a super-exponential speed, then its speed is factorial. Specifically, if for each \(c > 0\), there exists \(N\) such that \(| \mathcal P_N| > c^N\), then \(| \mathcal P_n| \geq n^{n/2 + o(n)}\). The proof relies on a graph representation of permutations: for a permutation \(\pi\) on \([k]\), let \(H(\pi)\) be the ordered graph on the vertex set \([2k]\) (with the usual ordering) whose edges are the pairs \(\{ i, \pi(i) + k \}\). In the first half of the proof, it is shown that any strongly monotone property that admits all the \(H(\pi)\) grows factorially; and in the second half, that any strongly monotone property that grows super-exponentially contains all the \(H(\pi)\). The paper presents several related results, which would be subsumed by a conjecture presented in the paper, which relies on the narrower notion of a hereditary property: a property is hereditary if the definition for strong monotonicity holds, except that ``\(e_i \subseteq f_i\)'' is replaced by ``\(e_i = f_i \cap V\).'' The conjecture is that a hereditary property that grows with super-exponential speed grows factorially.