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 Kr-free graphs on n vertices is 2ex(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 E1 be the 3-graph with 4 vertices and 1 edge. What is the number of induced {K43,E1}-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