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

Debsoumya Chakraborti, Some classical problems in 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$. The function $\operatorname{sat}(n,F)$ is defined to be the minimum number of edges in an $n$-vertex $F$-saturated graph.

In the first half of the talk, we will discuss a generalization of Erdős-Hajnal-Moon theorem (1964), which determined the value of $\operatorname{sat}(n,K_s)$. We resolve one of the fundamental questions of minimizing the number of cliques of size $r$ in a $K_s$-saturated graph for all sufficiently large number of vertices, confirming a conjecture of Kritschgau, Methuku, Tait, and Timmons. We further establish a corresponding stability result.

In the second half, we will focus on a central conjecture in graph saturation made by Tuza (1986), which states that for every graph $F$, the limit $\lim_{n \rightarrow \infty} \frac{\operatorname{sat}(n,F)}{n}$ exists. We make progress in the negative direction of this conjecture.

This talk will be based on a joint work with Po-Shen Loh.

Debsoumya Chakraborti, Rainbow matchings in edge-colored simple graphs

There has been much research on finding a large rainbow matching in a properly edge-colored graph, where a proper edge coloring is a coloring of the edge set such that no same-colored edges are incident. Barát, Gyárfás, and Sárközy conjectured that in every proper edge coloring of a multigraph (with parallel edges allowed, but not loops) with $2q$ colors where each color appears at least $q$ times, there is always a rainbow matching of size $q$. We prove that $2q + o(q)$ colors are enough if the graph is simple, confirming the conjecture asymptotically for simple graphs. We also make progress in the lower bound on the required number of colors for simple graphs, which disproves a conjecture of Aharoni and Berger. We use a randomized algorithm to obtain a large rainbow matching, and the analysis of the algorithm is based on differential equations method. We will also briefly comment on the limitations of using our probabilistic approach for the problem. This talk will be based on a joint work with Po-Shen Loh.

Debsoumya Chakraborti gave a talk on the problem of maximizing the number of cliques in a graph of small maximum degree at the Discrete Math Seminar

On September 15, 2020, Debsoumya Chakraborti from the IBS Discrete Mathematics Group presented a talk on the extremal problem on the number of cliques in a graph of small maximum degree with a fixed number of edges. The title of his talk was “Maximum number of cliques in a graph with bounded maximum degree“.

Debsoumya Chakraborti, Maximum number of cliques in a graph with bounded maximum degree

Generalized extremal problems have been one of the central topics of study in extremal combinatorics throughout the last few decades. One such simple-looking problem, maximizing the number of cliques of a fixed order in a graph with a fixed number of vertices and given maximum degree, was recently resolved by Chase. Settling a conjecture of Kirsch and Radcliffe, we resolve the edge variant of this problem, where the number of edges is fixed instead of the number of vertices. This talk will be based on joint work with Da Qi Chen.

Welcome Rutger Campbell and Debsoumya Chakraborti, new members of IBS Discrete Mathematics Group

The IBS discrete mathematics group welcomes Dr. Rutger Campbell and Dr. Debsoumya Chakraborti, new research fellows at the IBS discrete mathematics group from August 16, 2020.

Rutger Campbell received his Ph.D. from the Department of Combinatorics and Optimization at the University of Waterloo in 2020 under the supervision of Prof. Jim Geelen. He is interested in matroid theory and structural graph theory.

Debsoumya Chakraborti received his Ph.D. from the Program of Algorithms, Combinatorics, and Optimization at the Carnegie Mellon University in 2020 under the supervision of Prof. Po-Shen Loh. He is interested in extremal combinatorics, probabilistic combinatorics, and random graphs.

IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 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
Copyright © IBS 2018. All rights reserved.