MATH Seminar
| Title: Turan-type problems for bipartite graphs and hypergraphs |
|---|
| Colloquium: Combinatorics |
| Speaker: Liana Yepremyan of University of Oxford |
| Contact: Dwight Duffus, dwightduffus@emory.edu |
| Date: 2019-02-22 at 4:00PM |
| Venue: MSC W301 |
| Download Flyer |
| Abstract: A central problem of extremal combinatorics is to determine the Turan number of a given graph or a hypergraph F, i.e. the maximum number of edges in an r-uniform hypergraph on n vertices that does not contain a copy of F. For graphs, the asymptotic answer to this question is given by the celebrated Erdos-Stone theorem. However, it is wide open for bipartite graphs and for hypergraphs. For bipartite graphs, a beautiful conjecture of Erdos and Simonovits says that every rational number between 1 and 2 must appear as an exponent of some Turan number. Despite decades of effort, there are only few families for which this conjecture is known to be true. We will discuss some recent progress on this as well as related so-called supersaturation problems. For hypergraphs, since the problem was introduced over sixty years ago, it has only been solved for relatively few hypergraphs F. Many of these results were found very recently by means of the stability method, which has brought new life to research in a challenging area. We will discuss a variation of this method utilizing the Lagrangian function (we call it local stability method) which gives a generic unified approach for obtaining exact Turan numbers from asymptotic results and allowed us to enlarge the list of known Turan numbers of hypergraphs, in particular solving a conjecture of Frankl and Furedi from the 80's. Various parts of the work are joint with Sergey Norin, Adam Bene Watts, Tao Jiang and Jie Ma. |
See All Seminars