## “2019 Combinatorics Workshop” was held from August 13 to August 15, 2019 at Incheon.

The 2019 Combinatorics Workshop (2019 조합론 학술대회) was held from August 13, 2019 to August 15, 2019 at the SKYPARK Hotel, Songdo, Incheon. There were 16 talks.

### Plenary Speaker

• Mihyun Kang (강미현), Graz University of Technology

### Keynote Speakers

• Jaehoon Kim (김재훈), KAIST
• Seung Jin Lee (이승진), Seoul National University
• Meesue Yoo (유미수), Dankook University

### Invited Speakers

• Eun-Kyung Cho (조은경), Hankuk University of Foreign Studies
• Soogang Eoh (어수강), Seoul National University
• JiSun Huh (허지선), Sungkyunkwan University
• Jihyeug Jang (장지혁), Sungkyunkwan University
• Dong Yeap Kang (강동엽), KAIST and IBS Discrete Mathematics Group
• Min Jeong Kang (강민정), Incheon National University
• Dabeen Lee (이다빈), IBS Discrete Mathematics Group
• Kang-Ju Lee (이강주), Seoul National University
• Myeonghwan Lee (이명환), Incheon National University
• Jihye Park (박지혜), Yeungnam University
• Sun-mi Yun (윤선미), Sungkyunkwan University

## 2019 Combinatorics Workshop

The annual conference on Combinatorics Workshop (조합론 학술대회) began in 2004 by the Yonsei University BK21 Research Group. This year it will take place in Songdo, Incheon, August 13-15, 2019.

Due to the capacity (50 persons) of the place, we are able to limit your registration. In principle, registration is on a first-come, first-served basis.

• Title 2019 Combinatorics Workshop (2019 조합론 학술대회)
• Date August 13-15 (Tue-Thu), 2019
• Venue Hotel Skypark, Songdo, Incheon
• Web https://cw2019.combinatorics.kr

We are going to

• give six 50-minute talks and ten 25-minute talks in Korean.
• distribute the program and abstracts of CW2019.
• provide for the accommodations for all participants.
• provide for six meals (two breakfasts, two luncheons, one dinner, and one banquet) for all participants.

# Invited Speakers

• Eun-Kyung Cho, Hankuk University of Foreign Studies
• Soogang Eoh, Seoul National University
• JiSun Huh, Sungkyunkwan University
• Jihyeug Jang, Sungkyunkwan University
• Dong Yeap Kang, KAIST and IBS Discrete Mathematics Group
• Min Jeong Kang, Incheon National University
• Dabeen Lee, IBS Discrete Mathematics Group
• Kang-Ju Lee, Seoul National University
• Myeonghwan Lee, Incheon National University
• Jihye Park, Yeungnam University
• Sun-mi Yun, Sungkyunkwan University

# Organizing Committee

• Committee of Discrete Mathematics, The Korean Mathematical Society (Chair: Seog-Jin Kim, Konkuk University)

• IBS Discrete Mathematics Group
• NRF (National Research Foundation of Korea)

## “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.