Abstract:

A (multi)hypergraph H with vertices in  N contains a permutation p=a_1a_2... a_k of 1, 2, ..., k if one can reduce H by omitting vertices from the edges so that the resulting hypergraph is isomorphic, via an increasing mapping, to H_p=( {i, k+a_i}:  i=1, ..., k ). We formulate six conjectures stating that if H has n vertices and does not contain p then the size of H is O(n) and the number of such Hs is O(c^n). The latter part generalizes the Stanley-Wilf conjecture on permutations. Using generalized Davenport-Schinzel sequences, we prove the conjectures with weaker bounds O(n.b(n)) and O(b(n)^n), where b(n) -> infinity very slowly. We prove the conjectures fully if p first increases and then decreases or if p^{-1} decreases and then increases. For the cases p=12 (noncrossing structures) and p=21 (nonnested structures) we give many precise enumerative and extremal results, both for graphs and hypergraphs.