Counting r-graphs without forbidden configurations

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

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)216-234
Number of pages19
JournalJournal of Combinatorial Theory. Series B
Volume157
DOIs
StatePublished - Nov 2022

Keywords

  • Counting problems
  • Forbidden configurations
  • Hypergraphs

ASJC Scopus subject areas

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

Fingerprint

Dive into the research topics of 'Counting r-graphs without forbidden configurations'. Together they form a unique fingerprint.

Cite this