On April 1, 2022, Hong Liu from the University of Warwick is appointed as the Chief Investigator to lead a new group, the IBS Extremal Combinatorics and Probability Group (ECOPRO), in the Center for Mathematical and Computational Sciences. To enhance our collaboration, the IBS Discrete Mathematics Group will move to the 3rd floor of the theory building on April 19-21 to share the space with the Extremal Combinatorics and Probability Group.

## “2021 Combinatorics Workshop” was held from December 20 to December 22, 2021 at Yangpyeong

The 2021 Combinatorics Workshop (2021 조합론 학술대회) was held from December 20, 2021 to December 22, 2021 at the Bloomvista, Yangpyeong. There were 5 invited talks and 12 contributed talks.

### Invited Speakers

- Dongsu Kim, KAIST
- Joonkyung Lee, Hanyang University
- Hong Liu, University of Warwick, UK
- Suil O, SUNY Korea
- Seonjeong Park, Jeonju University

### Speakers of the contributed talks

- Jungho Ahn, KAIST / IBS DIMAG
- Jin-Hwan Cho, NIMS
- Linda Cook, IBS DIMAG
- Cheolwon Heo, Sungkyunkwan University
- Seonghyuk Im, KAIST
- Hyobin Kim, Kyungpook National University
- Minki Kim, IBS DIMAG
- Hyemin Kwon, Ajou University
- Hyunwoo Lee, KAIST
- Sang June Lee, Kyung Hee University
- Jaehyeon Seo, KAIST
- Semin Yoo, KIAS

### Organizing Committee

- Jeong-Ok Choi, GIST
- Sang-il Oum, IBS DIMAG / KAIST
- Heesung Shin, Inha University

### Participants (50 people, all of whom are fully vaccinated against COVID-19)

- Jungho Ahn,
, KAIST / IBS DIMAG**speaker** - Sejeong Bang, session chair, Yeungnam University
- Rutger Campbell, IBS DIMAG
- Debsoumya Chakraborti, IBS DIMAG
- Eun-Kyung Cho, Hankuk University of Foreign Studies
- Hyunsoo Cho, Ewha Womans University
- Jin-Hwan Cho,
, NIMS**speaker** - Jeong-Ok Choi,
/session chair, GIST**organizer** - Linda Cook,
, IBS DIMAG**speaker** - Taehyun Eom, KAIST
- Cheolwon Heo,
, Sungkyunkwan University**speaker** - Seonghyuk Im,
, KAIST**speaker** - Jihyeug Jang, Sungkyunkwan University
- Dosang Joe, NIMS
- Donggyu Kim, KAIST / IBS DIMAG
- Donghyun Kim, Sungkyunkwan University
- Dongsu Kim,
, KAIST**invited speaker** - Hyobin Kim,
, Kyungpook National University**speaker** - Jaehoon Kim, KAIST
- Jang Soo Kim, Sungkyunkwan University
- Jinha Kim, IBS DIMAG
- Minki Kim,
, IBS DIMAG**speaker** - Seog-Jin Kim, session chair, Konkuk University
- Doowon Koh, Chungbuk National University
- Hyemin Kwon,
, Ajou University**speaker** - O-joung Kwon, Incheon National University / IBS DIMAG
- Dabeen Lee, IBS DIMAG
- Duksang Lee, KAIST / IBS DIMAG
- Hyunwoo Lee,
, KAIST**speaker** - Joonkyung Lee,
, Hanyang University**invited speaker** - Sang June Lee,
, Kyung Hee University**speaker** - Seung Jin Lee, Seoul National University
- Hong Liu,
, University of Warwick, UK**invited speaker** - Ben Lund, IBS DIMAG
- Suil O,
, SUNY Korea**invited speaker** - Jaeseong Oh, KIAS
- Sang-il Oum,
IBS DIMAG / KAIST**organizer**/session chair, - Jae Hyun Park, Kyung Hee University
- Seonjeong Park,
**invited**, Jeonju University**speaker** - Jaehyeon Seo,
, KAIST**speaker** - Seunghyun Seo, session chair, Kangwon National University
- Heesung Shin,
/session chair, Inha University**organizer** - Mark Siggers, Kyungpook National University
- Jaebum Sohn, Yonsei University
- Minho Song, Sungkyunkwan University
- U-keun Song, Sungkyunkwan University
- Jeong Hyun Sung, Seoul National University
- Tuan Tran, IBS DIMAG
- Sounggun Wee, KAIST / IBS DIMAG
- Semin Yoo,
, KIAS**speaker**

