BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY: On the evolution of structure in triangle-free graphs - Matthew J
 enssen\, Kings College London
DTSTART:20231109T143000Z
DTEND:20231109T153000Z
UID:TALK207808@talks.cam.ac.uk
CONTACT:103978
DESCRIPTION:Erdős\, Kleitman and Rothschild proved that the number of tri
 angle-free\ngraphs on n vertices is asymptotically the same as the number 
 of bipartite\ngraphs\; or in other words\, a typical triangle-free graph i
 s bipartite.\nOsthus\, Promel and Taraz proved a sparse analogue of this r
 esult: if m >\n(\\sqrt{3}/4 +\\epsilon) n^{3/2} \\sqrt{\\log n}\, a typica
 l triangle-free graph\non n vertices with m edges is bipartite (and this n
 o longer holds below\nthis threshold). What do typical triangle-free graph
 s at sparser densities\nlook like and how many of them are there? We consi
 der what we call the\nordered regime\, where typical triangle-free graphs 
 are not bipartite but\nhave a dense max-cut. In this regime we prove asymp
 totic formulas for the\nnumber of triangle-free graphs and give a precise 
 probabilistic description\nof their structure. This leads to further resul
 ts such as determining the\nthreshold at which typical triangle-free graph
 s are q-colourable for q > 2\,\ndetermining the threshold for the emergenc
 e of a giant component in the\ncomplement of a max-cut\, and many others. 
 This is joint work with Will\nPerkins and Aditya Potukuchi.
LOCATION:MR12
END:VEVENT
END:VCALENDAR