2021/07/30 by József Balogh, Felix Christian Clemen, Balogh, József +3
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2107.14798
openalex publication_date 2021/07/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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,…,\binomkr \ 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.