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 > On the evolution of structure in triangle-free graphs

## On the evolution of structure in triangle-free graphsAdd to your list(s) Download to your calendar using vCal - Matthew Jenssen, Kings College London
- Thursday 09 November 2023, 14:30-15:30
- MR12.
If you have a question about this talk, please contact ibl10. ErdÅ‘s, Kleitman and Rothschild proved that the number of triangle-free graphs on n vertices is asymptotically the same as the number of bipartite graphs; or in other words, a typical triangle-free graph is bipartite. Osthus, Promel and Taraz proved a sparse analogue of this result: if m > (\sqrt{3}/4 +\epsilon) n^{3/2} \sqrt{\log n}, a typical triangle-free graph on n vertices with m edges is bipartite (and this no longer holds below this threshold). What do typical triangle-free graphs at sparser densities look like and how many of them are there? We consider what we call the ordered regime, where typical triangle-free graphs are not bipartite but have a dense max-cut. In this regime we prove asymptotic formulas for the number of triangle-free graphs and give a precise probabilistic description of their structure. This leads to further results such as determining the threshold at which typical triangle-free graphs are q-colourable for q > 2, determining the threshold for the emergence of a giant component in the complement of a max-cut, and many others. This is joint work with Will Perkins and Aditya Potukuchi. 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 listsflashacademy talks Department of Geography - Book launch Pitt-Rivers Archaeological Science Seminar Series## Other talksVariational Approach to KPZ Equation: Myths-Busting and Some Results The role of SARS-CoV-2 Membrane and Envelope proteins in protective immunity to COVID-19 The sweatshops of the consumer revolution. Economic growth, social inequality and material culture in Flanders and Brabant (c.18) Solution discovery in fluid dynamics using neural networks Seeing the world in a new light: Polychaete worms wriggle winding evolutionary paths to vision Introducing ACEpotentials.jl |