Introduction - University of South Florida.pdfVIP

THE ASYMPTOTIC NUMBER OF TRIPLE SYSTEMS NOT CONTAINING A FIXED ONE ˇ ¨ BRENDAN NAGLE AND VOJTECH RODL Abstract. For a fixed 3-uniform hypergraph F , call a hypergraph F -free if it contains no subhypergraph isomorphic to F . Let ex(n, F ) denote the size of a largest F -free hypergraph G ⊆ [n]3 . Let Fn (F ) denote the number of distinct labelled F -free G ⊆ [n]3 . We show that Fn (F ) = 2ex(n,F )+o(n3 ) , and discuss related problems. 1. Introduction For a finite s-uniform hypergraph F , let F orbn (F ) denote the set of all s-uniform labelled hypergraphs on n vertices which do not contain F as a subhypergraph. In this paper, we will be interested in estimating the cardinality Fn (F ) of the set F orbn (F ). Let ex(n, F ) be the Tur´an number of F , i.e. the maximum number of edges which an s-uniform hypergraph on n vertices may have while not containing F as a subgraph. It turns out that the problem of estimating Fn (F ) is closely related to the problem of finding Tur´an numbers ex(n, F ). For s = 2, it was proved in [EFR] that ex(n,F )(1+o(1)) (1− 1 ) n (1+o(1)) ( ) Fn (F ) = 2 = 2 χ(F )−1 2 (1) provided χ(F ) 2. As noted in [EFR], it seems likely that Fn (F ) = 2ex(n,F )(1+o(1)) holds for bipartite F as well. However, this is not even known for F = C , the cycle