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.

On December 1, 2020, Debsoumya Chakraborti from the IBS Discrete Mathematics Group presented his theorem with Po-Shen Loh about the existence of a rainbow matching of size q in a simple graph whose edges are colored properly by 2q+o(q) colors. The title of his talk was “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.

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.

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.