“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

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

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

  • Jungho Ahn, speaker, KAIST / IBS DIMAG
  • 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, speaker, NIMS
  • Jeong-Ok Choi, organizer/session chair, GIST
  • Linda Cook, speaker, IBS DIMAG
  • Taehyun Eom, KAIST
  • Cheolwon Heo, speaker, Sungkyunkwan University
  • Seonghyuk Im, speaker, KAIST
  • Jihyeug Jang, Sungkyunkwan University
  • Dosang Joe, NIMS
  • Donggyu Kim, KAIST / IBS DIMAG
  • Donghyun Kim, Sungkyunkwan University
  • Dongsu Kim, invited speaker, KAIST
  • Hyobin Kim, speaker, Kyungpook National University
  • Jaehoon Kim, KAIST
  • Jang Soo Kim, Sungkyunkwan University
  • Jinha Kim, IBS DIMAG
  • Minki Kim, speaker, IBS DIMAG
  • Seog-Jin Kim, session chair, Konkuk University
  • Doowon Koh, Chungbuk National University
  • Hyemin Kwon, speaker, Ajou University
  • O-joung Kwon, Incheon National University / IBS DIMAG
  • Dabeen Lee, IBS DIMAG
  • Duksang Lee, KAIST / IBS DIMAG
  • Hyunwoo Lee, speaker, KAIST
  • Joonkyung Lee, invited speaker, Hanyang University
  • Sang June Lee, speaker, Kyung Hee University
  • Seung Jin Lee, Seoul National University
  • Hong Liu, invited speaker, University of Warwick, UK
  • Ben Lund, IBS DIMAG
  • Suil O, invited speaker, SUNY Korea
  • Jaeseong Oh, KIAS
  • Sang-il Oum, organizer/session chair, IBS DIMAG / KAIST
  • Jae Hyun Park, Kyung Hee University
  • Seonjeong Park, invited speaker, Jeonju University
  • Jaehyeon Seo, speaker, KAIST
  • Seunghyun Seo, session chair, Kangwon National University
  • Heesung Shin, organizer/session chair, Inha University
  • 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, speaker, KIAS

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

  1. Curriculum vitae including a publication list (PDF format)
  2. Research statement (PDF format)
  3. Up to 3 best papers or preprints
  4. Consent to Collection and Use of Personal Information (Please convert to a PDF file)
  5. 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.

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.

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 (刘鸿), 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.