Letícia Mattos (UIUC)
Counting r-graphs without forbidden configurations*************************************************************************
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 Erdos, Kleitman and Rothschild, who showed that the number of K_r-free graphs on n vertices is 2^{ex(n,K_r)+o(n^2)}. Their work was later extended to forbidden induced graphs by Prömel and Steger. The results were stated in terms of a different notion of extremal number, which is not very well understood even for simple families of 3-graphs.
Here, we consider one of the most basic counting problems for 3-graphs. Let E_1 be 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?
In this talk, we show that the number of such 3-graphs is of order n^{Theta(n^2)}. More generally, we determine the number of induced F-free 3-graphs on n vertices for all families F of 3-graphs on 4 vertices.
The main tool behind our proof is a lemma which counts the number of solutions of a constraint satisfaction problem. This is based on a joint work with Balogh and Clemen.
