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.

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
PDF BibTeX Cite
Full Text: EMIS EuDML