The number of hypergraphs without linear cycles

摘要

The r-uniform linear k-cycle C-k(r) is the r-uniform hypergraph on k(r - 1) vertices whose edges are sets of r consecutive vertices in a cyclic ordering of the vertex set chosen in such a way that every pair of consecutive edges share exactly one vertex. Here, we prove a balanced supersaturation result for linear cycles which we then use in conjunction with the method of hypergraph containers to show that for any fixed pair of integers r, k = 3, the number of C-k(r)-free r-uniform hypergraphs on n vertices is 2(circle dot(nr-1)), thereby settling a conjecture due to Mubayi and Wang from 2017. (C) 2018 Elsevier Inc. All rights reserved.