Da Qi Chen, Bipartite Saturation

In extremal graph theory, a graph G is H-saturated if G does not contain a copy of H but adding any missing edge to G creates a copy of H. The saturation number, sat(n, H), is the minimum number of edges in an n-vertex H-saturated graph. This class of problems was first studied by Zykov and Erdős, Hajnal, and Moon. They also determined the saturation number when H is a clique and classified the extremal structures.

In this talk, we will focus mainly on the bipartite saturation problem (which was also first introduced by Erdős, Hajnal, and Moon). Here, we always assume that both G and H are bipartite graphs. Then, G is H-saturated if G does not contain H but adding any missing edge across the bipartition creates a copy of H. We can then similarly define sat(n, H) as the minimum number of edges of an n-by-n bipartite graph that is also H-saturated. One of the most interesting and natural questions here is to determine the saturation number for the complete bipartite graph $K_{s, t}$. When s=t, the saturation number and its extremal structures were determined long ago but nothing else is known for the general case. Half a decade ago, Gan, Korandi, and Sudakov gave an asymptotically tight bound that was only off by an additive constant.  We will highlight the main ideas behind that proof and show, with some additional techniques, how the bound can be improved to achieve tightness for the case when s=t-1.

This talk is based on collaborative work with Debsoumya Chakraborti and Mihir Hasabnis. See arXiv: https://arxiv.org/abs/2009.07651 for the full paper.