2019-2 IBS One-Day Conference on Extremal Graph Theory

Invited Speakers

• Jaehoon Kim (김재훈), KAIST
• Hong Liu (刘鸿), University of Warwick
• Abhishek Methuku, IBS Discrete Mathematics Group
• Péter Pál Pach, Budapest University of Technology and Economics

Schedule

August 12, Monday

11:00am-12:00pm Jaehoon Kim (김재훈): Tree decompositions of graphs without large bipartite holes

12:00pm-1:30pm Lunch

1:30pm-2:30pm Abhishek Methuku: Bipartite Turán problems for ordered graphs

3:00pm-4:00pm Péter Pál Pach: On some applications of graph theory to number theoretic problems

4:30pm-5:30pm Hong Liu: Recent advance in Ramsey-Turán theory

6:00pm-8:00pm Banquet

Abstract

Jaehoon Kim (김재훈), Tree decompositions of graphs without large bipartite holes

A recent result of Condon, Kim, Kühn and Osthus implies that for any $r\geq (\frac{1}{2}+o(1))n$, an $n$-vertex almost $r$-regular graph $G$ has an approximate decomposition into any collections of $n$-vertex bounded degree trees. In this talk, we prove that a similar result holds for an almost $\alpha n$-regular graph $G$ with any $\alpha>0$ and a collection of bounded degree trees on at most $(1-o(1))n$ vertices if $G$ does not contain large bipartite holes. This result is sharp in the sense that it is necessary to exclude large bipartite holes and we cannot hope for an approximate decomposition into $n$-vertex trees. This is joint work with Younjin Kim and Hong Liu.

Abhishek Methuku,  Bipartite Turán problems for ordered graphs

A zero-one matrix $M$ contains a zero-one matrix $A$ if one can delete rows and columns of $M$, and turn 1-entries into 0-entries such that the resulting matrix is $A$. The extremal number of $A$, denoted by $ex(n,A)$, is the maximum number of $1$-entries in an $n\times n$ sized matrix $M$ that does not contain $A$.

A matrix $A$ is column-$t$-partite (or row-$t$-partite), if it can be cut along the columns (or rows) into $t$ submatrices such that every row (or column) of these submatrices contains at most one $1$-entry. We prove that if $A$ is column-$t$-partite, then $\operatorname{ex}(n,A)<n^{2-\frac{1}{t}+\frac{1}{2t^{2}}+o(1)}$, and if $A$ is both column- and row-$t$-partite, then $\operatorname{ex}(n,A)<n^{2-\frac{1}{t}+o(1)}$, and this bound is close to being optimal. Our proof introduces a new density-increment-type argument which is combined with the celebrated dependent random choice method.

Results about the extremal numbers of zero-one matrices translate into results about the Turán numbers of bipartite ordered graphs. In particular, a zero-one matrix with at most $t$ 1-entries in each row corresponds to an ordered graph with maximum degree $t$ in one of its vertex classes. The aim of this talk is to establish general results about the extremal numbers of ordered graphs. Our results are partially motivated by a well known result of Füredi (1991) and Alon, Krivelevich, Sudakov (2003) stating that if $H$ is a bipartite graph with maximum degree $t$ in one of the vertex classes, then $\operatorname{ex}(n,H)=O(n^{2-\frac{1}{t}})$. This is joint work with Tomon.

Péter Pál Pach, On some applications of graph theory to number theoretic problems

How large can a set of integers be, if the equation $a_1a_2\dots a_h=b_1b_2\dots b_h$ has no solution consisting of distinct elements of this set? How large can a set of integers be, if none of them divides the product of $h$ others? How small can a multiplicative basis for $\{1, 2, \dots, n\}$ be? The first question is about a generalization of the multiplicative Sidon sets, the second one is of the primitive sets, while the third one is the multiplicative version of the well-studied analogue problem for additive bases.

In answering the above mentioned questions graph theory plays an important role and in most of our results not only the asymptotics are found, but very tight bounds are obtained for the error terms, as well. We will also discuss the counting version of these questions.

Hong Liu, Recent advance in Ramsey-Turán theory

We will talk about Ramsey-Turán theory and some recent development. More specifically, we will talk about graphs with $\alpha_r(G)=o(n)$, where $\alpha_r(G)$ is the largest size subset with no $K_r$. Two major open problems in this area from the 80s ask: (1) whether Bollobas-Erdos graph can be generalised to densities other than $1/2$; (2) whether the asymptotic extremal structure for $\alpha_r(G)$ resembles that of $\alpha_2(G)$. We settle the first conjecture by constructing Bollobas-Erdos type graph with density $a$ for arbitrary rational number $a\le 1/2$; and refute the second conjecture by witnessing asymptotic extremal structures that are drastically different from the $\alpha_2(G)$ problem via a ”Mobius product” construction.

Joint work with Christian Reiher, Maryam Sharifzadeh, and Katherine Staden.