Counting r-graphs without forbidden configurations

One of the major problems in combinatorics is to determine the number of r-uniform hypergraphs (r-graphs) on n vertices which are free of certain forbidden structures. This problem dates back to the work of Erdős, Kleitman and Rothschild, who showed that the number of K_r-free graphs on n vertices is 2^{ex(n,K_r)+o(n2)}. Their work was later extended to forbidding graphs as induced subgraphs by Prömel and Steger. Here, we consider one of the most basic counting problems for 3-graphs. Let E₁ be the 3-graph with 4 vertices and 1 edge. What is the number of induced {K₄³,E₁}-free 3-graphs on n vertices? We show that the number of such 3-graphs is of order n^Θ(n2). More generally, we determine asymptotically the number of induced F-free 3-graphs on n vertices for all families F of 3-graphs on 4 vertices. We also provide upper bounds on the number of r-graphs on n vertices which do not induce i∈L edges on any set of k vertices, where L⊆{0,1,…,(kr)} is a list which does not contain 3 consecutive integers in its complement. Our bounds are best possible up to a constant multiplicative factor in the exponent when k=r+1. The main tool behind our proof is counting the solutions of a constraint satisfaction problem.