### Host and Sponsors

## Hong Liu is moving to IBS as a Chief Investigator to start the IBS Extremal Combinatorics and Probability Group (ECOPRO) on April 2022 and is hiring up to 5 postdocs in all fields of combinatorics with emphasis on extremal and probabilistic combinatorics, graph theory, Ramsey theory, combinatorial number theory and discrete geometry

We are very excited to learn that Prof. Hong Liu from University of Warwick, UK will move to the Institute for Basic Science (IBS) as a Chief Investigator (CI) to lead a new group called the Extremal Combinatorics and Probability Group (ECOPRO) on April 2022. This new group will be also located in the IBS headquarter and is expected to work closely with the IBS Discrete Mathematics Group (DIMAG). Both DIMAG and ECOPRO belong to the IBS Center for Mathematical and Computational Sciences together with the Data Science Group and the Biomedical Mathematics Group and we share the staff members.

The website was made recently. https://www.ibs.re.kr/ecopro/

Yesterday, the IBS Extremal Combinatorics and Probability Group (ECOPRO) posted the hiring announcement for up to 5 postdocs. Here are a few paragraphs from the announcement.

The Extremal Combinatorics and Probability Group (ECOPRO) at the Institute for Basic Science (IBS) in Daejeon, South Korea invites applications for 5 postdoctoral research fellowship positions. ECOPRO is a new research group that will be officially launched in April 1, 2022 at IBS, led by Prof. Hong Liu. We welcome highly motivated postdoc researchers with outstanding research potential in all fields of combinatorics with emphasis on extremal and probabilistic combinatorics, graph theory, Ramsey theory, combinatorial number theory and discrete geometry. This appointment is for 2 years with possible 1 year extension contingent upon the outstanding performance of the researcher. The starting salary is no less than 57,000,000 KRW (about 48,400 USD or 42,800 EUR). The appointment starting date is flexible: between April 1 and Oct 1, 2022. This is a purely research position and will have no teaching duties.

A complete application packet should include

- Curriculum vitae including a publication list (PDF format)
- Research statement (PDF format)
- Up to 3 best papers or preprints
- Consent to Collection and Use of Personal Information (Please convert to a PDF file)
- Two or three recommendation letters.

For full consideration, applicants should email items 1, 2, 3, and 4 and arrange their recommendation letters emailed to ecopro@ibs.re.kr by **January 14, 2022**.

Recommendations letters forwarded by an applicant will not be considered.

## Hong Liu, Sublinear expander and embeddings sparse graphs

A notion of sublinear expander has played a central role in the resolutions of a couple of long-standing conjectures in embedding problems in graph theory, including e.g. the odd cycle problem of Erdős and Hajnal that the harmonic sum of odd cycle length in a graph diverges with its chromatic number. I will survey some of these developments.

## Hong Liu gave a talk on the extremal problem of finding nested cycles with no geometric crossing at the Discrete Math Seminar

On March 22, 2021 at the Discrete Math Seminar, Hong Liu (刘鸿) from the University of Warwick gave a talk on the extremal problem of having nested cycles with no geometric crossing by using the sublinear expanders. The title of his talk was “Nested cycles with no geometric crossing“.

## Extremal and Probabilistic Combinatorics (2021 KMS Spring Meeting)

A special session “Extremal and Probabilistic Combinatorics” at the 2021 KMS Spring Meeting is organized by Tuan Tran.

URL: https://www.kms.or.kr/meetings/spring2021/

## Speakers and Schedule

All talks are on April 30.

- [9:00 am]
**Joonkyung Lee (이준경)**, University College London*Majority dynamics on sparse random graphs*

- [9:30 am]
**Dong Yeap Kang (강동엽)**, Unversity of Birmingham*The Erdős-Faber-Lovász conjecture and related results*

- [10:00 am]
**Jinyoung Park (박진영)**, IAS*The threshold for the square of a Hamilton cycle*

- [10:50 am]
**Debsoumya Chakraborti**, IBS Discrete Mathematics Group*Generalized graph saturation*

- [11:20 am]
**Jaehoon Kim (김재훈)**, KAIST*Resolution of the Oberwolfach problem*

- [11:50 am]
**Hong Liu**, University of Warwick*Sublinear expanders and its applications*

## Abstracts

#### Debsoumya Chakraborti, Generalized graph saturation

