Turan-type problems for bipartite graphs and hypergraphs


Liana Yepremyan


Oxford University


Thu, 09/05/2019 - 1:00pm


RC-4082, The Red Centre, UNSW


A central problem of extremal combinatorics is to determine the Turán 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 a 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 Turán 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 Turán numbers from asymptotic results and allowed us to enlarge the list of known Turán numbers of hypergraphs, in particular solving a conjecture of Frankl and Füredi from the 80's.

Various parts of the work are joint with Sergey Norin, Adam Bene Watts, Tao Jiang and Jie Ma.

School Seminar Series: