On July 14, 2024, Two of our former members, Dong Yeap Kang (강동엽) and Abhishek Methuku, and their collaborators (Tom Kelly, Daniela Kühn, and Deryk Osthus) received the 2024 Frontiers of Science Award (FSA) at the International Congress for Basic Science held in Beijing from July 14 to July 26, 2024, for their paper on the proof of Erdős-Faber-Lovász conjecture published in Annals of Mathematics. Dong Yeap Kang and Abhishek Methuku are former members of the IBS Discrete Mathematics Group. Congratulations!

## Congratulations Dong Yeap Kang (강동엽) for receiving the Sangsan Prize for Young Mathematicians (상산젊은수학자상) from the Korean Mathematical Society

Our former member, Dr. Dong Yeap Kang (강동엽), has been selected as one of the three winners of this year receiving the Sangsan Prize for Young Mathematicians (상산젊은수학자상) from the Korean Mathematical Society. This prize is for those with outstanding academic achievements in mathematics who are within 5 years of receiving their Ph.D. degree. Dr. Kang was a research student of the IBS Discrete Mathematics Group and received his Ph.D. in 2020 from KAIST under the supervision of Sang-il Oum. He was a postdoctoral researcher at the University of Birmingham for 3 years and currently, he is a Young Scientist Fellow at the IBS Extremal Combinatorics and Probability Group. The award ceremony will be held on October 27, 2023 at the Seoul National University during the 2023 KMS Annual Meeting. Congratulations!

## Dong Yeap Kang (강동엽) gave a talk on the existence of a largest possible matching in a random subhypergraph of a k-uniform hypergraph with the codegree condition at the Discrete Math Seminar

On July 25, 2022, Dong Yeap Kang (강동엽) from the IBS Extremal Combinatorics and Probability Group gave a talk at the Discrete Math Seminar on the existence of a largest possible matching in a random subhypergraph of a k-uniform hypergraph with the codegree condition. The title of his talk was “Hamilton cycles and optimal matchings in a random subgraph of uniform Dirac hypergraphs.”

## Welcome Dong Yeap Kang (강동엽), a new member of the IBS Extremal Combinatorics and Probability Group

The IBS discrete mathematics group welcomes Dr. **Dong Yeap Kang (강동엽)**, a new research fellow at the IBS Extremal Combinatorics and Probability Group from June 16, 2023. Dr. Kang received his Ph.D. from the Department of Mathematical Science at KAIST in 2020 under the supervision of Prof. Sang-il Oum. Before joining the IBS Extremal Combinatorics and Probability Group, he was a research fellow at the University of Birmingham. He won the IBS Young Scientist Fellowship.

## Dong Yeap Kang (강동엽), Hamilton cycles and optimal matchings in a random subgraph of uniform Dirac hypergraphs

A *loose* cycle is a cyclic ordering of edges such that every two consecutive edges share exactly one vertex. A cycle is *Hamilton* if it spans all vertices. A *codegree* of a $k$-uniform hypergraph is the minimum nonnegative integer $t$ such that every subset of vertices of size $k-1$ is contained in $t$ distinct edges.

We prove “robust” versions of Dirac-type theorems for Hamilton cycles and optimal matchings.

Let $\mathcal{H}$ be a $k$-uniform hypergraph on $n$ vertices with $n \in (k-1)\mathbb{N}$ and codegree at least $n/(2k-2)$, and let $\mathcal{H}_p$ be a spanning subgraph of $\mathcal{H}$ such that each edge of $\mathcal{H}$ is included in $\mathcal{H}_p$ with probability $p$ independently at random. We prove that a.a.s. $\mathcal{H}_p$ contains a loose Hamilton cycle if $p = \Omega(n^{-k+1} \log n)$, which is asymptotically best possible. We also present similar results for Hamilton $\ell$-cycles for $\ell \geq 2$.

Furthermore, we prove that if $\mathcal{H}$ is a $k$-uniform hypergraph on $n$ vertices with $n \notin k \mathbb{N}$ and codegree at least $\lfloor n/k \rfloor$, then a.a.s. $\mathcal{H}_p$ contains a matching of size $\lfloor n/k \rfloor$ if $p = \Omega(n^{-k+1} \log n)$. This is also asymptotically best possible.

This is joint work with Michael Anastos, Debsoumya Chakraborti, Abhishek Methuku, and Vincent Pfenninger.

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

## Dong Yeap Kang (강동엽) gave an online talk on the proof of the Erdős-Faber-Lovász conjecture (1972) at the Virtual Discrete Math Colloquium

On January 27, 2021 at the Virtual Discrete Math Colloquium, Dong Yeap Kang (강동엽) from the University of Birmingham presented his recent breakthrough on the Erdős-Faber-Lovász conjecture, jointly with Tom Kelly, Daniela Kühn, Abhishek Methuku, and Deryk Osthus. The title of his talk is “A proof of the Erdős-Faber-Lovász conjecture“.

## Dong Yeap Kang (강동엽), A proof of the Erdős-Faber-Lovász conjecture

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.

## Dong Yeap Kang presented his work on random perturbed graphs at the discrete math seminar

On February 18, 2020, Dong Yeap Kang from KAIST & IBS Discrete Mathematics Group gave a talk on random perturbed graphs. The title of his talk is “Fragile minor-monotone parameters under random edge perturbation“. Dong Yeap will receive the Ph.D. degree at the end of this month from KAIST and will move to University of Birmingham, UK as a postdoc.

## Dong Yeap Kang (강동엽), Fragile minor-monotone parameters under random edge perturbation

We investigate how minor-monotone graph parameters change if we add a few random edges to a connected graph $H$. Surprisingly, after adding a few random edges, its treewidth, treedepth, genus, and the size of a largest complete minor become very large regardless of the shape of $H$. Our results are close to best possible for various cases. We also discuss analogous results for randomly perturbed bipartite graphs as well as the size of a largest complete odd minor in randomly perturbed graphs.