Seminar: October 1

Travis Johnston, Universtiy of South Carolina

Connecting Turan Problems on Hypergraphs to Forbidden Subposet Problems

What has become known as Turan problems are those of the following flavor: given a graph (or r-uniform hypergraph) H, how many edges can a host graph G have if it doesn't contain H as a subgraph? This question has been widely studied. Turan, and later Erdos, Stone, and Simonovits, answered the question for simple graphs. However, determining the Turan density of even 3-uniform hypergraphs has proved to be very difficult.

A seemingly similar question can be asked about posets. Let P be a subposet of the boolean lattice. How many sets can a set family F (a subset of the boolean lattice) contain, if it doesn't contain a copy of P? The first result in this area is due to Sperner who showed that an inclusion-free family of sets has at most n choose n/2 members. Again, many different people have asked, and with varying success, answered this question for a variety of posets P. Several remarkably simple posets have resisted the efforts of many: the diamond D_2, the 6-crown, and the 10-crown for example.

When viewed as posets, r-uniform hypergraphs are all anti-chains. So, while the two questions seem very similar, methods and results rarely translate between the two questions. In this talk we introduce Turan problems on non-uniform hypergraphs. We extend several classical results for uniform hypergraphs. Additionally, we demonstrate how results about the Turan density of non-uniform hypergraphs can translate to results about forbidden posets. This allows us to attack forbidden poset problems graph theory tools including Razborov's flag algebra method. This is joint work with my advisor Linyuan Lu.