Abstract

Given a graph H, we say that a graph G is H-saturated if G is maximally H-free, meaning G contains no copy of H but adding any new edge to G creates a copy of H. The saturation problem is to determine the saturation number sat(n,H), the minimum number of edges in an H-saturated graph G on n vertices. The saturation number of cliques was determined exactly by Erdos, Hajnal and Moon in the 60s. The problem becomes more interesting, however, if we additionally impose the condition that the minimum degree of G be large.

Let sat(n,K_r,t) be the minimum number of edges in a K_r-saturated graph G on n vertices which additionally has minimum degree at least t. Day showed in 2017 that for fixed r and t, sat(n,K_r,t)=tn-c(r,t) for large enough n, where c(r,t) is a constant depending on r and t. He raised the problem of estimating c(r,t) and proved the estimates 2^{t t}(3/2) << c(r,t) \leq t^{) for fixed r and large t. In this talk, I will present a result that shows that, for fixed r and large t, the order of magnitude of c(r,t) is 4}t t^(-1/2), and moreover gives information about the dependence on r. I will also discuss another result, which states that all the extremal graphs are blow-ups of some small graph.

The problem of estimating c(r,t) turns out to be intimately related to a celebrated result in extremal set theory known as the Two Families Theorem. There are several different versions of this theorem. I will discuss some of these and present a new version of the theorem which is needed in the proofs.