COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

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

## K_r-saturated graphs with large minimum degreeAdd 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 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. |
## Other listsFrom Genotype to Phenotype: Resources and Challenges (10th June 2009, Hinxton) DELETED CUSEAF## Other talksCANCELLED DUE TO UCU STRIKES: A Great Ape Dictionary: now what? Analysing the immunity profile of group A meningococcus in Ghana GENDER FLUIDITY: Progress and pushbacks in the UK today Western Science and Buddha Dhamma LMB Seminar: TBC Formalisation of the Balog–Szemerédi–Gowers Theorem in Isabelle/HOL |