BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:K_r-saturated graphs with large minimum degree -  Dr A. Calbert Ri
 podas (QMUL)
DTSTART:20230202T143000Z
DTEND:20230202T153000Z
UID:TALK196837@talks.cam.ac.uk
CONTACT:103978
DESCRIPTION:Given a graph H\, we say that a graph G is H-saturated if G is
  maximally H-free\, meaning G contains\nno copy of H but adding any new ed
 ge to G creates a copy of H. The saturation problem is to determine\nthe s
 aturation number sat(n\,H)\, the minimum number of edges in an H-saturated
  graph G on n vertices.\nThe saturation number of cliques was determined e
 xactly by Erdos\, Hajnal and Moon in the 60s. The problem\nbecomes more in
 teresting\, however\, if we additionally impose the condition that the min
 imum degree of G be large.\n\nLet sat(n\,K_r\,t) be the minimum number of 
 edges in a K_r-saturated graph G on n vertices which additionally has mini
 mum degree at least t.\nDay 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 depen
 ding on r and t. He raised the problem of estimating\nc(r\,t) and proved t
 he estimates 2^t t^(3/2) << c(r\,t) \\leq  t^(t^(2t^2)) for fixed r and la
 rge t. In this talk\, I will present a result that shows that\, for fixed 
 r and large t\,\nthe order of magnitude of c(r\,t) is 4^t t^(-1/2)\, and m
 oreover gives information about the dependence on r. I will also discuss a
 nother result\, which states that all the extremal graphs\nare blow-ups of
  some small graph.\n\nThe problem of estimating c(r\,t) turns out to be in
 timately related to a celebrated result in extremal set theory known as th
 e Two Families Theorem. There are\nseveral different versions of this theo
 rem. I will discuss some of these and present a new version of the theorem
  which is needed in the proofs.
LOCATION:MR12
END:VEVENT
END:VCALENDAR