Springe direkt zu Inhalt

Colloquium by Patrick Morris (Freie Universität Berlin): Triangle factors in pseudorandom graphs

Jun 21, 2021 | 04:00 PM s.t.

An (n, d, λ)-graph is an n vertex, d-regular graph with second eigenvalue in absolute value λ. When λ is small compared to d, such graphs 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 existence 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, λ)-graph G in fact contains a triangle factor: vertex disjoint triangles covering the whole vertex set. 
In this talk, we discuss a solution to the conjecture of Krivelevich, Sudakov and Szab ́o. The result can be seen as a clear distinction between pseudorandom graphs and random graphs, showing that essentially the same pseudorandom condition that ensures a triangle in a graph 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 such a graph G contains every graph on n vertices with maximum degree at most 2.

Time & Location

Jun 21, 2021 | 04:00 PM s.t.


Freie Universität Berlin
Technische Universität Berlin
Humboldt-Universität zu Berlin
Deutsche Forschungsgemeinschaft (DFG)