University of Cambridge > > Combinatorics Seminar > K_r-saturated graphs with large minimum degree

K_r-saturated graphs with large minimum degree

Add to your list(s) Download to your calendar using vCal

  • User Dr A. Calbert Ripodas (QMUL)
  • ClockThursday 02 February 2023, 14:30-15:30
  • HouseMR12.

If you have a question about this talk, please contact ibl10.

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 2t 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 4t 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.

This talk is part of the Combinatorics Seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2024, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity