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