## Abstract

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,Kr)+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_{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^{Θ(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.

Original language | English (US) |
---|---|

Pages (from-to) | 216-234 |

Number of pages | 19 |

Journal | Journal of Combinatorial Theory. Series B |

Volume | 157 |

DOIs | |

State | Published - Nov 2022 |

## Keywords

- Counting problems
- Forbidden configurations
- Hypergraphs

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics