On the evolution of structure in triangle-free graphs

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