Graph saturation is one of the oldest areas of investigation in extremal combinatorics. A graph G is called *F-saturated* if G does not contain a subgraph isomorphic to F, but the addition of any edge creates a copy of F. We resolve one of the most fundamental questions of minimizing the number of cliques of size r in a $K_s$-saturated graph for all sufficiently large numbers of vertices, confirming a conjecture of Kritschgau, Methuku, Tait and Timmons. We further prove a corresponding stability result. This talk will be based on joint work with Po-Shen Loh.

#### Jaehoon Kim (김재훈), Resolution of the Oberwolfach problem

The Oberwolfach problem, posed by Ringel in 1967, asks for a decomposition of $K_{2n+1}$ into edge-disjoint copies of a given 2-factor. We show that this can be achieved for all large n. We actually prove a significantly more general result, which allows for decompositions into more general types of factors.

#### Dong Yeap Kang (강동엽), The Erdős-Faber-Lovász conjecture and related results

A hypergraph is linear if every pair of two distinct edges shares at most one vertex. A longstanding conjecture by Erdős, Faber, and Lovász in 1972, states that the chromatic index of any linear hypergraph on n vertices is at most n.

In this talk, I will present the ideas to prove the conjecture for all large n. This is joint work with Tom Kelly, Daniela Kühn, Abhishek Methuku, and Deryk Osthus.

#### Joonkyung Lee (이준경), Majority dynamics on sparse random graphs

*Majority dynamics* on a graph G is a deterministic process such that every vertex updates its {-1,1}-assignment according to the majority assignment on its neighbor simultaneously at each step. Benjamini, Chan, O’Donnell, Tamuz and Tan conjectured that, in the Erdős-Rényi random graph G(n,p), the random initial {-1,1}-assignment converges to the unanimity with high probability whenever p>> 1/n.

This conjecture was firstly confirmed for $p>Cn^{-1/2}$ for a large constant C>0 by Fountoulakis, Kang and Makai. Although this result has been reproved recently by Tran and Vu and by Berkowitz and Devlin, none of them managed to extend it beyond the barrier $p>Cn^{-1/2}$. We prove the conjecture for sparser random graphs G(n,p), where $Dn^{-3/5}\log n < p < C n^{-1/2}$ with a large constant D>0.

Joint work with Debsoumya Chakraborti, Jeong Han Kim and Tuan Tran.

#### Hong Liu, Sublinear expanders and its applications

I will review the history of sublinear expander and present some recent applications, which lead to resolutions of several long-standing problems in sparse graphs embeddings.

#### Jinyoung Park (박진영), The threshold for the square of a Hamilton cycle

We will talk about a recent result of Jeff Kahn, Bhargav Narayanan, and myself stating that the threshold for the random graph G(n,p) to contain the square of a Hamilton cycle is $1/\sqrt n$, resolving a conjecture of Kühn and Osthus from 2012. The proof idea is motivated by the recent work of Frankston and the three aforementioned authors on a conjecture of Talagrand — “a fractional version of Kahn-Kalai expectation threshold conjecture.”

## Hong Liu (刘鸿), Nested cycles with no geometric crossing

In 1975, Erdős asked the following question: what is the smallest function $f(n)$ for which all graphs with $n$ vertices and $f(n)$ edges contain two edge-disjoint cycles $C_1$ and $C_2$, such that the vertex set of $C_2$ is a subset of the vertex set of $C_1$ and their cyclic orderings of the vertices respect each other? We prove the optimal linear bound $f(n)=O(n)$ using sublinear expanders.

This is joint work with Irene Gil Fernández, Jaehoon Kim and Younjin Kim.

## Hong Liu presented his result with R. Montgomery on the resolution the odd cycle problem of Erdős and Hajnal at the Discrete Math Seminar

On December 8, 2020, Hong Liu from University of Warwick presented a talk on his recent work with Richard Montgomery, answering the odd cycle problem of Erdős and Hajnal (1981). The title of his talk is “A solution to Erdős and Hajnal’s odd cycle problem“.

## Hong Liu (刘鸿), A solution to Erdős and Hajnal’s odd cycle problem

I will go over the history on the study of the set of cycle lengths of graphs with large average degree or chromatic number, and discuss recent work with Richard Montgomery on this topic. In particular, we will see the divergence of harmonic sum of odd cycle lengths in graphs with large chromatic number and the appearance of cycle lengths in very sparse sequences (such as powers of 2). The methods developed in this work allows also us to embed equally divided clique subdivisions, which was conjectured by Thomassen.

## Hong Liu (刘鸿), Cycles and trees in graphs (8/8)

This lecture series covers several different techniques on embedding paths/trees/cycles in (pseudo)random graphs/expanders as (induced) subgraphs.