Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: Counting Pattern-free Set Partitions II: Noncrossing and Other Hypergraphs. | Counting Pattern-free Set Partitions II Noncrossing and Other Hypergraphs Martin Klazar Department of Applied Mathematics Charles University Malostranské námẽstí 25 118 00 Praha Czech Republic klazar@ Submitted January 28 2000 Accepted May 23 2000. Dedicated to the memory of Rodica Simion Abstract A multi hypergraph H with vertices in N contains a permutation p a1a2 . .ak 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 Hp i k ai 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 cn . The latter part generalizes the Stanley-Wilf conjecture on permutations. Using generalized Davenport-Schinzel sequences we prove the conjectures with weaker bounds O n 3 n and O 3 n n where 3 n 1 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. 2000 MSC Primary 05A05 05A15 05A18 05C65 05D05 Secondary 03D20 05C30 11B83. Support of the grant GAUK 158 99 is gratefully acknowledged. THE ELECTRONIC .JOURNAL OF COMBINATORICS 7 2000 R34 2 1 Notation conjectures and motivation We shall investigate numbers and sizes of pattern-free hypergraphs. A hypergraph H is a finite multiset of finite nonempty subsets of N 1 2 . . More explicitly H Hi i 2 I where the edges Hi Hi c N and the index set I are finite. If Hi Hj we say that the edges Hi and Hj are parallel. Simple hypergraphs have no parallel edges with i j. The union of all edges is denoted u H. The elements of u H c N are called vertices. Two isomorphic hypergraphs Hl and H2 are considered as identical only if they are isomorphic via an increasing mapping F uH1 UH2 otherwise they are distinct. We write I
