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

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

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

## DIMAG had its first workshop “2019-1 IBS Workshop on Graph Theory”

DIMAG had its first workshop “2019-1 IBS Workshop on Graph Theory” on February 11 and 12, 2019. There were 6 invited talks — Jeong Han Kim (KIAS), Cory T. Palmer (Univ. of Montana), Martin Balko (Charles Univ.), Dong Yeap Kang (KAIST), Boram Park (Ajou Univ.), and Dániel Gerbner (Alfréd Rényi Institute of Mathematics). We would like to thank all speakers and participants.

The talks are recorded but due to technical problems, only four talks are available online.

## Schedule

### Feb. 11, 2019, Monday

1:30pm-2:20pm Jeong Han Kim: Entropy and sorting
2:20pm-3:10pm Cory T. PalmerGeneralized Turán problems – Berge hypergraphs
Coffee Break
4:00pm-4:50pm Martin BalkoRamsey numbers of edge-ordered graphs
4:50pm-5:40pm Dong Yeap Kang: On the rational Turán exponents conjecture
Banquet

### Feb. 12, 2019, Tuesday

9:30am-10:20am Boram ParkSum-free set problem on integers
Coffee Break
11:00am-11:50am Dániel GerbnerGeneralized Turán problems – counting subgraphs
Lunch

We plan to provide meals to all participants and provide a room at a near-by hotel for invited speakers and selected participants. Please register in the following form below by January 28, Monday; please register early if you want to receive the support for the accommodation.

## Abstracts

#### Jeong Han Kim (김정한), Entropy and Sorting

We reconsider the old problem of sorting under partial information, and give polynomial time algorithms for the following tasks: (1) Given a partial order P, find (adaptively) a sequence of comparisons (questions of the form, “is x < y?”) which sorts ( i.e., finds an unknown linear extension of) P using O(log(e(P))) comparisons in worst case (where e(P) is the number of linear extensions of P). (2) Compute (on line) answers to any comparison algorithm for sorting a partial order P which force the algorithm to use Ω(log(e(P))) comparisons. (3) Given a partial order P of size n, estimate e(P) to within a factor exponential in n. (We give upper and lower bounds which differ by the factor $n^n /n!$.) Our approach, based on entropy of the comparability graph of P and convex minimization via the ellipsoid method, is completely different from earlier attempts to deal with these questions.

Joint work with J. Kahn.

#### Cory T. Palmer, Generalized Turán problems – Berge hypergraphs

Let $F$ be a graph. We say that a hypergraph $H$ is a Berge-$F$ if there is a bijection $f : E(F) \rightarrow E(H )$ such that $e \subseteq f(e)$ for every $e \in E(F)$. Note that Berge-$F$ actually denotes a class of hypergraphs. The maximum number of edges in an $n$-vertex $r$-graph with no subhypergraph isomorphic to any Berge-$F$ is denoted $\operatorname{ex}_r(n,\textrm{Berge-}F)$. Observe that when $r=2$, then a Berge-$F$ is simply the graph $F$ and thus again we! are investigating the Tur\’an function $\operatorname{ex}(n,F)$.

In this talk we will survey results on the function $\operatorname{ex}_r(n,\textrm{Berge-}F)$ for various graphs $F$. We will also describe several interesting open problems.

#### Martin Balko, Ramsey numbers of edge-ordered graphs

An edge-ordered graph is a graph with linearly ordered set of edges. We introduce and study Ramsey numbers of edge-ordered graphs, called edge-ordered Ramsey numbers. We prove some basic properties of these numbers for general edge! -ordered graphs and we provide some stronger estimates for special classes of edge-ordered graphs. We also pose some new open problems and compare edge-ordered Ramsey numbers with the standard Ramsey numbers of graphs and with ordered Ramsey numbers, which are Ramsey numbers for graphs with linearly ordered vertex sets.

Joint work with Mate Vizer.

#### Dong Yeap Kang (강동엽), On the rational Turán exponents conjecture

The extremal number ${\rm ex}(n,F)$ of a graph $F$ is the maximum number of edges in an $n$-vertex graph not containing $F$ as a subgraph. A real number $r \in [1,2]$ is realisable if there exists a graph $F$ with ${\rm ex}(n , F) = \Theta(n^r)$. Several decades ago, Erdős and Simonovits conjectured that every rational number in $[1,2]$ is realisable. Despite decades of effort, the only known realisable numbers are $1,\frac{7}{5},2$, and the numbers of the form $1+\frac{1}{m}$, $2-\frac{1}{m}$, $2-\frac{2}{m}$ for integers $m \geq 1$. In particular, it is not even known whether the set of all realisable numbers contains a single limit point other than two numbers 1 and 2.

We discuss some recent progress on the conjecture of Erdős and Simonovits. First, we show that $2 – \frac{a}{b}$ is realisable for any integers $a,b \geq 1$ with $b>a$ and $b \equiv \pm 1 ~({\rm mod}\:a)$. This includes all previously known ones, and gives infinitely many limit points $2-\frac{1}{m}$ in the set of all realisable numbers as a consequence.

Secondly, we propose a conjecture on subdivisions of bipartite graphs. Apart from being interesting on its own, we show that, somewhat surprisingly, this subdivision conjecture in fact implies that every rational number between 1 and 2 is realisable.

This is joint work with Jaehoon Kim and Hong Liu.

#### Boram Park (박보람), Sum-free set problem on integers

For an abelian  group $G$, a set $A \subset G$ is sum-free if there are no $x, y, z \in A$ such that $x + y = z$. Sum-free sets was initiated by Schur (1916) by an attempt to prove the famous Fermat’s Last Theorem. Since then, there have been intensive and fruitful research in the field of additive combinatorics. One of great interest in the study of sum-free sets is to consider sum-free subsets of a set of integers, which has attracted a significant attention in the literature over the years.

In this talk, some recent results on sum-free sets of integers are discussed. Then we present a result on $k$-sum $\bf{n}$-free set, where $\bf{n}$ is an $n$-dimensional integer vector. The work is based on joint work with Ilkyoo Choi and Ringi Kim.

#### Dániel Gerbner, Generalized Turán problems – counting subgraphs

Given two graphs $H$ and $F$, our goal is to determine the maximum number of copies of $H$ in an $F$-free graph on $n$ vertices. The systematic research of these problems was initiated (after several sporadic results) by Alon and Shikhelman. I describe several results of mine in this area, with different sets of co-authors.

Joint work with Ervin Győri, Abhishek Methuku, Cory Palmer and Mate Vizer.

기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209