zbMATH — the first resource for mathematics

Counting pattern-free set partitions. II: Noncrossing and other hypergraphs. (English) Zbl 0944.05002
Electron. J. Comb. 7, No. 1, Research paper R34, 25 p. (2000); printed version J. Comb. 7, No. 2 (2000).
[For Part I see Eur. J. Comb. 21, 367-378 (2000).]
Summary: A (multi)hypergraph $${\mathcal H}$$ with vertices in $$\mathbb{N}$$ contains a permutation $$p=a_1a_2\ldots a_k$$ of $$1, 2, \ldots, k$$ if one can reduce $${\mathcal H}$$ by omitting vertices from the edges so that the resulting hypergraph is isomorphic, via an increasing mapping, to $${\mathcal H}_p=(\{i, k+a_i\}:\;i=1, \ldots, k)$$. We formulate six conjectures stating that if $${\mathcal H}$$ has $$n$$ vertices and does not contain $$p$$ then the size of $${\mathcal H}$$ is $$O(n)$$ and the number of such $${\mathcal H}$$s 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\beta(n))$$ and $$O(\beta(n)^n)$$, where $$\beta(n)\rightarrow\infty$$ 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.

MSC:
 05A05 Permutations, words, matrices 05A18 Partitions of sets 05D05 Extremal set theory 05C30 Enumeration in graph theory 03D20 Recursive functions and relations, subrecursive hierarchies 11B83 Special sequences and polynomials 05A15 Exact enumeration problems, generating functions 05C65 Hypergraphs
Full Text: