Counting $r$-graphs without forbidden configurations

József Balogh, Felix Christian Clemen, Letícia Mattos

Published 2021-07-30Version 1

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\H{o}s, Kleitman and Rothschild, who showed that the number of $K_r$-free graphs on $n$ vertices is $2^{\text{ex}(n,K_r)+o(n^2)}$. Their work was later extended to forbidding graphs as induced subgraphs by Pr\"omel and Steger. Here, we consider one of the most basic counting problems for $3$-graphs. Let $E_1$ be the $3$-graph with $4$ vertices and $1$ edge. What is the number of induced $\{K_4^3,E_1\}$-free $3$-graphs on $n$ vertices? We show that the number of such $3$-graphs is of order $n^{\Theta(n^2)}$. More generally, we determine asymptotically the number of induced $\mathcal{F}$-free $3$-graphs on $n$ vertices for all families $\mathcal{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 \in L$ edges on any set of $k$ vertices, where $L \subseteq \big \{0,1,\ldots,\binom{k}{r} \big\}$ 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.