Hereditary properties of partitions, ordered graphs and ordered hypergraphs

DOI10.1016/J.EJC.2006.05.004MaRDI QIDQ850077zbMATH OpenOpenAlexFDO

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

Publication date 15 November 2006

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0702351

zbMATH Keywords

jump in speed speed of properties Stanley-Wilf conjecture strongly monotone properties

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Extremal problems in graph theory (05C35) Hypergraphs (05C65)

Abstract: In this paper we use the Klazar-Marcus-Tardos method to prove that if a hereditary property of partitions P has super-exponential speed, then for every k-permutation pi, P contains the partition of [2k] with parts {i, pi(i) + k}, where 1 <= 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 and of Marcus and Tardos. Our main results follow from a generalization to ordered hypergraphs of the theorem of Marcus and Tardos.

Review text

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.

Recommendations

Cites work

Cited in

(19)

This page was built for publication: Hereditary properties of partitions, ordered graphs and ordered hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q850077)