Hong Liu gave a talk describing approximate structures of an n-vertex m-edge graph minimizing the number of cliques of size k at the Discrete Math Seminar

On May 26, 2020, Hong Liu from University of Warwick presented a talk on his recent work describing approximate structures of an n-vertex m-edge graph minimizing the number of cliques of size k. The title of his talk was “Asymptotic Structure for the Clique Density Theorem”.

Hong Liu (刘鸿), Asymptotic Structure for the Clique Density Theorem

The famous Erdős-Rademacher problem asks for the smallest number of r-cliques in a graph with the given number of vertices and edges. Despite decades of active attempts, the asymptotic value of this extremal function for all r was determined only recently, by Reiher [Annals of Mathematics, 184 (2016) 683-707]. Here we describe the asymptotic structure of all almost extremal graphs. This task for r=3 was previously accomplished by Pikhurko and Razborov [Combinatorics, Probability and Computing, 26 (2017) 138–160].

Hong Liu gave a talk on the conjecture of Mader about the topological minors in C4-free graphs at the discrete math seminar

On December 12, 2019, Hong Liu from University of Warwick gave a talk on the resolution of the conjecture of Mader on the existence of a complete topological minor under the condition of average degree for C4-free graphs at the discrete math seminar held at KAIST. The title of his talk was “A proof of Mader’s conjecture on large clique subdivisions in $C_4$-free graphs“.

Hong Liu, A proof of Mader’s conjecture on large clique subdivisions in $C_4$-free graphs

Given any integers $s,t\geq 2$, we show there exists some $c=c(s,t)>0$ such that any $K_{s,t}$-free graph with average degree $d$ contains a subdivision of a clique with at least $cd^{\frac{1}{2}\frac{s}{s-1}}$ vertices. In particular, when $s=2$ this resolves in a strong sense the conjecture of Mader in 1999 that every $C_4$-free graph has a subdivision of a clique with order linear in the average degree of the original graph. In general, the widely conjectured asymptotic behaviour of the extremal density of $K_{s,t}$-free graphs suggests our result is tight up to the constant $c(s,t)$. This is joint work with Richard Montgomery.

“2019-2 IBS One-Day Conference on Extremal Graph Theory” was held on August 12, 2019.

The 2019-2 IBS One-Day Conference on Extremal Graph Theory was held on August 12, 2019 at the IBS Discrete Mathematics Group. There were four talks. Here is a list of talks.

• Jaehoon Kim (김재훈), KAIST: Tree decompositions of graphs without large bipartite holes
• Hong Liu (刘鸿), University of Warwick: Recent advance in Ramsey-Turán theory
• Abhishek Methuku, IBS Discrete Mathematics Group: Bipartite Turán problems for ordered graphs
• Péter Pál Pach, Budapest University of Technology and Economics: On some applications of graph theory to number theoretic problems

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.