TY - JOUR

T1 - Counting r-graphs without forbidden configurations

AU - Balogh, József

AU - Clemen, Felix Christian

AU - Mattos, Letícia

N1 - Funding Information:
Research is partially supported by NSF grants DMS-1764123 and RTG DMS-1937241, the Arnold O. Beckman Research Award (UIUC Campus Research Board RB 18132), the Langan Scholar Fund (UIUC RB 18132), and the Simons Fellowship.Research is partially supported by the Arnold O. Beckman Research Award (UIUC Campus Research Board RB 18132).Research is funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany's Excellence Strategy – The Berlin Mathematics Research Center MATH+ (EXC-2046/1, project ID: 390685689).
Publisher Copyright:
© 2022 Elsevier Inc.

PY - 2022/11

Y1 - 2022/11

N2 - 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.

AB - 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.

KW - Counting problems

KW - Forbidden configurations

KW - Hypergraphs

UR - http://www.scopus.com/inward/record.url?scp=85135705558&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85135705558&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2022.07.001

DO - 10.1016/j.jctb.2022.07.001

M3 - Article

AN - SCOPUS:85135705558

SN - 0095-8956

VL - 157

SP - 216

EP - 234

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -