K_r-saturated graphs with large minimum degree

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

• Dr A. Calbert Ripodas (QMUL)
• Thursday 02 February 2023, 14:30-15:30
• MR12.

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

This talk is part of the Combinatorics Seminar series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• Combinatorics Seminar
• DPMMS Lists
• DPMMS Pure Maths Seminar
• DPMMS info aggregator
• DPMMS lists
• Hanchen DaDaDash
• Interested Talks
• MR12
• School of Physical Sciences
• bld31

Note that ex-directory lists are not shown.