BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: An (n\, d\, λ)-graph is an n vertex\, d-regular graph with sec
 ond eigenvalue in absolute value λ. When λ is small compared to d\, such gr
 aphs have pseudo-random properties. A fundamental question in the study of 
 pseudorandom graphs is to find conditions on the parameters that guarantee 
 the existence of a certain subgraph. A celebrated construction due to Alon 
 gives a triangle-free (n\, d\, λ)-graph with d = Θ(n^2/3) and λ = Θ(d^2/n).
  This construction is optimal as having λ = o(d^2/n) guarantees the existen
 ce of a triangle in a (n\, d\, λ)-graph. Krivelevich\, Sudakov and Szab ́o 
 (2004) conjectured that if n ∈ 3N and λ = o(d^2/n) then an (n\, d\, λ)-grap
 h G in fact contains a triangle factor: vertex disjoint triangles covering 
 the whole vertex set.  In this talk\, we discuss a solution to the conjectu
 re of Krivelevich\, Sudakov and Szab ́o. The result can be seen as a clear 
 distinction between pseudorandom graphs and random graphs\, showing that es
 sentially the same pseudorandom condition that ensures a triangle in a grap
 h actually guarantees a triangle factor. In fact\, even more is true: as a 
 corollary to this result and a result of Han\, Kohayakawa\, Person and the 
 author\, we can conclude that the same condition actually guarantees that s
 uch a graph G contains every graph on n vertices with maximum degree at mos
 t 2. 
DTSTAMP:20210615T165100
DTSTART:20210621T160000
CLASS:PUBLIC
LOCATION:online
SEQUENCE:0
SUMMARY:Patrick Morris (Freie Universität Berlin): Triangle factors in pseu
 dorandom graphs
UID:107919082@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20210621-C-Morris.html
END:VEVENT
END:VCALENDAR